bondpuoq
@bondpuoq
Web-программист с недавних пор

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

Имеется задание, написать алгоритм сортировки, который принимает в качестве параметра массив большой компании (т.е. большой массив), содержащий возраст (в годах) обычных людей. Не очень силен в сортировках и алгоритмах, но сказали, что QuickSort не лучшее решение.
  • Вопрос задан
  • 1078 просмотров
Решения вопроса 1
Ocelot
@Ocelot
Если возраст целочисленный, хорошо подходит cортировка подсчетом. Как раз за O(n).
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
@bromzh
Drugs-driven development
Во-первых, есть строгое доказательство, что сортировка произвольного массива не может быть выполнена быстрее, чем за 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...
Ответ написан
LittleFatNinja
@LittleFatNinja
горе девелопер, любитель лютой садомии
нету сортировки о(n)
макс o(n logN)
Ответ написан
donkaban
@donkaban
Умею рисовать тени
Возраст в годах - диапазон, скажем 120 лет. 8 бит. Гистограмма. O(n), точнее просто N :)
Массив на 120 элементов, один проход, вывод.
Ответ написан
Комментировать
@mikhail_404
В задаче указано важное условие, что будет сортироваться возраст людей, т.е. это диапазон от 1900 - 2015 при очень грубой оценке. Отсортировать МОЖНО за линию (O(N)), используя сортировку подсчетом или поразрадную сортировку.
Ответ написан
Комментировать
@odissey_nemo
Программист, ГИС-системы, растры, космоснимки
Сортировка слиянием отсортирует любой объём данных, помещающихся на жёстком или ином диске.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы