Алгоритм сортировки - NiNa.Az

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

История

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

Первые прототипы современных методов сортировки появились уже в 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 элементов: ${\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(n)}$
Алгоритмы неустойчивой сортировки
Сортировка выбором (англ. 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-большое
• Временная сложность алгоритма

Примечания

1. Кнут, 2007, с. 416.
2. Кнут, 2007, с. 417.
3. Кнут, 2007, с. 417-418.
4. Кнут, 2007, с. 418.
5. Кнут, 2007, с. 419.
6. Кнут, 2007, с. 420.
7. Кнут, 2007, с. 420-421.
8. Кнут, 2007, с. 421.
9. Кнут, 2007, с. 422.
10. Кнут, 2007, с. 22.
11. Кнут, 2007, с. 23.
12. Han, Yijie. Deterministic sorting in O(n log log n) time and linear space (англ.) // Journal of Algorithms. Cognition, Informatics and Logic. — 2004. — Т. 50, № 1. — С. 96-105. — doi:10.1016/j.jalgor.2003.09.001. Архивировано 12 ноября 2020 года.
13. Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.
14. Кнут, 2007.

Литература

• Кнут Д. Э. Искусство программирования. Том 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
• Анимированное сравнение алгоритмов сортировки (англ.)