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

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

Изменить: фаза слияния является линейной, поэтому mergesort - nlog_n.

Ответ 6

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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

Короче: выполните несколько тестов.

Ответ 11

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

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

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

Ответ 12

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

Ответ 13

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