Индексная сортировка, индексный массив

[FasterHarder]

Всем хай! Без лишних прелюдий переходим к делу.

Условие такое:
Построить индексный массив, упорядочивающий данные по возрастанию (индексация в массиве начинается с 1):
25 3 2 9 14 10 13 40 3 16
----------------------
Привлекла мое внимание эта фраза "индексный массив"!
Немного погуглив примерно понял, что это такое. Правда во всех примерах писали про составные данные (аля структура/класс), но это ладно...

Правильно ли я понимаю, что надо вот, что сделать:
1. На вход программе подаются целые числа ---> сохраняем их в одномерном массиве.
2. Создаем новый массив такого же размера. Элементы этого массива равны значениям своих индексов

indexVector[i] := i;

3. Сортируем массив indexVector, отталкиваясь от значения элементов массива из п.1. Т е упорядочиваем индексы в массиве indexVector, не меняя взаимного расположения стартовых чисел.
4. На выходе распечатываем содержимое indexVector. Для примера в этом посте: 3 2 9 4 6 7 5 10 1 8. И вот это и будет являться ИНДЕКСНЫМ МАССИВОМ, да?

Допустим, если все описал выше корректно, то остается вопрос: а каким способом сортировки надо производить упорядочивание-то? Любым? (как правило от сортируемых данных зависит, конечно). Ну, допустим, Шелла...
2. Этот алгоритм называют индексной сортировкой?

спс. за внимание

[Akina]

Цитата FasterHarder @ 22.05.21, 10:14

а каким способом сортировки надо производить упорядочивание-то? Любым?

Нет. У тебя не определено поведение при наличии в исходном массиве равных элементов. Для примера в этом посте 3 9 2 4 6 7 5 10 1 8 также будет являться корректным ответом без дополнительных уточнений. А если будет дополнено, что для равных элементов индексы для них должны располагаться в определённом порядке (скажем, по возрастанию), то на выбор метода сортировки начинают влиять соображения устойчивости.

[AVA12]

Устойчивость - не проблема. Любой алгоритм сортировки можно сделать устойчивым, если использовать составной ключ (элемент, индекс_в_исходном_массиве). В данном случае если в исходном массиве A[B[i]] = A[B[j]], то сравниваем элементы индексного массива B[i] и B[j], которые различны по определению.

[FasterHarder]

Akina, вот знаешь, а на мой взгляд ты фантастично точно описал проблему!
именно, когда есть одинаковые элементы сортировка сбивается из-за неустойчивости. Тестировал на др.данных, не как в этом примере

Причем, если в сравнении заменить "<" на "<=", то вообще получается совсем другой ответ (неправильный)...
За базовую сортировку взял сортировку выбором минимального. В итоге еле-еле закодировал...

вот фрагмент кода сортировки:

 for i := 1 to N do
        index[i] := i;
      
  
    for i := 1 to (N - 1) do
    begin
        imin := index[i];
        for j := (i + 1) to N do
        begin
            if(data[index[j]] < data[imin]) then  // если поменять на <=, то получается белиберда
                imin := j;
        end;
        //writeln('i = ', i, ';   imin = ', imin);
              
        //write(imin:6);
        //if(index[imin] <> index[i]) then
        begin
            swap := index[imin];
            index[imin] := index[i];
            index[i] := swap;
        end;
        //for j := 1 to N do
        //    write(index[j]:4);
        //readln;
    end;

я потратил более часа, чтобы это написать), но так и не уверен, а правильно ли здесь все, лол. В принципе, да, в 99% все ок, но, вот когда есть одинаковые элементы (как ты точно заметил), то индексы идут не по порядку (точнее, иногда они идут по порядку, иногда - нет). Как с этим бороться - ума не приложу.

Вообще оказалось сложнее здесь все, чем казалось изначально...

Сообщение отредактировано: FasterHarder - 23.05.21, 18:11

[Akina]

Цитата FasterHarder @ 23.05.21, 18:07

Как с этим бороться - ума не приложу.

Сперва найди ответ на вопрос "зачем с этим бороться, и надо ли бороться вообще".

Построение индекса - он ведь не для того, чтобы построить индекс. А для того, чтобы быстро найти в массиве нужный элемент. И, если элемент идентифицируется только значением, то глубоко сиренево, какой из них найден, второй или девятый. найден = этого достаточно. А как только появляется разница - так появляется дополнительное условие при сортировке, и уже не только значение принимается во внимание.

Т.е. на мой взгляд в прикладном смысле устойчивость не имеет никакого значения вообще, равно как и сохранение порядка. Зато важно правильное, корректное и полное формулирование критерия сортировки (сравнения элементов при выполнении сортировки).

Добавь в него сравнение исходных позиций при равенстве значений - и вот проблема ушла, потому что выражение сортировки стало уникальным.

Добавлено 23.05.21, 18:52

Цитата AVA12 @ 23.05.21, 17:47

Устойчивость - не проблема. Любой алгоритм сортировки можно сделать устойчивым, если использовать составной ключ (элемент, индекс_в_исходном_массиве).

А это по большому счёту изменение выражения сортировки - то есть изменение исходного задания. Что может быть и не очень корректным.

[FasterHarder]

Akina, полностью согласен с твоими рассуждениями.

вроде я разобрался и окончательно понял со всей этой индексной сортировкой
1. такой прием хорош, когда, например, данные СЛОЖНЫЕ/составные, т е много полей, вложенных массивов, объектов классов и пр. В этом случае менять местами элементы оч.затратно (а если еще и deep copy идет, то совсем может долго исполняться). Не, другое дело, когда в массиве УКАЗАТЕЛИ на данные, тогда можно сортировать через указатели без всяких индексов. И, когда данные сложные, то там и более точные критерии сортировки образуются. Тут вроде все понятно)..надеюсь, что я правильно понял)

2. а насчет того, что порядок элементов с одинаковым значением иногда меняется - проблема в сортировке выбором! Ведь при этой сортировке меняется местами 1ый элемент из неотсортированной части, с минимаксным элементом и в итоге 1ый элемент "улетает" в хвост(на место минимаксного). А если это был дубликатный элемент, то он уходит за своего близнеца (дубликата) и впоследствии его близнец обрабатывается РАНЬШЕ, хотя на старте стоял позже...вроде в этом проблема) Необходимо поменять тип сортировки и отказаться от выбором, а, например, использовать ВСТАВКАМИ, т к при вставках происходит сдвиг и взаимное расположение элементов НЕ меняется

Всем спс, особенно Akina, особенно за пост №2 - точнейшее попадание в проблему)

Скрытый текст

p.s. что-то не припомню у Макконела описание этого приема (индексный массив) в "Совершенном коде", хотя может не обратил внимание...он должен был об этом где-то написать все равно)

[FasterHarder]

в итоге победил сортировкой обмена (пузырьком, даже оптимальным вроде пузырьком), т к выбором нереал, а на вставках тоже устойчивость сбивалась
сейчас все работает как часы:

    for i := 2 to N do
    begin
        for j := N downto i do
        begin
            if(data[index[j]] < data[index[j - 1]]) then
            begin
                swap := index[j];
                index[j] := index[j - 1];
                index[j - 1] := swap;
            end;
        end;
    end;

Еще применение этой индексной сортировки: когда надо, чтобы данные оставались в первоначальном состоянии, но при этом вывести их надо в отсортированном виде для каких-либо нужд временно/одномоментно...

Скрытый текст

До чего же неприятная сортировка вставками! Вроде считается, что способы: пузырек, выбором и вставками равны по силе и по простоте, но, ИМХО, насколько же неудобно кодить вставками)...Стараюсь избегать ее до последнего!

[AVA12]

Цитата

Любой алгоритм сортировки можно сделать устойчивым, если использовать составной ключ (элемент, индекс_в_исходном_массиве). В данном случае если в исходном массиве A[B[i]] = A[B[j]], то сравниваем элементы индексного массива B[i] и B[j], которые различны по определению.

Цитата

в итоге победил сортировкой обмена (пузырьком, даже оптимальным вроде пузырьком), т к выбором нереал, а на вставках тоже устойчивость сбивалась

Похоже, мне на пенсию пора. Я уже нихрена не понимаю в современной культуре программирования.

[scrambrella]

Пузырёк оптимальным не бывает. Разве что на очень маленьких массивах.

[Akina]

Цитата scrambrella @ 31.05.21, 12:37

Пузырёк оптимальным не бывает.

Да сколько угодно... надо быстренько прогнать программку в три оператора, готовых сортирных библиотек под рукой нет - что может быть проще, чем за минуту накидать пузырёк?