Сортировка отрицательных и положительных элементов

@Pavel_n · Регистрация: 07.04.2012

Студворк — интернет-сервис помощи студентам

Всем привет!
Есть такое задание:
Упорядочить массив так, чтобы все положительные числа были расположены сначала по возростанию, а все отрицательные - в конце по убыванию.

Как поставить правильно условия, чтобы отбирались сначала положительные, потом отрицательные? Или лучше сделать это в двух подпрограммах?
Буду рад любой помощи.
Благодарю!

P.S. Пробовал различные варианты - не получалось. На форуме искал - не нашел.

Вот получилась просто сортировка по возростанию (подпрограмма)

C++
1
2
3
4
5
6
7
8
9
10
sort_pol(int a[], int n)
{int i,j,tmp;
for(i=0;i<n-1;i++)
   for(j=i+1;j<n;j++)
   if(a[i]>a[j])
      {tmp=a[i];
      a[i]=a[j];
      a[j]=tmp;
      }
}

Добавлено через 12 часов 14 минут
Получилось!!!
Все намного проще чем Я думал.
Скидываю программку может кому пригодиться:

mimicria · 11.02.2013, 15:00

Сообщение от Pavel_n

Все намного проще чем Я думал.

Ну формально условие не выполнено, потому как массив не упорядочен согласно правил, только вывод в memo

@Pavel_n · 11.02.2013, 18:20 **[ТС]**

Сообщение от mimicria

Ну формально условие не выполнено, потому как массив не упорядочен согласно правил, только вывод в memo

Результата Я добился

.
У меня не получаеться в подпрограмме выбрать только положительные (или отрицательные). Я не знаю куда это if впихнуть.

@volvo · 11.02.2013, 18:48

Pavel_n, всё проще, не надо вообще никаких if, кроме того что у тебя уже есть:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    const int n = 10;
    int a[n] = {1, 4, 2, 18, -22, -11, 5, 17, -92, -88};
 
 
    for(int i = 0; i < n; i++)
        for(int j = n - 1; j > i; j--)
            if((a[j-1] > 0 && a[j] > 0 && a[j-1] > a[j]) || // Два положительных => сортируем по возрастанию
               (a[j-1] < 0 && a[j] < 0 && a[j-1] < a[j]) || // два отрицательных => по убыванию
               (a[j-1] * a[j] < 0 && a[j-1] < a[j])) // положительное и отрицательное => положительное впереди
            {
                int T = a[j - 1];
                a[j - 1] = a[j];
                a[j] = T;
            }

было: <1, 4, 2, 18, -22, -11, 5, 17, -92, -88>
стало: <1, 2, 4, 5, 17, 18, -11, -22, -88, -92>

@Pavel_n · 11.02.2013, 21:44 **[ТС]**

UI, что Я могу сказать. Благодарю! Работает! +

@FasterHarder · 20.10.2022, 08:55

volvo, привет, твой пост #4 спас меня

------------------------------------------------------------------------
#1
У меня очень похожая задача, правда не 2 категории ( положительные, отрицательные ), а 3 - еще добавляются нулевые элементы. Сортировка такого плана: нулевые, затем положительные ( ASC ), затем отрицательные ( DESC )
Мне люто повезло, т к оказалось, что можно объединить категорию нулевых и положительных, превратив ее в неотрицательные

В этом случае поменялись немного условия:

C
1
if( ( ( a[ j - 1] >= 0 ) and ( a[ j ] >= 0 ) and ( a[ j - 1 ] > a[ j ] ) ) or           // Два положительных => сортируем по возрастанию

и это

C
1
( ( a[ j - 1 ] * a[ j ] <= 0 ) and ( ( a[ j - 1 ] < 0 ) or ( a[ j ] < 0 ) ) and ( a[ j - 1 ] < a[ j ] ) ) ) // неотрицательное и отрицательное => неотрицательное вперед

Все отработало на отлично

Но есть такой момент, а если бы надо было сортироваться по правилу:
<положительные на убывание><нули><отрицательные на возрастание>
В этом случае ведь никакие 2 категории не объединяются в одну. К чему бы это привело? В твоем посте #4 стоит 3 подусловия ( плюс-плюс, минус-минус, плюс-минус ) и это ТОЛЬКО для двух групп чисел ( полож. и отр. ), а если будет ТРИ группы, то кол-во проверок не будет расти по степени какой-нибудь...Т е нужно уже сравнивать 0-плюс, 0-минус, плюс-плюс и т.п. В этом случае if превратится в что-то страшное.
------------------------------------------------------------------------
#2
Как считаешь, может имеет немного декомпозировать код и вынести эту проверку в if в отдельную функцию, для моей задачи получилась такая:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// эта функция проверяет, надо ли переставлять элементы массива местами в процессе сортировки
// a -> A[ j - 1 ]; b -> A[ j ]
int Is_ready_to_swap( const int a, const int b )
{
#define FAILURE 0
#define SUCCES ( !FAILURE )
 
    // два неотрицательных элемента => сортируем по возрастанию
    if ( ( a >= 0 ) and ( b >= 0 ) and ( a > b ) )
    {
        return SUCCES;
    }
 
    // два отрицательных элемента => сортируем по убыванию
    if ( ( a < 0 ) and ( b < 0 ) and ( a < b ) )
    {
        return SUCCES;
    }
 
    // неотрицательное и отрицательное => неотрицательное вперед
    if ( ( a * b <= 0 ) and ( ( a < 0 ) or ( b < 0 ) ) and ( a < b ) )
    {
        return SUCCES;
    }
 
    return FAILURE;
}

Вообще, в целом, это имеет место быть с тз техники программирования или неуместно?
Плюсы в том, что туда можно забить множество доп. проверок if, не потеряв в читабельности сильно. Для случая, когда 3 группы необъединяются их будет вроде около 7 штук...

Тогда перед обменом элементов такой вызов:

C
1
2
3
4
5
6
7
8
9
10
        for( j = n - 1; j > i; j--)
        {
            int ready_to_swap = Is_ready_to_swap( a[ j - 1 ], a[ j ] );
            if ( ready_to_swap == 1 )
            {
                int T = a[j - 1];
                a[j - 1] = a[j];
                a[j] = T;
            }
        }

------------------------------------------------------------------------
#3
Я так понимаю, что для сортировки ты выбрал разновидность обменной ( похоже чем-то на пузырек ) со сложностью O( n^2 ), где n - количество элементов сортируемого массива.
Но что-то до конца не понимаю, а можно ли сейчас, используя эту проверку

C
1
            int ready_to_swap = Is_ready_to_swap( a[ j - 1 ], a[ j ] );

перед тем, как переставлять элементы подключить любую другую, основанную на обменах, например "выбором", "Хоара", "Шелла", "пирамидальная ( если через массив дерамида строится )" и др. и таким образом поднять производительность до O( n * log( n ) )?
Речь только про сортировки "in place", т е, например не через двоичное дерево.
Такое чувство, что нет. Например в Хоара ведь получаем подпоследовательности через опорный элемент и все бьется лишь на 2 группы как бы. Хм...
------------------------------------------------------------------------
#4
Давай рассмотрим еще такой вариант, когда групп не 2 и не 3, а пусть 20. Например, есть массив объектов типа "Спортсмен". У него есть фио, ДР, возраст, вес и др. поля и есть ключевое поле "Вид спорта" ( футбол, хоккей и т.п.). Элементов много ( пусть 20К ), видов спорта разных ровно 20 шт. И нужно агрегировать спортсменов по виду спорта ( group by ), а внутри каждой группы отсортировать по разным полям( разные типы данные ). Например, футболистов по фио, хоккеистов по ДР и т.д. В этом случае составлять все возможные проверки в if, наверное, не стоит))
Тут для каждой группы потребуется свое условие для сортировки? Т е будет 20 функций? Для сортировки уже применить, например, некое подобие хеш-таблицы ( по названию спорта возвращает №слота ) на цепочках. И вставлять в цепочку ( это ЛОС будет, НЕ массив ) нужного спортсмена ( или ссылку на него ), сохраняя упорядоченность. Издалека похоже на карманную сортировку, очень издалека, ИМХО.
Или вообще все не так?

Спс. за внимание и сорри, что забрал у тебя кучу времени ( а я знаю, что оно очень дорого стоит ) на чтение всего этого...

@volvo · 20.10.2022, 10:33

FasterHarder, не разочаровывай меня, а?

Сообщение от FasterHarder

а если бы надо было сортироваться по правилу:
<положительные на убывание><нули><отрицательные на возрастание>

Это не все равно, что
<положительные и нули на убывание><отрицательные на возрастание>?

@FasterHarder · 20.10.2022, 10:43

блин, точно)
это получается неотрицательные по убыванию + отрицательные на возрастание - 2 группы, эх...
т е получается 0 всегда можно "присоединить" к какой-нибудь группе)

ну хорошо, но все равно, с 3 группами ( которые нельзя объединить ) ведь все усложняется?

ps: я уж давно разочаровал, мне терять нечего)

Алексей1153 · 20.10.2022, 11:49

эх, вот, за что я люблю STL

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
 
int main()
{
    int a[] = {1, 4, 2, 18, -22, -11, 5, 17, -92, -88, 3, -100, +44};
    
    for(auto i:a){std::cout<<i<<',';} std::cout<<'\n';
    
    //выполнение задания в три строчки
    auto second_begin=std::partition(std::begin(a),std::end(a),[](const auto& item){return item>=0;});
    std::sort(std::begin(a),second_begin);
    std::sort(std::make_reverse_iterator(std::end(a)),std::make_reverse_iterator(second_begin));
 
    for(auto i:a){std::cout<<i<<',';} std::cout<<'\n';
 
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@Pavel_n 1 / 1 / 2 Регистрация: 07.04.2012 Сообщений: 38
	11.02.2013, 21:44 [ТС]
	UI, что Я могу сказать. Благодарю! Работает! + 0

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726
	20.10.2022, 10:43
	блин, точно) это получается неотрицательные по убыванию + отрицательные на возрастание - 2 группы, эх... т е получается 0 всегда можно "присоединить" к какой-нибудь группе) ну хорошо, но все равно, с 3 группами ( которые нельзя объединить ) ведь все усложняется? ps: я уж давно разочаровал, мне терять нечего) 0