Какая сортировка самая быстрая? Тестируем алгоритмы
На собеседованиях часто спрашивают, какая сортировка самая быстрая. Вопрос с подвохом. Объясняем, почему, и ищем оптимальный вариант.
В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.
В одной из наших статей мы уже разобрали различные типы сортировок. Теперь давайте проанализируем их и некоторые другие алгоритмы подробнее.
Временная сложность алгоритма
Грубо говоря, это время работы, используемое алгоритмом. Существует теория алгоритмов как отдельная дисциплина, и для полного погружения в вопрос рекомендуется прочесть третий том «Искусства программирования», который так и называется: «Сортировка и поиск».
Существуют:
- алгоритмы сортировки O(n2) вроде сортировки вставками, пузырьком и выбором, которые используются в особых случаях;
- быстрая сортировка (общего назначения): в среднем O(n log n) обменов, но худшее время – O(n2), если массив уже отсортирован, или элементы равны;
- алгоритмы O(n log n), такие как сортировка слиянием и кучей (пирамидальная сортировка), которые также являются хорошими алгоритмами сортировки общего назначения;
- O(n) или линейные алгоритмы сортировки (выбор, выбор с обменом, выбор с подсчетом) для списков целых чисел, которые могут быть подходящими в зависимости от характера целых чисел в ваших списках.
Если все, что вы знаете, – это отношение общего порядка между элементами, то оптимальные алгоритмы будут иметь сложность О(n log n). Для линейных алгоритмов нужна дополнительная информация о структуре элементов.
Оптимальность алгоритма тесно зависит от типа списков/массивов, которые вы собираетесь сортировать, и даже от модели ЭВМ. Чем больше информации в вашем распоряжении, тем более точным будет выбор. При очень слабых предположениях о факторах оптимальной сложностью худшего случая может быть О(n!).
Данный ответ касается только сложностей. Фактическое время выполнения алгоритмов зависит от огромного количества факторов.
Тестирование
Итак, какая же сортировка самая быстрая?
В одной из статей автор анализирует практически все известные виды сортировок. Он поделил тесты на 4 группы:
- Массив случайных чисел (10, 1000, 105, 107 и 109).
- Массив (109), который разбивается на отсортированные подмассивы (размер, равный min из длины оставшегося суффикса и случайного числа по модулю константы (10, 100 и т. д. до размера массива)).
- Отсортированный массив с некоторым числом перестановок 2-х случайных элементов.
- Тесты с отсортированным в прямом и обратном порядках массивом, тесты с массивом натуральных чисел в интервале 1-n, где несколько чисел заменены на случайные, а также тесты с уймой (10, 25, 50, 75 и 90 процентов) повторений элемента.
Итоговые результаты каждой группы тестов:
1.
Сортировка вставками обошла остальные типы, в т. ч. сортировку выбором.
2.
Лучшие результаты показала сортировка Шелла по Хиббарду.
3.
Поразрядная сортировка (LSD-версия) оказалась лучшей для 107 и 108 элементов, но вот в работе с перестановками она не очень хороша.
Четвертая группа составлена таким образом, чтобы изменить правила для алгоритмов, которым «нравятся» последовательности случайных чисел. Вот файл, в котором подробно описаны все тесты. Код проекта лежит здесь.
Визуализация
Неплохая визуализация сортировок продемонстрирована в этом видео:
https://www.youtube.com/watch?v=BeoCbJPuvSE
Кажется, что она отвечает на вопрос о том, какая сортировка самая быстрая, но не стоит забывать, что на скорость влияет множество факторов, и это лишь один из продемонстрированных вариантов.