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

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

История

Табулятор Холлерита с «сортировальным ящиком»

Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определённая электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определён порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков. Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту.

EDVAC

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчётов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC. Наряду с отмеченными алгоритмами внутренней сортировки, появлялись алгоритмы внешней сортировки, развитию которых способствовал ограниченный объём памяти первых вычислительных машин. В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния.

Быстрая сортировка Хоара

К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы.

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние со вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям.

Формулировка задачи

Пусть требуется упорядочить N элементов: $R_{1},R_{2},\dots ,R_{n}$. Каждый элемент представляет собой запись $R_{j}$, содержащую некоторую информацию и ключ $K_{j}$, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей $a,b,c$ выполнялись следующие условия:

• закон трихотомии: либо $a<b$, либо $a>b$, либо $a=b$;
• закон транзитивности: если $a<b$ и $b<c$, то $a<c$.

Данные условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке большинством методов.

Задачей сортировки является нахождение такой перестановки записей $p(1)p(2)\dots p(n)$ с индексами $\{1,2,\dots ,N\}$, после которой ключи расположились бы в порядке неубывания:

$K_{p(1)}\leqslant K_{p(2)}\leqslant \dots \leqslant K_{p(n)}$

Сортировка называется устойчивой, если не меняет взаимного расположения элементов с одинаковыми ключами:

$p(i)<p(j)$ для любых $K_{p(i)}=K_{p(j)}$ и $i<j$.

Методы сортировки можно разделить на внутренние и внешние. Внутренняя сортировка используется для данных, помещающихся в оперативную память, за счёт чего является более гибкой в плане структур данных. При внешней сортировке данные в оперативную память не помещаются, и она ориентирована на достижение результата в условиях ограниченных ресурсов.

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей, всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log² n) операций. При этом число n должно быть заранее известно;
• Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Оптимальность O(n log n) в общем случае

В общем случае задача сортировки предполагает, что единственной обязательно доступной операцией над элементами является сравнение. Ответом на сравнение элементов $a$ и $b$ может быть один из двух вариантов: $a\leq b$ или $a>b$. Поэтому если в ходе работы алгоритм совершает $k$ сравнений, то всего возможно $2^{k}$ вариантов комбинаций ответов на них.

Количество перестановок из $n$ элементов равно $n!$. Для того, чтобы можно было сюръективно отобразить множество комбинаций ответов на множество всех перестановок, количество сравнений должно быть не меньше, чем $\log _{2}{n!}$ (поскольку сравнение — единственная разрешённая операция).

Прологарифмировав формулу Стирлинга, можно обнаружить, что $\log _{2}{n!}=\log _{2}{\left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\right)}=n\log n+O(n)=\Omega (n\log n)$

Свойства и типы

• Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
• Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
• Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоёмкость худшего случая для этих алгоритмов составляет $O$($n\cdot \log n$), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

• Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.
  • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
• Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.
  • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
  • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

• потребности в дополнительной памяти или её отсутствию
• потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Обзор наиболее популярных алгоритмов сортировки

Алгоритм	Описание	Время исполнения		Затраты памяти	Примечание
		В худшем случае	В среднем	В лучшем случае
Алгоритмы устойчивой сортировки
Сортировка пузырьком (англ. Bubble sort)	Проходит по массиву, сравнивает последовательные пары элементов и меняет их местами, если они расположены в неправильном порядке.	$O(n^{2})$	$O(n^{2})$	$O(1)$	В процессе сортировки минимальный элемент "всплывает" вверх массива, напоминая пузырь
Сортировка перемешиванием (англ. Cocktail sort)	Двунаправленный, оптимизированный вариант сортировки пузырьком	$O(n^{2})$	$O(n^{2})$	$O(1)$
Сортировка вставками (англ. Insertion sort)	Элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов	$O(n^{2})$	$O(n^{2})$	$O(1)$
Гномья сортировка (англ. Gnome sort)	Гибрид сортировок вставками и пузырьком.	$O(n^{2})$	$O(n^{2})$	$O(1)$	Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков
Сортировка слиянием (англ. Merge sort)	Рекурсивно сортирует половины массива, а затем комбинирует их в один	$O(n\log {n})$	$O(n\log {n})$	$O(n)$
Сортировка с помощью двоичного дерева (англ. Tree sort)	На основе исходных данных строится двоичное дерево поиска, в котором последовательно собираются минимальные значения	$O(n^{2})$	$O(n\log {n})$	$O(n)$
Сортировка Timsort (англ. Timsort)	Гибрид сортировок вставками и слиянием. Основан на предположении, что при решении практических задач входной массив зачастую состоит из отсортированных подмассивов	$O(n\log {n})$	$O(n\log {n})$	$O(1)$
Алгоритмы неустойчивой сортировки
Сортировка выбором (англ. Selection sort)	Делит входной массив на упорядоченную и неупорядоченную части. Затем последовательно переносит в первую часть наименьшие элементы из второй	$O(n^{2})$	$O(n^{2})$	$O(1)$
Сортировка расчёской (англ. Comb sort)	Модификация сортировки пузырьком, в которой расстояние между сравниваемыми парами значений отлично от 1	$O(n^{2})$	$O(n^{2}/2^{p})$	$O(1)$	Несмотря на бóльшую алгоритмическую сложность, при не очень больших размерах массива сортировка расчёской будет более эффективна чем быстрая сортировка
Сортировка Шелла (англ. Shell sort)	Модификация сортировки вставками, в которой расстояние между сравниваемыми парами значений отлично от 1	$O(n^{2})$	$O(n\log ^{2}{n})$	$O(1)$
Пирамидальная сортировка (сортировка кучи, Heapsort)	На основе исходных данных строится двоичная куча, в которой последовательно собираются минимальные значения	$O(n\log {n})$	$O(n\log {n})$	$O(1)$
Плавная сортировка (англ. Smoothsort)	Модификация пирамидальной сортировки, оптимизирующая сортировку частично упорядоченного массива	$O(n\log {n})$	$O(n\log {n})$	$O(n)$
Быстрая сортировка (англ. Quicksort)	Выбирается опорный элемент p. Все ключи меньшие p перемещаются влево от него, а все ключи большие либо равные p, вправо. Далее алгоритм рекурсивно применяется к каждой из частей	$O(n^{2})$	$O(n\log {n})$	$O(\log {n})$
Интроспективная сортировка (англ. Introsort)	Гибрид быстрой и пирамидальной сортировок	$O(n\log {n})$	$O(n\log {n})$	$O(n)$
Придурковатая сортировка (англ. Stooge sort)	Меняет местами первый и последний элементы массива, если необходимо. Затем делит массив на три части, в каждой из которых запускается рекурсивно	$O(n^{\log {3}/\log {1.5}})$ $=O(n^{2.709...})$	$O(n^{2.709...})$	$O(1)$	Метод назван в честь американской комик-группы "Three stooges" ("Три придурка"). Сходство заключается в том, что алгоритм безумно мечется по уже отсортированным третям массива.
Непрактичные алгоритмы сортировки
Bogosort	Массив произвольно перемешивается до тех пор, пока не окажется отсортированным	Неограниченно	$O(n!)$	$O(1)$	Используется только в академических целях
Сортировка перестановкой	Генерируются все возможные последовательности массива, из которых выбирается упорядоченная	$O(n!)$	$O(n!)$	$O(n)$	Используется только в академических целях
Гравитационная сортировка (англ. Bead sort)	Числа представляются в виде бусинок на штырях, затем сортируются под действием гравитации	$O({\sqrt {n}})$	$O({\sqrt {n}})$	$O(n^{2})$	Требуется специализированное аппаратное обеспечение
Алгоритмы, не основывающиеся на сравнениях
Блочная сортировка (англ. Bucket sort)	Элементы распределяются по блокам согласно диапазону значений, каждый из которых затем рекурсивно сортируется	$O(n^{2})$	$O(n^{2}+n/k+k)$	$O(n+k)$	$k$ - заранее известное количество корзин
Поразрядная сортировка (англ. Radix sort)	Массив сортируется согласно с помощью поразрядного сравнения чисел	$O(wn)$	$O(wn)$	$O(n)$	$w$ — количество бит, требуемых для хранения каждого ключа.
Сортировка подсчётом (англ. Counting sort)	Подсчитывается количество вхождений каждого целого числа из диапазона ключей в массив. Затем выводится значения всех ненулевых значений	$O(n+k)$	$O(n+k)$	$O(n+k)$	$k$ - максимальное значение элементов ключа

Сортировка строк

Одним из частых приложений алгоритмов сортировки является сортировка строк. Обобщённый алгоритм может выглядеть так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины N со строкой длины N+1) считается меньше любого символа.

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой». Также на практике эффективным способом решения проблемы сортировки строк, содержащих числа, является добавление некоторого числа нулей перед числом, таким образом, «011» будет считаться больше «009».

См. также

• O-большое
• Временная сложность алгоритма

Литература

• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
• Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
• Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7.

Ссылки

• Теория, задачи, тестирующая система
• Алгоритмы сортировки на algolist.manual.ru
• Анимированное сравнение алгоритмов сортировки (англ.)