Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.
Виды алгоритмов сортировки
Сортировка пузырьком / 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. Это означает, что сортировка достигла последнего шага. А на последнем шага элементы сортируются обычной сортировкой вставками.
Первоначально было предложено расчитывать расстояние между сравниваемыми элементами следующим образом:
- первая итерация — d1 = N/2, где N — размер массива;
- последующие итерации — di = di-1/2;
- последняя итерация — dk = 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, это алгоритм оказывается значительно быстрее других устойчивых сортировок.
Описание алгоритмов сортировки и сравнение их производительности
На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.
Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Описание основных сортировок и их реализация
Я постараюсь кратко и понятно описать сортировки и указать асимптотику, хотя последнее в рамках данной статьи не очень важно (интересно же узнать реальное время работы). О потреблении памяти в дальнейшем ничего писать не буду, замечу только, что сортировки, использующие непростые структуры данных (как, например, сортировка деревом), обычно потребляют ее в больших количествах, а остальные сортировки в худшем случае только создают вспомогательный массив. Также существует понятие стабильности (устойчивости) сортировки. Это значит, что относительный порядок элементов при их равенстве не меняется. Это тоже в рамках данной статьи неважно (в конце концов, можно просто прицепить к элементу его индекс), однако в одном месте пригодится.
Сортировка пузырьком / Bubble sort
Будем идти по массиву слева направо. Если текущий элемент больше следующего, меняем их местами. Делаем так, пока массив не будет отсортирован. Заметим, что после первой итерации самый большой элемент будет находиться в конце массива, на правильном месте. После двух итераций на правильном месте будут стоять два наибольших элемента, и так далее. Очевидно, не более чем после n итераций массив будет отсортирован. Таким образом, асимптотика в худшем и среднем случае – O(n 2 ), в лучшем случае – O(n).
Шейкерная сортировка / Shaker sort
(также известна как сортировка перемешиванием и коктейльная сортировка). Заметим, что сортировка пузырьком работает медленно на тестах, в которых маленькие элементы стоят в конце (их еще называют «черепахами»). Такой элемент на каждом шаге алгоритма будет сдвигаться всего на одну позицию влево. Поэтому будем идти не только слева направо, но и справа налево. Будем поддерживать два указателя begin и end, обозначающих, какой отрезок массива еще не отсортирован. На очередной итерации при достижении end вычитаем из него единицу и движемся справа налево, аналогично, при достижении begin прибавляем единицу и двигаемся слева направо. Асимптотика у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше.
Сортировка расческой / Comb sort
Еще одна модификация сортировки пузырьком. Для того, чтобы избавиться от «черепах», будем переставлять элементы, стоящие на расстоянии. Зафиксируем его и будем идти слева направо, сравнивая элементы, стоящие на этом расстоянии, переставляя их, если необходимо. Очевидно, это позволит «черепахам» быстро добраться в начало массива. Оптимально изначально взять расстояние равным длине массива, а далее делить его на некоторый коэффициент, равный примерно 1.247. Когда расстояние станет равно единице, выполняется сортировка пузырьком. В лучшем случае асимптотика равна O(nlogn), в худшем – O(n 2 ). Какая асимптотика в среднем мне не очень понятно, на практике похоже на O(nlogn).
Об этих сортировках (пузырьком, шейкерной и расческой) также можно почитать здесь.
Сортировка вставками / Insertion sort
Создадим массив, в котором после завершения алгоритма будет лежать ответ. Будем поочередно вставлять элементы из исходного массива так, чтобы элементы в массиве-ответе всегда были отсортированы. Асимптотика в среднем и худшем случае – O(n 2 ), в лучшем – O(n). Реализовывать алгоритм удобнее по-другому (создавать новый массив и реально что-то вставлять в него относительно сложно): просто сделаем так, чтобы отсортирован был некоторый префикс исходного массива, вместо вставки будем менять текущий элемент с предыдущим, пока они стоят в неправильном порядке.
Сортировка Шелла / Shellsort
Используем ту же идею, что и сортировка с расческой, и применим к сортировке вставками. Зафиксируем некоторое расстояние. Тогда элементы массива разобьются на классы – в один класс попадают элементы, расстояние между которыми кратно зафиксированному расстоянию. Отсортируем сортировкой вставками каждый класс. В отличие от сортировки расческой, неизвестен оптимальный набор расстояний. Существует довольно много последовательностей с разными оценками. Последовательность Шелла – первый элемент равен длине массива, каждый следующий вдвое меньше предыдущего. Асимптотика в худшем случае – O(n 2 ). Последовательность Хиббарда – 2 n — 1, асимптотика в худшем случае – O(n 1,5 ), последовательность Седжвика (формула нетривиальна, можете ее посмотреть по ссылке ниже) — O(n 4/3 ), Пратта (все произведения степеней двойки и тройки) — O(nlog 2 n). Отмечу, что все эти последовательности нужно рассчитать только до размера массива и запускать от большего от меньшему (иначе получится просто сортировка вставками). Также я провел дополнительное исследование и протестировал разные последовательности вида si = a * si — 1 + k * si — 1 (отчасти это было навеяно эмпирической последовательностью Циура – одной из лучших последовательностей расстояний для небольшого количества элементов). Наилучшими оказались последовательности с коэффициентами a = 3, k = 1/3; a = 4, k = 1/4 и a = 4, k = -1/5.
Несколько полезных ссылок:
Сортировка деревом / Tree sort
Будем вставлять элементы в двоичное дерево поиска. После того, как все элементы вставлены достаточно обойти дерево в глубину и получить отсортированный массив. Если использовать сбалансированное дерево, например красно-черное, асимптотика будет равна O(nlogn) в худшем, среднем и лучшем случае. В реализации использован контейнер multiset.
Здесь можно почитать про деревья поиска:
Гномья сортировка / Gnome sort
Алгоритм похож на сортировку вставками. Поддерживаем указатель на текущий элемент, если он больше предыдущего или он первый — смещаем указатель на позицию вправо, иначе меняем текущий и предыдущий элементы местами и смещаемся влево.
Сортировка выбором / Selection sort
На очередной итерации будем находить минимум в массиве после текущего элемента и менять его с ним, если надо. Таким образом, после i-ой итерации первые i элементов будут стоять на своих местах. Асимптотика: O(n 2 ) в лучшем, среднем и худшем случае. Нужно отметить, что эту сортировку можно реализовать двумя способами – сохраняя минимум и его индекс или просто переставляя текущий элемент с рассматриваемым, если они стоят в неправильном порядке. Первый способ оказался немного быстрее, поэтому он и реализован.
Пирамидальная сортировка / Heapsort
Развитие идеи сортировки выбором. Воспользуемся структурой данных «куча» (или «пирамида», откуда и название алгоритма). Она позволяет получать минимум за O(1), добавляя элементы и извлекая минимум за O(logn). Таким образом, асимптотика O(nlogn) в худшем, среднем и лучшем случае. Реализовывал кучу я сам, хотя в С++ и есть контейнер priority_queue, поскольку этот контейнер довольно медленный.
Почитать про кучу можно здесь:
Быстрая сортировка / Quicksort
Выберем некоторый опорный элемент. После этого перекинем все элементы, меньшие его, налево, а большие – направо. Рекурсивно вызовемся от каждой из частей. В итоге получим отсортированный массив, так как каждый элемент меньше опорного стоял раньше каждого большего опорного. Асимптотика: O(nlogn) в среднем и лучшем случае, O(n 2 ). Наихудшая оценка достигается при неудачном выборе опорного элемента. Моя реализация этого алгоритма совершенно стандартна, идем одновременно слева и справа, находим пару элементов, таких, что левый элемент больше опорного, а правый меньше, и меняем их местами. Помимо чистой быстрой сортировки, участвовала в сравнении и сортировка, переходящая при малом количестве элементов на сортировку вставками. Константа подобрана тестированием, а сортировка вставками — наилучшая сортировка, подходящая для этой задачи (хотя не стоит из-за этого думать, что она самая быстрая из квадратичных).
Сортировка слиянием / Merge sort
Сортировка, основанная на парадигме «разделяй и властвуй». Разделим массив пополам, рекурсивно отсортируем части, после чего выполним процедуру слияния: поддерживаем два указателя, один на текущий элемент первой части, второй – на текущий элемент второй части. Из этих двух элементов выбираем минимальный, вставляем в ответ и сдвигаем указатель, соответствующий минимуму. Слияние работает за O(n), уровней всего logn, поэтому асимптотика O(nlogn). Эффективно заранее создать временный массив и передать его в качестве аргумента функции. Эта сортировка рекурсивна, как и быстрая, а потому возможен переход на квадратичную при небольшом числе элементов.
Сортировка подсчетом / Counting sort
Создадим массив размера r – l, где l – минимальный, а r – максимальный элемент массива. После этого пройдем по массиву и подсчитаем количество вхождений каждого элемента. Теперь можно пройти по массиву значений и выписать каждое число столько раз, сколько нужно. Асимптотика – O(n + r — l). Можно модифицировать этот алгоритм, чтобы он стал стабильным: для этого определим место, где должно стоять очередное число (это просто префиксные суммы в массиве значений) и будем идти по исходному массиву слева направо, ставя элемент на правильное место и увеличивая позицию на 1. Эта сортировка не тестировалась, поскольку большинство тестов содержало достаточно большие числа, не позволяющие создать массив требуемого размера. Однако она, тем не менее, пригодилась.
Блочная сортировка / Bucket sort
(также известна как корзинная и карманная сортировка). Пусть l – минимальный, а r – максимальный элемент массива. Разобьем элементы на блоки, в первом будут элементы от l до l + k, во втором – от l + k до l + 2k и т.д., где k = (r – l) / количество блоков. В общем-то, если количество блоков равно двум, то данный алгоритм превращается в разновидность быстрой сортировки. Асимптотика этого алгоритма неясна, время работы зависит и от входных данных, и от количества блоков. Утверждается, что на удачных данных время работы линейно. Реализация этого алгоритма оказалась одной из самых трудных задач. Можно сделать это так: просто создавать новые массивы, рекурсивно их сортировать и склеивать. Однако такой подход все же довольно медленный и меня не устроил. В эффективной реализации используется несколько идей:
1) Не будем создавать новых массивов. Для этого воспользуемся техникой сортировки подсчетом – подсчитаем количество элементов в каждом блоке, префиксные суммы и, таким образом, позицию каждого элемента в массиве.
2) Не будем запускаться из пустых блоков. Занесем индексы непустых блоков в отдельный массив и запустимся только от них.
3) Проверим, отсортирован ли массив. Это не ухудшит время работы, так как все равно нужно сделать проход с целью нахождения минимума и максимума, однако позволит алгоритму ускориться на частично отсортированных данных, ведь элементы вставляются в новые блоки в том же порядке, что и в исходном массиве.
4) Поскольку алгоритм получился довольно громоздким, при небольшом количестве элементов он крайне неэффективен. До такой степени, что переход на сортировку вставками ускоряет работу примерно в 10 раз.
Осталось только понять, какое количество блоков нужно выбрать. На рандомизированных тестах мне удалось получить следующую оценку: 1500 блоков для 10 7 элементов и 3000 для 10 8 . Подобрать формулу не удалось – время работы ухудшалось в несколько раз.
Поразрядная сортировка / Radix sort
(также известна как цифровая сортировка). Существует две версии этой сортировки, в которых, на мой взгляд, мало общего, кроме идеи воспользоваться представлением числа в какой-либо системе счисления (например, двоичной).
LSD (least significant digit):
Представим каждое число в двоичном виде. На каждом шаге алгоритма будем сортировать числа таким образом, чтобы они были отсортированы по первым k * i битам, где k – некоторая константа. Из данного определения следует, что на каждом шаге достаточно стабильно сортировать элементы по новым k битам. Для этого идеально подходит сортировка подсчетом (необходимо 2 k памяти и времени, что немного при удачном выборе константы). Асимптотика: O(n), если считать, что числа фиксированного размера (а в противном случае нельзя было бы считать, что сравнение двух чисел выполняется за единицу времени). Реализация довольно проста.
MSD (most significant digit):
На самом деле, некоторая разновидность блочной сортировки. В один блок будут попадать числа с равными k битами. Асимптотика такая же, как и у LSD версии. Реализация очень похожа на блочную сортировку, но проще. В ней используется функция digit, определенная в реализации LSD версии.
Битонная сортировка / Bitonic sort:
Идея данного алгоритма заключается в том, что исходный массив преобразуется в битонную последовательность – последовательность, которая сначала возрастает, а потом убывает. Ее можно эффективно отсортировать следующим образом: разобьем массив на две части, создадим два массива, в первый добавим все элементы, равные минимуму из соответственных элементов каждой из двух частей, а во второй – равные максимуму. Утверждается, что получатся две битонные последовательности, каждую из которых можно рекурсивно отсортировать тем же образом, после чего можно склеить два массива (так как любой элемент первого меньше или равен любого элемента второго). Для того, чтобы преобразовать исходный массив в битонную последовательность, сделаем следующее: если массив состоит из двух элементов, можно просто завершиться, иначе разделим массив пополам, рекурсивно вызовем от половинок алгоритм, после чего отсортируем первую часть по порядку, вторую в обратном порядке и склеим. Очевидно, получится битонная последовательность. Асимптотика: O(nlog 2 n), поскольку при построении битонной последовательности мы использовали сортировку, работающую за O(nlogn), а всего уровней было logn. Также заметим, что размер массива должен быть равен степени двойки, так что, возможно, придется его дополнять фиктивными элементами (что не влияет на асимптотику).
Timsort
Гибридная сортировка, совмещающая сортировку вставками и сортировку слиянием. Разобьем элементы массива на несколько подмассивов небольшого размера, при этом будем расширять подмассив, пока элементы в нем отсортированы. Отсортируем подмассивы сортировкой вставками, пользуясь тем, что она эффективно работает на отсортированных массивах. Далее будем сливать подмассивы как в сортировке слиянием, беря их примерно равного размера (иначе время работы приблизится к квадратичному). Для этого удобного хранить подмассивы в стеке, поддерживая инвариант — чем дальше от вершины, тем больше размер, и сливать подмассивы на верхушке только тогда, когда размер третьего по отдаленности от вершины подмассива больше или равен сумме их размеров. Асимптотика: O(n) в лучшем случае и O(nlogn) в среднем и худшем случае. Реализация нетривиальна, твердой уверенности в ней у меня нет, однако время работы она показала довольно неплохое и согласующееся с моими представлениями о том, как должна работать эта сортировка.
Подробнее timsort описан здесь:
Тестирование
Железо и система
Процессор: Intel Core i7-3770 CPU 3.40 GHz
ОЗУ: 8 ГБ
Тестирование проводилось на почти чистой системе Windows 10 x64, установленной за несколько дней до запуска. Использованная IDE – Microsoft Visual Studio 2015.Тесты
Все тесты поделены на четыре группы. Первая группа – массив случайных чисел по разным модулям (10, 1000, 10 5 , 10 7 и 10 9 ). Вторая группа – массив, разбивающийся на несколько отсортированных подмассивов. Фактически брался массив случайных чисел по модулю 10 9 , а далее отсортировывались подмассивы размера, равного минимуму из длины оставшегося суффикса и случайного числа по модулю некоторой константы. Последовательность констант – 10, 100, 1000 и т.д. вплоть до размера массива. Третья группа – изначально отсортированный массив случайных чисел с некоторым числом «свопов» — перестановок двух случайных элементов. Последовательность количеств свопов такая же, как и в предыдущей группе. Наконец, последняя группа состоит из нескольких тестов с полностью отсортированным массивом (в прямом и обратном порядке), нескольких тестов с исходным массивом натуральных чисел от 1 до n, в котором несколько чисел заменены на случайное, и тестов с большим количеством повторений одного элемента (10%, 25%, 50%, 75% и 90%). Таким образом, тесты позволяют посмотреть, как сортировки работают на случайных и частично отсортированных массивах, что выглядит наиболее существенным. Четвертая группа во многом направлена против сортировок с линейным временем работы, которые любят последовательности случайных чисел. В конце статьи есть ссылка на файл, в котором подробно описаны все тесты.
Размер входных данных
Было бы довольно глупо сравнивать, например, сортировку с линейным временем работы и квадратичную, и запускать их на тестах одного размера. Поэтому каждая из групп тестов делится еще на четыре группы, размера 10 5 , 10 6 , 10 7 и 10 8 элементов. Сортировки были разбиты на три группы, в первой – квадратичные (сортировка пузырьком, вставками, выбором, шейкерная и гномья), во второй – нечто среднее между логарифмическим временем и квадратом, (битонная, несколько видов сортировки Шелла и сортировка деревом), в третьей все остальные. Кого-то, возможно, удивит, что сортировка деревом попала не в третью группу, хотя ее асимптотика и O(nlogn), но, к сожалению, ее константа очень велика. Сортировки первой группы тестировались на тестах с 10 5 элементов, второй группы – на тестах с 10 6 и 10 7 , третьей – на тестах с 10 7 и 10 8 . Именно такие размеры данных позволяют как-то увидеть рост времени работы, при меньших размерах слишком велика погрешность, при больших алгоритм работает слишком долго (или же недостаток оперативной памяти). С первой группой я не стал заморачиваться, чтобы не нарушать десятикратное увеличение (10 4 элементов для квадратичных сортировок слишком мало), в конце концов, сами по себе они представляют мало интереса.
Как проводилось тестирование
На каждом тесте было производилось 20 запусков, итоговое время работы – среднее по получившимся значениям. Почти все результаты были получены после одного запуска программы, однако из-за нескольких ошибок в коде и системных глюков (все же тестирование продолжалось почти неделю чистого времени) некоторые сортировки и тесты пришлось впоследствии перетестировать.
Тонкости реализации
Возможно, кого-то удивит, что в реализации самого процесса тестирования я не использовал указатели на функции, что сильно сократило бы код. Оказалось, что это заметно замедляет работу алгоритма (примерно на 5-10%). Поэтому я использовал отдельный вызов каждой функции (это, конечно, не отразилось бы на относительной скорости, но… все же хочется улучшить и абсолютную). По той же причине были заменены векторы на обычные массивы, не были использованы шаблоны и функции-компараторы. Все это более актуально для промышленного использования алгоритма, нежели его тестирования.
Результаты
Все результаты доступны в нескольких видах – три диаграммы (гистограмма, на которой видно изменение скорости при переходе к следующему ограничению на одном типе тестов, график, изображающий то же самое, но иногда более наглядно, и гистограмма, на которой видно, какая сортировка лучше всего работает на каком-то типе тестов) и таблицы, на которых они основаны. Третья группа была разделена еще на три части, а то мало что было бы понятно. Впрочем, и так далеко не все диаграммы удачны (в полезности третьего типа диаграмм я вообще сильно сомневаюсь), но, надеюсь, каждый сможет найти наиболее подходящую для понимания.
Поскольку картинок очень много, они скрыты спойлерами. Немного комментариев по поводу обозначений. Сортировки названы так, как выше, если это сортировка Шелла, то в скобочках указан автор последовательности, к названиям сортировок, переходящих на сортировку вставками, приписано Ins (для компактности). В диаграммах у второй группы тестов обозначена возможная длина отсортированных подмассивов, у третьей группы — количество свопов, у четвертой — количество замен. Общий результат рассчитывался как среднее по четырем группам.
Первая группа сортировок
Массив случайных чисел
Совсем скучные результаты, даже частичная отсортированность при небольшом модуле почти незаметна.
Частично отсортированный массив
Уже гораздо интереснее. Обменные сортировки наиболее бурно отреагировали, шейкерная даже обогнала гномью. Сортировка вставками ускорилась только под самый конец. Сортировка выбором, конечно, работает совершенно также.
Свопы
Здесь наконец-то проявила себя сортировка вставками, хотя рост скорости у шейкерной примерно такой же. Здесь проявилась слабость сортировки пузырьком — достаточно одного свопа, перемещающего маленький элемент в конец, и она уже работает медленно. Сортировка выбором оказалась почти в конце.
Изменения в перестановке
Группа почти ничем не отличается от предыдущей, поэтому результаты похожи. Однако сортировка пузырьком вырывается вперед, так как случайный элемент, вставленный в массив, скорее всего будет больше всех остальных, то есть за одну итерацию переместится в конец. Сортировка выбором стала аутсайдером.
Повторы
Здесь все сортировки (кроме, конечно, сортировки выбором) работали почти одинаково, ускоряясь по мере увеличении количества повторов.
Итоговые результаты
За счет своего абсолютного безразличия к массиву, сортировка выбором, работавшая быстрее всех на случайных данных, все же проиграла сортировке вставками. Гномья сортировка оказалась заметно хуже последней, из-за чего ее практическое применение сомнительно. Шейкерная и пузырьковая сортировки оказались медленнее всех.
Вторая группа сортировок
Массив случайных чисел
Сортировка Шелла с последовательностью Пратта ведет себя совсем странно, остальные более менее ясно. Сортировка деревом любит частично отсортированные массивы, но не любит повторов, возможно, поэтому самое худшее время работы именно посередине.
Все как прежде, только Шелл с Праттом усилился на второй группе из-за отсортированности. Также становится заметным влияние асимптотики — сортировка деревом оказывается на втором месте, в отличие от группы с меньшим числом элементов.
Частично отсортированный массив
Здесь понятным образом ведут себя все сортировки, кроме Шелла с Хиббардом, который почему-то не сразу начинает ускоряться.
Здесь все, в общем, как и прежде. Даже асимптотика сортировки деревом не помогла ей вырваться с последнего места.
Свопы
Здесь заметно, что у сортировок Шелла большая зависимость от частичной отсортированности, так как они ведут себя практически линейно, а остальные две только сильно падают на последних группах.
Изменения в перестановке
Здесь все похоже на предыдущую группу.
Повторы
Опять все сортировки продемонстрировали удивительную сбалансированность, даже битонная, которая, казалось бы, почти не зависит от массива.
Итоговые результаты
Убедительное первое место заняла сортировка Шелла по Хиббарду, не уступив ни в одной промежуточной группе. Возможно, стоило ее отправить в первую группу сортировок, но… она слишком слаба для этого, да и тогда почти никого не было бы в группе. Битонная сортировка довольно уверенно заняла второе место. Третье место при миллионе элементах заняла другая сортировка Шелла, а при десяти миллионах сортировка деревом (асимптотика сказалась). Стоит обратить внимание, что при десятикратном увеличении размера входных данных все алгоритмы, кроме древесной сортировки, замедлились почти в 20 раз, а последняя всего лишь в 13.
Третья группа сортировок
Массив случайных чисел
Почти все сортировки этой группы имеют почти одинаковую динамику. Почему же почти все сортировки ускоряются, когда массив частично отсортирован? Обменные сортировки работают быстрее потому, что надо делать меньше обменов, в сортировке Шелла выполняется сортировка вставками, которая сильно ускоряется на таких массивах, в пирамидальной сортировке при вставке элементов сразу завершается просеивание, в сортировке слиянием выполняется в лучшем случае вдвое меньше сравнений. Блочная сортировка работает тем лучше, чем меньше разность между минимальным и максимальным элементом. Принципиально отличается только поразрядная сортировка, которой все это безразлично. LSD-версия работает тем лучше, чем больший модуль. Динамика MSD-версия мне не ясна, то, что она сработала быстрее чем LSD удивило.
Частично отсортированный массив
Здесь все тоже довольно понятно. Стало заметен алгоритм Timsort, на него отсортированность действует сильнее, чем на остальные. Это позволило этому алгоритму почти сравняться с оптимизированной версией быстрой сортировки. Блочная сортировка, несмотря на улучшение времени работы при частичной отсортированности, не смогла обогнать поразрядную сортировку.
Свопы
Здесь очень хорошо сработали быстрые сортировки. Это, скорее всего, объясняется удачным выбором опорного элемента. Все остальное почти также, как и в предыдущей группе.
Изменения в перестановке
Мне удалось достичь желаемой цели — поразрядная сортировка упала даже ниже адаптированной быстрой. Блочная сортировка оказалась лучше остальных. Еще почему-то timsort обогнал встроенную сортировку C++, хотя в предыдущей группе был ниже.
Повторы
Здесь все довольно тоскливо, все сортировки работают с одинаковой динамикой (кроме линейных). Из необычного можно заметить, что сортировка слиянием упала ниже сортировки Шелла.
Итоговые результаты
Несмотря на мои старания, LSD-версия поразрядной сортировки все-таки заняла первое место и при 10 7 , и при 10 8 элементов. Также она продемонстрировала почти линейный рост времени. Единственная ее замеченная мной слабость — плохая работа с перестановками. MSD-версия сработала немного хуже, в первую очередь из-за большого количества тестов, состоящих из случайных чисел по модулю 10 9 . Реализацией блочной сортировки я остался доволен, несмотря на громоздкость, она показало неплохой результат. Кстати, я слишком поздно это заметил, она не до конца соптимизирована, можно еще отдельно создавать массивы run и cnt, чтобы не тратить время на их удаление. Далее уверенно заняли места различные версии быстрой сортировки. Timsort-у не удалось, на мой взгляд, оказать им серьезную конкуренцию, хотя он не сильно отстал. Далее по скорости идут сортировки слиянием, после них — мои версии сортировки Шелла. Лучше всего оказалась последовательность s * 3 + s / 3, где s — предыдущий элемент последовательности. Далее идет единственное расхождение в двух таблицах — сортировка расческой оказалась лучше при большем числе элементов, чем сортировка Шелла с последовательностью Седжвика. И за последнее место боролись пирамидальная сортировка и оригинальная сортировка Шелла.
Выиграла последняя. Кстати, сортировка Шелла, как я потом проверил, очень плохо работает на тестах размера 2 n , так что ей просто повезло, что она попала в первую группу.
Если говорить о практическом применении, то хороша поразрядная сортировка (особенно lsd-версия), она стабильна, проста в реализации и очень быстра, однако не основана на сравнениях. Из основанных на сравнениях сортировок лучше всего смотрится быстрая сортировка. Ее недостатки — неустойчивость и квадратичное время работы на неудачных входных данных (пусть они и могут встретиться только при намеренном создании теста). Но с этим можно бороться, например, выбирая опорный элемент по какому-нибудь другому принципу, или же переходя на другую сортировку при неудаче (например, introsort, который, если не ошибаюсь, и реализован в С++). Timsort лишен этих недостатков, лучше работает на сильно отсортированных данных, но все же медленнее в целом и гораздо сложнее пишется. Остальные сортировки на данный момент, пожалуй, не очень практичны. Кроме, конечно, сортировки вставками, которую весьма удачно иногда можно вставить в алгоритм.
Заключение
Должен отметить, что не все известные сортировки приняли участие в тестировании, например, была пропущена плавная сортировка (мне просто не удалось ее адекватно реализовать). Впрочем, не думаю, что это большая потеря, эта сортировка очень громоздкая и медленная, как можно видеть, например, из этой статьи: habrahabr.ru/post/133996 Еще можно исследовать сортировки на распараллеливание, но, во-первых, у меня нет опыта, во-вторых, результаты, которые получались, крайне нестабильны, очень велико влияние системы.
Здесь можно посмотреть результаты всех запусков, а также некоторые вспомогательные тестирования: ссылка на документ.
Реализации алгоритмов с векторами остались, но их корректность и хорошую работу не гарантирую. Проще взять коды функций из статьи и переделать. Генераторы тестов тоже могут не соответствовать действительности, на самом деле такой вид они приняли уже после создания тестов, когда нужно было сделать программу более компактной.
Объяснение алгоритмов сортировки с примерами на Python
В этой статье будут рассмотрены популярные алгоритмы, принципы их работы и реализация на Python. А ещё сравним, как быстро они сортируют элементы в списке.
В качестве общего примера возьмём сортировку чисел в порядке возрастания. Но эти методы можно легко адаптировать под ваши потребности.
Пузырьковая сортировка
Этот простой алгоритм выполняет итерации по списку, сравнивая элементы попарно и меняя их местами, пока более крупные элементы не «всплывут» в начало списка, а более мелкие не останутся на «дне».
Алгоритм
Сначала сравниваются первые два элемента списка. Если первый элемент больше, они меняются местами. Если они уже в нужном порядке, оставляем их как есть. Затем переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.
При достижении конца списка процесс повторяется заново для каждого элемента. Это крайне неэффективно, если в массиве нужно сделать, например, только один обмен. Алгоритм повторяется n² раз, даже если список уже отсортирован.
Для оптимизации алгоритма нужно знать, когда его остановить, то есть когда список отсортирован.
Чтобы остановить алгоритм по окончании сортировки, нужно ввести переменную-флаг. Когда значения меняются местами, устанавливаем флаг в значение True , чтобы повторить процесс сортировки. Если перестановок не произошло, флаг остаётся False и алгоритм останавливается.
Реализация
Алгоритм работает в цикле while и прерывается, когда элементы ни разу не меняются местами. Вначале присваиваем swapped значение True , чтобы алгоритм запустился хотя бы один раз.
Время сортировки
Если взять самый худший случай (изначально список отсортирован по убыванию), затраты времени будут равны O(n²), где n — количество элементов списка.
Сортировка выборкой
Этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Наименьший элемент удаляется из второго списка и добавляется в первый.
Алгоритм
На практике не нужно создавать новый список для отсортированных элементов. В качестве него используется крайняя левая часть списка. Находится наименьший элемент и меняется с первым местами.
Теперь, когда нам известно, что первый элемент списка отсортирован, находим наименьший элемент из оставшихся и меняем местами со вторым. Повторяем это до тех пор, пока не останется последний элемент в списке.
Реализация
По мере увеличения значения i нужно проверять меньше элементов.
Время сортировки
Затраты времени на сортировку выборкой в среднем составляют O(n²), где n — количество элементов списка.
Сортировка вставками
Как и сортировка выборкой, этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Алгоритм перебирает второй сегмент и вставляет текущий элемент в правильную позицию первого сегмента.
Алгоритм
Предполагается, что первый элемент списка отсортирован. Переходим к следующему элементу, обозначим его х . Если х больше первого, оставляем его на своём месте. Если он меньше, копируем его на вторую позицию, а х устанавливаем как первый элемент.
Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x или не дойдём до конца списка. В первом случае x помещается на правильную позицию.
Реализация
Время сортировки
Время сортировки вставками в среднем равно O(n²), где n — количество элементов списка.
Пирамидальная сортировка
Также известна как сортировка кучей. Этот популярный алгоритм, как и сортировки вставками или выборкой, сегментирует список на две части: отсортированную и неотсортированную. Алгоритм преобразует второй сегмент списка в структуру данных «куча» (heap), чтобы можно было эффективно определить самый большой элемент.
Алгоритм
Сначала преобразуем список в Max Heap — бинарное дерево, где самый большой элемент является вершиной дерева. Затем помещаем этот элемент в конец списка. После перестраиваем Max Heap и снова помещаем новый наибольший элемент уже перед последним элементом в списке.
Этот процесс построения кучи повторяется, пока все вершины дерева не будут удалены.
Реализация
Создадим вспомогательную функцию heapify() для реализации этого алгоритма:
Время сортировки
В среднем время сортировки кучей составляет O(n log n), что уже значительно быстрее предыдущих алгоритмов.
Сортировка слиянием
Этот алгоритм относится к алгоритмам «разделяй и властвуй». Он разбивает список на две части, каждую из них он разбивает ещё на две и т. д. Список разбивается пополам, пока не останутся единичные элементы.
Соседние элементы становятся отсортированными парами. Затем эти пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока не отсортируются все элементы.
Алгоритм
Список рекурсивно разделяется пополам, пока в итоге не получатся списки размером в один элемент. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Это происходит до тех пор, пока не получится полный отсортированный список.
Сортировка осуществляется путём сравнения наименьших элементов каждого подмассива. Первые элементы каждого подмассива сравниваются первыми. Наименьший элемент перемещается в результирующий массив. Счётчики результирующего массива и подмассива, откуда был взят элемент, увеличиваются на 1.
Реализация
Обратите внимание, что функция merge_sort() , в отличие от предыдущих алгоритмов, возвращает новый список, а не сортирует существующий. Поэтому такая сортировка требует больше памяти для создания нового списка того же размера, что и входной список.
Время сортировки
В среднем время сортировки слиянием составляет O(n log n).
Быстрая сортировка
Этот алгоритм также относится к алгоритмам «разделяй и властвуй». Его используют чаще других алгоритмов, описанных в этой статье. При правильной конфигурации он чрезвычайно эффективен и не требует дополнительной памяти, в отличие от сортировки слиянием. Массив разделяется на две части по разные стороны от опорного элемента. В процессе сортировки элементы меньше опорного помещаются перед ним, а равные или большие —позади.
Алгоритм
Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.
Реализация
Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).
Время выполнения
В среднем время выполнения быстрой сортировки составляет O(n log n).
Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n²).
Встроенные функции сортировки на Python
Иногда полезно знать перечисленные выше алгоритмы, но в большинстве случаев разработчик, скорее всего, будет использовать функции сортировки, уже предоставленные в языке программирования.
Отсортировать содержимое списка можно с помощью стандартного метода sort() :
Или можно использовать функцию sorted() для создания нового отсортированного списка, оставив входной список нетронутым:
Оба эти метода сортируют в порядке возрастания, но можно изменить порядок, установив для флага reverse значение True :
В отличие от других алгоритмов, обе функции в Python могут сортировать также списки кортежей и классов. Функция sorted() может сортировать любую последовательность, которая включает списки, строки, кортежи, словари, наборы и пользовательские итераторы, которые вы можете создать.
Функции в Python реализуют алгоритм Tim Sort, основанный на сортировке слиянием и сортировке вставкой.
Сравнение скоростей сортировок
Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.
Пузырьковая сортировка — самый медленный из всех алгоритмов. Возможно, он будет полезен как введение в тему алгоритмов сортировки, но не подходит для практического использования.
Быстрая сортировка хорошо оправдывает своё название, почти в два раза быстрее, чем сортировка слиянием, и не требуется дополнительное место для результирующего массива.
Сортировка вставками выполняет меньше сравнений, чем сортировка выборкой и в реальности должна быть производительнее, но в данном эксперименте она выполняется немного медленней. Сортировка вставками делает гораздо больше обменов элементами. Если эти обмены занимают намного больше времени, чем сравнение самих элементов, то такой результат вполне закономерен.Вы познакомились с шестью различными алгоритмами сортировок и их реализациями на Python. Масштаб сравнения и количество перестановок, которые выполняет алгоритм вместе со средой выполнения кода, будут определяющими факторами в производительности. В реальных приложениях Python рекомендуется использовать встроенные функции сортировки, поскольку они реализованы именно для удобства разработчика.
