Какая сортировка самая быстрая

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

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

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

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

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

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

алгоритмы сортировки 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

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

Какая сортировка самая быстрая? Тестируем алгоритмы, изображение №4

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

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

Алгоритмы сортировки

Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

Виды алгоритмов сортировки

Сортировка пузырьком / Bubble sort

Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.

Сортировка пузырьком, пример

Плюсы и минусы

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

Пример реализации на Kotlin:

Сортировка перемешиванием / Shaker (cocktail, ripple, shuffle, shuttle) sort

Также известна как шейкерная или коктейльная сортировка.

Сортировка перемешиванием — это разновидность сортировки пузырьком. Отличие в том, что данная сортировка в рамках одной итерации проходит по массиву в обоих направлениях (слева направо и справа налево), тогда как сортировка пузырьком — только в одном направлении (слева направо).

Общая идея алгоритма:

Обход массива слева направо, аналогично пузырьковой — сравнение соседних элементов, меняя их местами, если левое значение больше правого. В итоге наибольшее число будет перемещено в конец массива.
Обход массива в обратном направлении (справа налево), начиная с элемента, который находится перед последним отсортированным. На этом этапе элементы также сравниваются между собой и меняются местами, чтобы наименьшее значение всегда было слева. В итоге наименьшее число будет перемещено в начало массива.

Пример реализации на Kotlin:

Сложность у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше (обычно менее чем в два раза быстрее).

Сортировка расчёской / Comb sort

Сортировка расчёской — еще одна разновидность сортировки пузырьком. Данная сортировка улучшает сортировку пузырьком за счет устранения маленьких значений в конце списка (черепах).

Достигается это тем, что вместо сравнения соседних элементов, сравниваются элементы на достаточно большом расстоянии друг от друга, постепенно уменьшая это расстояние. Сначала разрыв между элементами берётся максимальный, т.е. на единицу меньше, чем размер массива. Затем на каждой итерации расстояние уменьшается путём деления расстояния на фактор уменьшения. Так продолжается до тех пор, пока разность индексов сравниваемых элементов не достигнет единицы. Тогда сравниваются уже соседние элементы как и в сортировке пузырьком, но эта итерация будет последней.

Оптимальное значение фактора уменьшения — 1,247.

Пример реализации на Kotlin:

Сортировка вставками / Insertion sort

Сортировка вставками — алгоритм, при котором каждый последующий элемент массива сравнивается с предыдущими элементами (отсортированными) и вставляется в нужную позицию.

Общая идея алгоритма:

Сравниваем второй элемент с первым элементом массива и при необходимости меняем их местами. Условно эти элементы (первый и второй) будут являться отсортированным массивом, остальные элементы — неотсортированным.
Сравниваем следующий элемент из неотсортированного массива с элементами отсортированного и вставляем в нужную позицию.
Повторям шаг 2 до тех пор, пока в неотсортированном массиве не останется элементов.

Пример реализации на Kotlin:

Сортировка Шелла / Shell sort

Сортировка Шелла — усовершенствованная разновидность сортировки вставками.

Сначала сравниваются и сортируются между собой значения, стоящие друг от друга на некотором расстоянии — d. После этого расстояние d уменьшается и процедура повторяется до тех пор, пока значение d не станет минимальным, т.е. d = 1. Это означает, что сортировка достигла последнего шага. А на последнем шага элементы сортируются обычной сортировкой вставками.

Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:

первая итерация — d₁ = N/2, где N — размер массива;
последующие итерации — d_i = d_i-1/2;
последняя итерация — d_k = 1

Существуют и другие последовательности.

Пример реализации на Kotlin:

Сортировка выбором / Selection Sort

Сортировка выбором — это алгоритм, при котором многократно осуществляется поиск минимального элемента в неотсортированной части массива и его помещение в конец отсортированной части массива.

Общая идея алгоритма:

Данный алгоритм условно делит массив на две части:
- подмассив, который уже отсортирован (находится в левой части массива),
- подмассив, который нужно отсортировать (находится в правой части массива).
Пример реализации на Kotlin:

Быстрая сортировка / Quick Sort

Быстрая сортировка — это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:
- Выбрать из массива элемент, который обычно называют опорным. Это может быть любой элемент из массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность.
- Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».
- Рекурсивно применить первые два шага к отрезкам, содержащим «меньшие» и «большие» значения. Не применять к массиву, в котором только один элемент или отсутствуют элементы.
Пример реализации на Kotlin:

Сортировка слиянием / Merge sort

Сортировка слиянием — это алгоритм типа “разделяй и властвуй”.

Общая идея алгоритма:
- Массив разбивается на две части примерно одинакового размера. Разбиение получившихся массивов повторяется до тех пор, пока размер каждого массива не достигнет единицы.
- Каждая из получившихся частей сортируется отдельно, после чего происходит слияние двух массивов следующим образом:
  - На каждом шаге сравниваем первые элементы массивов, берём наименьшее значение и записываем в результирующий массив.
  - Когда один из массив закончился, добавляем оставшиеся элементы второго массива в результирующий массив.
  Пример реализации на Kotlin:
  
  Пирамидальная сортировка / Heap sort
  
  Пирамидальная сортировка — это улучшенная сортировка выбором.
  
  Для сортировки используется бинарное сортирующее дерево — дерево, у которого выполнены условия:
  - Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
  - Значение в любой вершине не меньше значения её потомков.
  Общая идея алгоритма:
  - Выстраиваем массив в виде сортирующего дерева:
    Array[i] >= Array[2i + 1]
    Array[i] >= Array[2i + 2]
    при 0 <= i < n/2
  - Обмениваем элементы Array[0] и Array[n-1] местами. Array[0] является корнем сортирующего дерева, т.е. самым большим значением массива.
  - Повторям шаги до тех пор, пока в сортирующем дереве не останется один элемент.
  Пример реализации на Kotlin:
  
  Сортировка подсчётом / Counting sort
  
  Сортировка подсчётом — это алгоритм, основанный на подсчёте повторяющихся элементов в массиве.
  
  Общая идея алгоритма (простой вариант):
  - Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями.
  - Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C — это значения массива A, а значение в массиве C — это то, сколько раз это число повторяется в массиве A.
  - Проходим по массиву C и переносим значения в массив A.
  Пример реализации на Kotlin:
  - n — размер отсортированного массива, а k — размер вспомогательного массива
  Блочная (карманная, корзинная) сортировка / Bucket sort
  
  Блочная сортировка — это алгоритм, основанный на разделении входного массива на несколько частей — блоки/сегменты — и использовании другого алгоритма для их сортировки.
  
  Общая идея алгоритма:
  - Делим массив на блоки таким образом, чтобы элементы в каждом следующем блоке были всегда больше, чем в предыдущем.
  - Сортируем каждый блок, используя какой-либо другой алгоритм сортировки, либо рекурсивно тем же методом разбиения на блоки.
  - Объединяем все блоки в один массив.
  Пример реализации на Kotlin:
  - k — количество блоков.
  Поразрядная (цифровая) сортировка / Radix sort
  
  Поразрядная сортировка — это алгоритм, который использует внутреннюю структуру сортируемых объектов.
  
  Перед началом сортировки необходимо знать:
  - length — максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове);
  - rang количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).
  Общая идея алгоритма:
  - Создаём пустые массивы, количество которых равно rang.
  - Распределяем исходные значения по этим массивам. Распределение осуществляется по значению младшего (крайнего) разряда.
  - Соединяем значения в той последовательности, в которой они находятся после распределения по спискам.
  - Повторяем шаги 1-2 для оставшихся разрядов.
  Пример реализации на Kotlin:
  - w — количество бит, требуемых для хранения каждого ключа.
  Битонная сортировка / Bitonic sort
  
  Битонная сортировка — алгоритм, основанный на понятии битонных последовательностей и операций над ними.
  
  Битонная последовательность — последовательность, которая сначала возрастает, а потом убывает.
  
  Общая идея алгоритма:
  - Создаём битонную последовательность. В результате получаем два массива: первый отсортирован в порядке возрастания, второй — в порядке убывания.
  - Последовательно сравниваем элементы первого и второго массивов (сначала первые элементы, потом вторые и т.д.). Если какой либо элемент из второго массива окажется меньше, то меняем его местами с элементом из первого массива. В результате в первом массиве окажутся наименьшие элементы из обоих массивов, а во втором — наибольшие. При этом каждый из массивов будет являться битонной последовательностью.
  - Рекурсивно применяем второй шаг к отсортированным массивам, после чего массивы можно склеить.
  Чтобы превратить произвольную последовательность в битонную, нужно:
  - разделить последовательность пополам;
  - первую часть отсортировать по возрастанию;
  - вторую часть отсортировать по убыванию.
  Пример реализации на Kotlin:
  
  Timsort
  
  Timsort — гибридный алгоритм, сочетающий в себе сортировку вставками и сортировку слиянием.
  
  Наилучший способ сортировки массива.
  
  Какой способ является самым лучшим и по вашему мнению и почему? Есть ли способы быстрее способа, основанного на алгоритме «быстрой сортировки»? Если да, то будьте добры рассказать, где можно о нем почитать.
  - Лучшего способа нет, если говорить о "разумных" алгоритмах и не учитывать эзотерику типа Bogosort или Intelligent Design Sort.
  - Стандартные операции sort в современных языках обычно используют разные алгоритмы в зависимости от размера входных данных. То есть, на маленьких размерах массивов O(N^2) сортировка вставками часто оказывается более эффективной, чем, например, O(N log N) быстрая сортировка.
  - Естественно, что для больших размеров выбирается сортировка с O(N log N) временем работы.
  - Можно строго доказать, что, если S — алгоритм сортировки, основанный на построении дерева решений, то O(N log N) — это минимальное возможное время работы алгоритма S в худшем его случае. А это означает, что все алгоритмы типа quicksort , mergesort , сортировки вставками и т.п. не могут работать за время, меньшее, чем O(N log N) .
  Тем не менее, есть сортировки, которые не используют деревья решений и работают за линейное время при некоторых ограничениях. Например, поразрядная сортировка.
  - Из литературы — Cormen, Introduction To Algorithms.
  я просто оставлю это здесь
  
  @Котик_хочет_кушать правильно сказал, что лучшего способа нет.
  
  Из почти всегда применимых алгоритмов quicksort IMHO самый быстрый (время O(N*log N)), хотя (даже правильно реализованый) изредка (на практике очень редко) может привести к времени порядка O(N^2). Он требует log N дополнительной памяти, т.е. на практике можете считать, что не требует. Основной недостаток quicksort — это неустойчивый (unstable) алгоритм.
  
  Сортировка называется устойчивой, если порядок записей с одинаковыми ключами после сортировки сохраняется. Очевидно, что если Вы сортируете массив чисел, то устойчивость алгоритма неважна (одно число 10 от другого 10 неотличимо). Для сортровки записей (структур) это не так (хотя зависит от прикладной задачи).
  
  Из устойчивых сортировок (я рассматриваю алгоритмы со временем O(N*log N)) IMHO самым быстрым является сортировка слиянием (mergesort) в ее почти простейшей реализации, требующий N/2 дополнительной памяти.
  
  Похожие результаты (иногда м.б. даже быстрее, но обычно медленнее) показывает timsort (это тоже разновидность сортировки слиянием). Обычно она требует 30-40% N дополнительной памяти.
  
  Также (пользуясь случаем) хочу обратить внимание на yamsort. Еще один алгоритм и программа устойчивой (stable) сортировки слиянием c небольшой (около 6 % от размера сортируемого массива) дополнительной памятью. Он несколько медленнее timsort, но при сортировке очень больших массивов (особенно в многопользовательских системах), когда дополниетельная память вызывает paging, это алгоритм оказывается значительно быстрее других устойчивых сортировок.
  Похожие публикации:

Какая сортировка самая быстрая