Стабильный, эффективный сорт?

Question

Я пытаюсь создать необычную реализацию ассоциативного массива, которая очень экономит пространство, и мне нужен алгоритм сортировки, который удовлетворяет всем следующим требованиям:

1. Стабильный (не изменяет относительный порядок элементов с равными ключами.)
2. Стек на месте или почти на месте (O (log n) - это нормально, но нет использования O (n) пространства или кучи.
3. O (n log n) сложность времени.

Также обратите внимание, что сортируемая структура данных - это массив.

Легко видеть, что есть базовый алгоритм, который соответствует любым 2 из этих трех (сортировка вставок соответствует 1 и 2, сортировка слиянием соответствует 1 и 3, сортировка кучи соответствует 2 и 3), но я не могу для себя найдите все, что соответствует всем трем критериям.

Answer 1

Я считаю, что сортировка слиянием может быть написана на месте. Это может быть лучший маршрут.

Answer 2

Примечание : стандартная быстрая сортировка не O (n log n)! В худшем случае это может занять до O (n ^ 2) времени. Проблема в том, что вы можете поворачиваться на элементе, который далек от медианы, поэтому ваши рекурсивные вызовы сильно разбалансированы.

Существует способ борьбы с этим, который заключается в тщательном подборе медианы, которая гарантированно или, по крайней мере, очень вероятно, будет близка к медиане. Удивительно, что на самом деле вы можете найти точную медиану в линейном времени, хотя в вашем случае это звучит так, как будто вы заботитесь о скорости, поэтому я бы не советовал этого.

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

Кстати, сортировка слиянием может быть выполнена на месте, хотя сложно и на месте, и на стабильном уровне.

Answer 3

Список Википедии содержит список алгоритмов сортировки. Включает категоризацию по времени выполнения, стабильности и распределению.

Ваша лучшая ставка, вероятно, будет состоять в том, чтобы изменить эффективный нестабильный сорт, чтобы он был стабильным, что сделает его менее эффективным.

Answer 4

А как насчет быстрой сортировки?

Exchange тоже может сделать это, может быть более "стабильным" по вашим условиям, но быстрая сортировка быстрее.

Answer 5

Быстрая сортировка может быть сделана стабильной, если сделать это в связанном списке. Это стоит n, чтобы выбрать случайный или медиану из 3 пивотов, но с очень маленькой константой (обход списка).

Разделив список и убедившись, что левый список отсортирован так, что одинаковые значения идут влево, а правый список отсортирован так, что одинаковые значения идут вправо, сортировка будет стабильной без каких-либо дополнительных затрат. Кроме того, поскольку это относится к присваиванию, а не к обмену, я думаю, что скорость может быть немного лучше, чем быстрая сортировка в массиве, поскольку существует только одна запись.

Итак, в заключение перечислите все ваши элементы и выполните быструю сортировку в списке

Answer 6

Быструю сортировку можно сделать достаточно простой, просто добавив в каждую запись поле последовательности, инициализируя его в индексе перед сортировкой и используя его как наименее значимую часть ключа сортировки.

Это немного отрицательно влияет на затраченное время, но не влияет на временную сложность алгоритма. Он также имеет минимальные накладные расходы на хранение для каждой записи, но это редко имеет значение, пока вы не получите очень большое количество записей (и минимизируется при больших размерах записи).

Я использовал этот метод с функцией C qsort(), чтобы не писать свои собственные. К каждой записи добавляется 32-разрядное целое число и заполняется начальным порядковым номером перед вызовом qsort().

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

Ваш пробег может варьироваться, поэтому всегда помните: Измерьте, не угадайте!

Answer 7

Поскольку ваши элементы находятся в массиве (а не, скажем, в связанном списке), у вас есть некоторая информация об их первоначальном порядке, доступная вам в самих индексах массива. Вы можете воспользоваться этим, написав свои функции сортировки и сравнения, чтобы знать индексы:

function cmp( ar, idx1, idx2 )
{
   // first compare elements as usual
   rc = (ar[idx1]<ar[idx2]) ? -1 : ( (ar[idx1]>ar[idx2]) ? 1 : 0 );

   // if the elements are identical, then compare their positions
   if( rc != 0 )
      rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0);

   return rc; 
}

Этот метод может использоваться для обеспечения стабильности любого вида, если только сортировка выполняет обмен элементов. Индексы элементов изменятся, но относительный порядок идентичных элементов останется прежним, поэтому сортировка останется устойчивой. Это не будет работать из коробки для такой сортировки, как heapsort, потому что оригинальная heapification «выбрасывает» относительный порядок, хотя вы можете адаптировать эту идею к другим видам.

Answer 8

Существует класс стабильных алгоритмов слияния на месте, хотя они являются сложными и линейными с довольно высокой константой, скрытой в O (n). Чтобы узнать больше, взгляните на эту статью и ее библиографию .

Редактировать: фаза слияния является линейной, таким образом, сортировка слиянием равна nlog_n.

Answer 9

Я реализовал стабильную быструю сортировку на месте и стабильную сортировку на месте слияния . Сортировка слиянием выполняется немного быстрее и гарантированно работает в O (n * log (n) ^ 2), но не в быстрой сортировке. Оба используют O (log (n)) пробел.

Answer 10

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

Например, чтобы ответить на ваш конкретный вопрос, вам нужно выбрать сортировку слиянием на месте.

Тем не менее, вы также можете взглянуть на strand sort , у него есть некоторые очень интересные свойства.