Какой использовать алгоритм сортировки, если требуется сложность не более O(n) и максимальная производительность?

Question

[Alexey Sh]

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

Answer 1

[Ocelot]

Если возраст целочисленный, хорошо подходит cортировка подсчетом. Как раз за O(n).

Comments

[Alexey Sh]

А насчет TimSort, что думаете?

[sim3x]

от О(2n) до О(n^2)

[MiiNiPaa]

Да ничего не думаем. Обобщённые алгоритмы сортировки не могут работать быстрее O(n logn) в принципе.
Для более быстрой работы необходимо использовать специфические свойства сортируемых элементов. Сортировка подсчётом работает очень хорошо когда множество элементов ограничено (возраста более 150 быть не может)

[Ocelot]

Тимсорт в лучшем случае даст сложность O(n log(n)), а в худшем - O(n²). Не годится.

[Alexey Sh]

Ребят, всем большое спасибо. Сейчас буду курить как работает сортировка подсчетом

Answer 2

[bromzh]

Во-первых, есть строгое доказательство, что сортировка произвольного массива не может быть выполнена быстрее, чем за O(n*log(n)) операций (log тут по основанию 2).
Во-вторых, у сортировок есть много параметров: время в лучшем/худшем/среднем случае, доп. память, стабильность.
QuickSort имеет время O(n log n) в среднем и лучшем, а в худшем - за O(n^2). Ещё она нестабильная и требует O(n) памяти. В обычных условиях это устраивает, но худший случай в ней - её слабое место.
Есть модификации быстрой сортировки, позволяющие уменьшить время худшего случая до O(n log n).
В языках программирования встроенные сортировки - это обычно либо быстрая сортировка с улучшениями, либо какая-нибудь стабильная сортировка, какой-нибудь merge sort.

Так что либо бери родную, либо пиши сам. Самая простая модификация быстрой сортировки, при которой худшее время станет O(n log n) - это сделать случайный выбор опорного элемента.

Ну и читай https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

Comments

[h8nor]

Что можете сказать о сортировке методом Шелла Дональда с интервалами длин Марцина Циура?
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

[stas8]

> log тут по основанию 2

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

[Виталий Витренко]

Все выше описано верно лишь для сортировок на основе сравнений.

Answer 3

[LittleFatNinja]

нету сортировки о(n)
макс o(n logN)

Comments

[Alexey Sh]

Я честно говоря не очень в алгоритмах, поэтому и задал вопрос, буду иметь в виду, видел что можно надеяться на такую сложность в TimSort

[Ocelot]

Максимум o(n logN) - для сортировок, основанных только на сравнениях. Если снять это ограничение, можно в некоторых случаях получить линейное время.

Answer 4

[Don Kaban]

Возраст в годах - диапазон, скажем 120 лет. 8 бит. Гистограмма. O(n), точнее просто N :)
Массив на 120 элементов, один проход, вывод.

Answer 5

[mikhail_404]

В задаче указано важное условие, что будет сортироваться возраст людей, т.е. это диапазон от 1900 - 2015 при очень грубой оценке. Отсортировать МОЖНО за линию (O(N)), используя сортировку подсчетом или поразрадную сортировку.

Answer 6

[Odissey Nemo]

Сортировка слиянием отсортирует любой объём данных, помещающихся на жёстком или ином диске.