• dev nolj Жуйк, вопросец по алгоритмам.
    Есть массив, отортированный по определенному принципу. Скажем, по X.
    У некоторого (не очень большого) количества элементов в массиве X изменился, причем не на случайное число, а зависящее от предыдущего. т.е. увеличился или уменьшился на n.

    Каким образом быстро отсортировать массив снова?
    Гугление подсказывает Insertion sort, но на мой вкус это как-то не очень оптимально.
    Мне в голову приходит, что надо плясать от предыдущего индекса каждого элемента.
    (предварительно убрав их из массива конечно).
    Есть у кого здравые идеи? :)

Replies (12)

  • @Dyn, А что ты такое делаешь, если не секрет?
  • @Dyn, пока столь неопределённые данные про принцип сортировки и кол-во изменяемых элементов никто ничего толкового не подскажет, а хранение данных в массиве гарантирует, что будешь много раз гонять их по памяти туда-сюда. Кстати, совет сильно зависит от того, что является элементом массива.
  • @Kensay, сортировку объектов :)
  • @nikma, количество — думаю меньше тысячи. изменяется около или менее 10%. какая разница какой там элемент? алгоритмы сортировки он количества сравнений вроде как считают
  • @Dyn, да, но если у тебя большие элементы, то гонять их по памяти дорого. Используют индексную сортировку, к которой применяют какой-либо алгоритм. У тебя же массив и вставка элемента потребует копирования хвоста массива.
  • @nikma, госспади спаси и сохрани. кто ж хранит в массиве сам объект? ссылку на него хранят. :)
  • @Dyn, бывают и такие случаи. ИМХО или обобщённый алгоритм не учитывающий особенностей изменяемый элементов (сортровка шела или пирамидальная) или эвристики на тему сортировка слиянием. Массив старый сливается с массивом изменённых элементов, сам массив копируется. Память вроде не жалко в твоём случае.
  • @Dyn, массив изменённых сортируешь произвольным способом (он маленький). самый быстрый способ в твоём случае.
  • @nikma, не очень понял твой совет. память относительно не жалко, но это должно быть как можно более быстро. вот кстати если не очень понятно объяснил идею исходный массив: 1 1 2 3 4 7 9 11 15 15. (11 на 10, 15 на 13) — 1 1 2 3 4 7 9 10 13 15 — (10 на 8, 13 на 16) — 1 1 2 3 4 7 8 9 15 16
  • @nikma, пузырьковой — медленно получается
  • @Dyn, старый массив не трогаем. точнее помечаем изменённые элементы. что-то вроде удаления. Изменённые складываем в новый массив. Перед вставкой его сортируем, например пирамидальной. Далее слияние двух массивов в новом массиве.
  • @nikma, ща я тебе в жаббер стукнусь