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

История

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle p(i)<p(j)}$ для любых ${\displaystyle K_{p(i)}=K_{p(j)}}$ и ${\displaystyle 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 ) в общем случае

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

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

Прологарифмировав формулу Стирлинга , можно обнаружить, что ${\displaystyle \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)}$

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

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

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

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

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

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

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

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

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

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

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

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

См. также

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

Примечания

Литература

• Кнут Д. Э. = 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 .

Ссылки

	Имеется викиучебник по теме « »

• (англ.)