Я сталкивался со многими алгоритмами сортировки во время учебы в старшей школе. Тем не менее, я никогда не знаю, какой самый быстрый (для случайного массива целых чисел). Итак, мои вопросы:
- Какой самый быстрый в настоящее время известный алгоритм сортировки?
- Теоретически, возможно, что есть еще более быстрые? Итак, какая наименьшая сложность для сортировки?
algorithms
time-complexity
optimization
sorting
поколения
источник
источник
Ответы:
В общих чертах, существуют алгоритмы сортировки , такие как сортировка по вставкам, сортировка по пузырькам и сортировка по выбору, которые обычно следует использовать только в особых случаях; Быстрая сортировка, которая является наихудшим вариантом O ( n 2 ), но довольно часто O ( n log n ) с хорошими константами и свойствами и которая может использоваться в качестве процедуры сортировки общего назначения; О ( п войти п ) алгоритмы, как слияния сортировки и куча сортировку, которые также являются хорошими алгоритмами общего назначения сортировки; и О ( нO ( n2) O ( n2) O ( n logн ) O ( n logн ) , или линейные алгоритмы сортировки для списков целых чисел, таких как основание, ведро и счетные сортировки, которые могут быть подходящими в зависимости от природы целых чисел в ваших списках.O ( n )
Если элементы в вашем списке таковы, что все, что вы о них знаете, это отношение общего порядка между ними, то оптимальные алгоритмы сортировки будут иметь сложность . Это довольно крутой результат, и вы легко сможете найти подробности в Интернете. Алгоритмы линейной сортировки используют дополнительную информацию о структуре сортируемых элементов, а не только общее отношение порядка между элементами.Ω ( n logн )
В более общем смысле, оптимальность алгоритма сортировки тесно связана с предположениями, которые вы можете сделать относительно типа списков, которые вы собираетесь сортировать (а также с моделью машины, на которой будет работать алгоритм, что может сделать даже плохую сортировку в противном случае). Алгоритмы лучший выбор, рассмотрите пузырьковую сортировку на машинах с лентой для хранения). Чем сильнее ваши предположения, тем больше углов может сократить ваш алгоритм. При очень слабых предположениях о том, насколько эффективно вы можете определить «сортировку» списка, оптимальной сложностью в худшем случае может быть даже .Ω ( n ! )
Этот ответ имеет дело только со сложностями. Фактическое время выполнения реализаций алгоритмов будет зависеть от большого числа факторов, которые трудно учесть в одном ответе.
источник
Ответ, как это часто бывает на такие вопросы, - «это зависит». Это зависит от таких вещей, как (а) насколько велики целые числа, (б) содержит ли входной массив целые числа в случайном или почти отсортированном порядке, (в) нужен ли алгоритм сортировки, чтобы быть устойчивым, или нет, а также другие факторы: (d) помещается ли весь список чисел в памяти (сортировка в памяти по сравнению с внешней сортировкой), и (e) машина, на которой вы его запускаете.
На практике алгоритм сортировки в стандартной библиотеке вашего языка, вероятно, будет довольно хорошим (довольно близким к оптимальному), если вам нужна сортировка в памяти. Поэтому на практике просто используйте любую функцию сортировки, предоставляемую стандартной библиотекой, и измерьте время выполнения. Только если вы обнаружите, что (i) сортировка составляет большую часть общего времени выполнения, и (ii) время выполнения недопустимо, вы должны возиться с алгоритмом сортировки. Если эти два условия делают захват, то вы можете посмотреть на конкретных аспектах вашей конкретной области и эксперимента с другими быстро алгоритмами сортировки.
Но реально, на практике алгоритм сортировки редко является серьезным узким местом производительности.
источник
Кроме того, отвечая на ваш второй вопрос
Для сортировки общего назначения сложность задачи сортировки на основе сравнения составляет Ω (n log n) . Есть некоторые алгоритмы, которые выполняют сортировку в O (n), но все они основаны на предположениях относительно входных данных и не являются алгоритмами сортировки общего назначения.
По существу, сложность определяется минимальным количеством сравнений, необходимых для сортировки массива (log n представляет максимальную высоту двоичного дерева решений, построенного при сравнении каждого элемента массива).
Вы можете найти формальное доказательство для нижней границы сложности сортировки здесь :
источник
Самым быстрым алгоритмом целочисленной сортировки с точки зрения наихудшего случая, с которым я сталкивался, является Andersson et al. У него наихудший случай , что, конечно, быстрее, чем O ( n log n ) .O ( n logжурналн ) O ( n logн )
источник
Я прочитал два других ответа во время написания этого, и я не думаю, что кто-то ответил на ваш вопрос должным образом. Другие ответы рассматривали посторонние идеи о случайных распределениях и сложности пространства, которые, вероятно, выходят за рамки изучения в старших классах. Итак, вот мое взятие.
источник
источник
источник
Поскольку вы не упоминаете никаких ограничений на оборудование и, учитывая, что ищете «самый быстрый», я бы сказал, что вам следует выбрать один из алгоритмов параллельной сортировки, основанный на доступном оборудовании и типе входных данных, которые у вас есть.
В теории, например,
quick_sort
естьO(n log n)
. Сp
процессорами в идеале это должно сводиться к тому,O(n/p log n)
чтобы мы запускали его параллельно.Процитирую Википедию: временная сложность ...
На практике для больших размеров входных данных это было бы невозможно достичь
O(log n)
из-за проблем с масштабируемостью.Вот псевдокод для параллельной сортировки слиянием . Реализация
merge()
может быть такой же, как в обычной сортировке слиянием:Также см:
источник