На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Индексная сортировка, индексный массив
Всем хай! Без лишних прелюдий переходим к делу.

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

----------------------
Привлекла мое внимание эта фраза "индексный массив"!
Немного погуглив примерно понял, что это такое. Правда во всех примерах писали про составные данные (аля структура/класс), но это ладно...

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

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

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

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

Нет. У тебя не определено поведение при наличии в исходном массиве равных элементов. Для примера в этом посте 3 9 2 4 6 7 5 10 1 8 также будет являться корректным ответом без дополнительных уточнений. А если будет дополнено, что для равных элементов индексы для них должны располагаться в определённом порядке (скажем, по возрастанию), то на выбор метода сортировки начинают влиять соображения устойчивости.
Устойчивость - не проблема. Любой алгоритм сортировки можно сделать устойчивым, если использовать составной ключ (элемент, индекс_в_исходном_массиве). В данном случае если в исходном массиве A[B[i]] = A[B[j]], то сравниваем элементы индексного массива B[i] и B[j], которые различны по определению.
Akina, вот знаешь, а на мой взгляд ты фантастично точно описал проблему!
именно, когда есть одинаковые элементы сортировка сбивается из-за неустойчивости. Тестировал на др.данных, не как в этом примере

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

вот фрагмент кода сортировки:
ExpandedWrap disabled
     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 -
Цитата FasterHarder @
Как с этим бороться - ума не приложу.

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

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

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

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

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

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

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

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

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

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

ExpandedWrap disabled
        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;


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

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

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

Похоже, мне на пенсию пора. Я уже нихрена не понимаю в современной культуре программирования.
Пузырёк оптимальным не бывает. Разве что на очень маленьких массивах.
Цитата scrambrella @
Пузырёк оптимальным не бывает.

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


Рейтинг@Mail.ru
[ Script execution time: 0,0334 ]   [ 19 queries used ]   [ Generated: 13.06.21, 14:19 GMT ]