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

Question

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

1. Stable (не изменяет относительный порядок элементов с равные ключи.)
2. на месте или почти на месте (O (не войти п) стек хорошо, но не O (N) использование пространства или кучи распределение.
3. О (п войти п) временную сложность.

Также обратите внимание, что структура данных, подлежащая сортировке, является arra у.

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

Answer 1

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

Обмен может сделать это тоже, может быть более «стабильным» на ваших условиях, но quicksort быстрее.

Answer 2

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

Answer 3

Возможно, shell sort? Если я правильно изучил курс данных, он, как правило, был стабильным, но хуже время O (n log^2 n), хотя оно выполняет O (n) на почти отсортированных данных. Он основан на сортировке вставки, поэтому он сортируется на месте.

Answer 4

Существует список алгоритмов сортировки на Wikipedia. Он включает классификацию по времени выполнения, стабильности и распределению.

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

Answer 5

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

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

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

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

Answer 6

Существует класс стабильных алгоритмов слияния на месте, хотя они сложны и линейны с довольно высокой константой, скрытой в O (n). Чтобы узнать больше, посмотрите на this article, and its bibliography.

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

Answer 7

Не беспокойтесь о O (n log n), пока не сможете продемонстрировать, что это имеет значение. Если вы можете найти алгоритм O (n^2) с существенно более низкой константой, пойдите для него!

Общий сценарий наихудшего сценария не имеет отношения к делу, если ваши данные сильно ограничены.

Вкратце: выполните несколько тестов.

Answer 8

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

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, потому что исходная кучка «отбрасывает» относительный порядок, хотя вы могли бы приспособить идею к другим видам.

Answer 9

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

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

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

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

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

Answer 10

Возможно, я немного в колесе, но мне нравится сортировка с использованием ручного кодирования. Это просто, стабильно и хорошо. Дополнительное временное хранилище, которое ему нужно, это всего лишь N*sizeof(int), что не так уж плохо.

Answer 11

Существует красивый список функций сортировки on wikipedia, который поможет вам найти любую функцию сортировки, которую вы используете.

Например, чтобы задать конкретный вопрос, похоже, что сортировка на месте на месте - это то, что вы хотите.

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

Answer 12

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

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

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

Answer 13

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