Сортировка по O (n * log (n)) в худшем случае

Question

Существует ли некий массив, который работает в O (n * log (n)) наихудшем времени?

Я видел в Википедии, что есть такие сортировки, но они нестабильный , что это значит?Есть ли способ сделать это при малой сложности?

Существует ли лучший алгоритм сортировки?

Answer 1

Алгоритм, который требует только O (1) дополнительной памяти (так что изменение входного массива разрешено) обычно описывается как «на месте», и это самая низкая сложность пространства.

A sortописывается как «стабильный» или нет, в зависимости от того, что происходит, когда на входе есть два элемента, которые сравнивают как равные, но как-то различимы.Например, предположим, что у вас есть куча записей с целочисленным полем и строковым полем, и вы сортируете их по целочисленному полю.Вопрос в том, что если две записи имеют одно и то же целочисленное значение, но разные строковые значения, то будет ли та, которая была первой во входных данных, также первой в выходных данных, или возможно, что они будут перевернуты?Стабильная сортировка - это та, которая гарантирует сохранение порядка элементов, которые сравниваются одинаково, но не идентичны.

Трудно сделать сортировку сравнения на месте, и * 1008.* Стабильный, и достигает O(n log n) сложность времени наихудшего случая.У меня есть смутное представление о том, что неизвестно, возможно ли это, или нет, но я не в курсе этого.

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

Как выполнить сортировку на месте с использованием алгоритма сортировки слиянием?

Что касается «наилучшей» сортировки- в некоторых стратегиях сортировки используется тот факт, что в целом, принимая во внимание большое количество приложений, компьютеры тратят много времени на сортировку данных, которые не перетасовываются случайным образом, а имеют некоторую структуру. Timsort - это алгоритм, позволяющий использовать преимущества часто встречающейся структуры.Он очень хорошо работает во многих практических приложениях.Вы не можете описать это как «лучший» вид, так как это эвристика, которая, кажется, хорошо работает на практике, а не является строгим улучшением предыдущих алгоритмов.Но это «самый» известный из всех, по мнению людей, которые поставляют его в качестве сортировки по умолчанию (Python, Java 7, Android).Вы, вероятно, не охарактеризовали бы это как «сложность с малым пространством», хотя это не лучше, чем стандартная сортировка слиянием.

Answer 2

Для вопроса лучший алгоритм, простой ответ: это зависит . Это зависит от размера набора данных, который вы хотите отсортировать, это зависит от ваших требований. Скажите , Пузырьковая сортировка имеет наихудший случай и среднюю сложность как О (n ² ), где n - количество сортируемых элементов. Существует много алгоритмов сортировки с существенно лучшей наихудшей или средней сложностью O (n log n). Даже другие алгоритмы сортировки О (n ² ), такие как сортировка вставкой , имеют тенденцию иметь лучшую производительность, чем пузырьковая сортировка . Поэтому пузырьковая сортировка не является практичным алгоритмом сортировки, когда n большое.

Среди простых алгоритмов average среднего (n ² ) сортировка выбора почти всегда превосходит пузырьковая сортировка , но обычно превосходит вставку сортировать .

выборочная сортировка значительно превосходит на больших массивах алгоритмы Θ (n log n) «разделяй и властвуй», такие как mergesort . Тем не менее, сортировка вставки или сортировка выбора , как правило, быстрее для небольших массивов.

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

Answer 3

Вы можете проверить между mergesort, quicksort или heapsort все хорошо описанные здесь .

Существует также сортировка по радиусу, сложность которой составляет O (кН), но она в полной мере использует дополнительное потребление памяти.

Вы также можете увидеть , что для небольших коллекций быстрая сортировка выполняется быстрее, но тогда Mergesort берет на себя инициативу, но все это зависит от конкретного случая, поэтому найдите время, чтобы изучить все 4 алгоритма

Answer 4

Относительно вашего вопроса, означающего «стабильный», давайте рассмотрим следующее: у нас есть класс детей, связанных с возрастом:

Phil, 10
Hans, 10
Eva, 9
Anna, 9
Emil, 8
Jonas, 10

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

Теперь наступает стабильность: Если мы сортируем stable , мы сортируем Фила, Ганса и Джонаса в том порядке, в котором они были раньше, то есть сначала мы помещаем Фила, затем Ганса и, наконец, Джонаса (просто потому, что они были в этом порядке в оригиналепоследовательность, и мы рассматриваем только возраст как критерий сравнения).Точно так же мы должны поставить Еву перед Анной (оба того же возраста, но в оригинальной последовательности, Ева была до Анны).

Итак, результат:

Emil, 8
Eva, 9
Anna, 9
Phil, 10   \
Hans, 10   | all aged 10, and left in original order.
Jonas, 10  /

Чтобы поставить егов двух словах: Стабильность означает, что если два элемента равны (по выбранному критерию сортировки), то элемент, идущий первым в исходной последовательности, все равно будет первым в результирующей последовательности.

Обратите внимание , что вы можете легко преобразовать любой алгоритм сортировки в стабильный алгоритм сортировки: если ваша исходная последовательность содержит n элементов: e1, e2, e3, ..., en, вы просто прикрепляете счетчик к каждому: (e1, 0), (e2, 1), (e3, 2), ..., (en, n-1).Это означает, что вы сохраняете для каждого элемента его исходное положение.

Если теперь два элемента равны, вы просто сравниваете их счетчики и ставите один с меньшим значением счетчика первым.Это увеличивает время выполнения (и память) на O(n), что асимптотически не ухудшается, поскольку для лучшего алгоритма сортировки (сравнения) уже требуется O(n lg n).

Answer 5

• Heapsort , возможно рандомизированная быстрая сортировка
• стабильная сортировка
• , как уже упоминалось: нетнет.Например, вы можете распараллелить алгоритм сортировки.Это приводит к совершенно другим алгоритмам сортировки ..

Answer 6

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

Конкретный случай проблемы определит, какой алгоритм лучше всего подходит для ваших нужд, т.е. сортировка строк 1M отличается от сортировки 7-битных целых 2M в 2MB оперативной памяти.

Также учтите, что помимо асимптотической сложности времени выполнения, реализация имеет большое значение, а также объем доступной памяти и политики кэширования.

Я мог бы реализовать быструю сортировку в 1 строке в Python, грубо сохранив сложность O (n log n) (с некоторыми оговорками относительно стержня), но нотация Big-Oh ничего не говорит о константах, которые тоже актуальны (т.е. это примерно в 30 раз медленнее, чем встроенная сортировка Python, которая, вероятно, написана на C):

qsort = lambda a: [] if not a else qsort(filter(lambda x: x<a[len(a)/2], a)) + filter(lambda x: x == a[len(a)/2], a) + qsort(filter(lambda x: x>a[len(a)/2], a))

Для обсуждения стабильной / нестабильной сортировки, смотрите здесь http://www.developerfusion.com/article/3824/a-guide-to-sorting/6/.

Возможно, вы захотите получить хорошую книгу об алгоритмах (например, Кормен или Скиена).