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

1
12737
Добавить в избранное

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

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

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

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

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

Существуют:

  • алгоритмы сортировки 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 элементов, но вот в работе с перестановками она не очень хороша.

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

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

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

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

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

Интересуетесь алгоритмами?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




1 комментарий

Оставьте комментарий