Встроенная сортировка, в каких случаях можно её обогнать?
Возможно вопрос простой, но никакого ответа найти не смог.
По проекту сравнения сортировок, есть дополнительный вопрос:
"В каких случаях можно обогнать встроенную в язык сортировку?"
Тестировал массивы, случайные, частично-упорядоченные, частично-отсортированные, но встроенная PHP сортировка оказывается быстрее всех, она вроде бы основана на Quicksort, но работает уж больно быстрее.
Ответы (2 шт):
При некоторых ограничениях можно сортировать массив с линейной сложностью. Как пример можно привести сортировку подсчётом или поразрядную сортировка. Такая сортировка может работать быстрее, чем быстрая сортировка, которая имеет линейно-логарифмическую сложность.
Ещё надо понимать, что встроенные в язык функции могут использовать оптимизации, недоступные из самого языка. Особенно это может быть заметно в интерпретируемых языках программирования, каким является PHP.
Я в PHP не компетентен, но об алгоритмах (в С++) могу и поговорить :)
Так вот, конечно, сложность алгоритма важна, кто бы спорил... но есть еще такая вещь, как константа в этой самой сложности. И самым простым примером является сортировка вставками - которая при O(n2) отлично работает на почти упорядоченных массивах. Стандартный алгоритм - по крайней мере в ряде реализаций - прибегает к нему уже в самом конце той же быстрой сортировки. Если же знать ситуацию заранее - можно сразу к нему прибегнуть.
У меня на искусственном почти упорядоченном массиве из миллиона элементов получилось
стандартная сортировка ~ 101 ms
сортировка вставками ~ 0,9 ms
(Visual C++ 2017 64x)
Весь код - https://rextester.com/NFCBWN86771, тут разница не такая разительная, в 2 раза, а не на 2 порядка, но все равно InsertionSort обгоняет.
Так что ответ - "в некоторых частных случаях" :)
Как вот этот...