Какая сортировка самая быстрая? Тестируем алгоритмы

На собеседованиях часто спрашивают, какая сортировка самая быстрая. Вопрос с подвохом. Объясняем, почему, и ищем оптимальный вариант.

В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.

В одной из наших статей мы уже разобрали различные типы сортировок. Теперь давайте проанализируем их и некоторые другие алгоритмы подробнее.

Временная сложность алгоритма

Грубо говоря, это время работы, используемое алгоритмом. Существует теория алгоритмов как отдельная дисциплина, и для полного погружения в вопрос рекомендуется прочесть третий том «Искусства программирования», который так и называется: «Сортировка и поиск».

Существуют:

  • алгоритмы сортировки O(n2) вроде сортировки вставками, пузырьком и выбором, которые используются в особых случаях;
  • быстрая сортировка (общего назначения): в среднем O(n log n) обменов, но худшее время – O(n2), если массив уже отсортирован, или элементы равны;
  • алгоритмы O(n log n), такие как сортировка слиянием и кучей (пирамидальная сортировка), которые также являются хорошими алгоритмами сортировки общего назначения;
  • O(n) или линейные алгоритмы сортировки (выбор, выбор с обменом, выбор с подсчетом) для списков целых чисел, которые могут быть подходящими в зависимости от характера целых чисел в ваших списках.

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

Оптимальность алгоритма тесно зависит от типа списков/массивов, которые вы собираетесь сортировать, и даже от модели ЭВМ. Чем больше информации в вашем распоряжении, тем более точным будет выбор. При очень слабых предположениях о факторах оптимальной сложностью худшего случая может быть О(n!).

Данный ответ касается только сложностей. Фактическое время выполнения алгоритмов зависит от огромного количества факторов.

Тестирование

Итак, какая же сортировка самая быстрая?

В одной из статей автор анализирует практически все известные виды сортировок. Он поделил тесты на 4 группы:

  1. Массив случайных чисел (10, 1000, 105, 107 и 109).
  2. Массив (109), который разбивается на отсортированные подмассивы (размер, равный min из длины оставшегося суффикса и случайного числа по модулю константы (10, 100 и т. д. до размера массива)).
  3. Отсортированный массив с некоторым числом перестановок 2-х случайных элементов.
  4. Тесты с отсортированным в прямом и обратном порядках массивом, тесты с массивом натуральных чисел в интервале 1-n, где несколько чисел заменены на случайные, а также тесты с уймой (10, 25, 50, 75 и 90 процентов) повторений элемента.

Итоговые результаты каждой группы тестов:

1.

Сортировка вставками обошла остальные типы, в т. ч. сортировку выбором.

2.

Лучшие результаты показала сортировка Шелла по Хиббарду.

3.

Поразрядная сортировка (LSD-версия) оказалась лучшей для 107 и 108 элементов, но вот в работе с перестановками она не очень хороша.

Четвертая группа составлена таким образом, чтобы изменить правила для алгоритмов, которым «нравятся» последовательности случайных чисел. Вот файл, в котором подробно описаны все тесты. Код проекта лежит здесь.

Визуализация

Неплохая визуализация сортировок продемонстрирована в этом видео:

https://www.youtube.com/watch?v=BeoCbJPuvSE

Кажется, что она отвечает на вопрос о том, какая сортировка самая быстрая, но не стоит забывать, что на скорость влияет множество факторов, и это лишь один из продемонстрированных вариантов.

Вас также могут заинтересовать другие статьи по теме:

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

admin
21 февраля 2017

Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

Данная статья содержит не только самые распространенные алгоритмы и структу...
admin
29 января 2017

Изучаем алгоритмы: полезные книги, веб-сайты, онлайн-курсы и видеоматериалы

В этой подборке представлен список книг, веб-сайтов и онлайн-курсов, дающих...