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

Алгоритм сортировки
Алгоритм сортировки
Область использования	информатика; программирование; математика; анализ данных

Алгоритм сортировки
Алгоритм сортировки
Область использования	информатика; программирование; математика; анализ данных

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

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

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

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

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

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

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

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

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

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

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

p(i)<p(j)

для любых

K_{p(i)}=K_{p(j)}

и

i<j

.

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

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

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n), а плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей, всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее существует алгоритм сортировки Хана (англ. Yijie Han) с вычислительной сложностью O(n log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике)^[12]. Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать 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)

^[13]

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

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

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

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

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


Алгоритм	Описание	Время исполнения			Затраты памяти	Примечание
Алгоритм	Описание	В худшем случае	В среднем	В лучшем случае	Затраты памяти	Примечание
Алгоритмы устойчивой сортировки
Сортировка пузырьком (англ. Bubble sort)	Проходит по массиву, сравнивает последовательные пары элементов и меняет их местами, если они расположены в неправильном порядке	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$	В процессе сортировки минимальный элемент «всплывает» вверх массива, напоминая пузырь
Сортировка перемешиванием (англ. Cocktail sort)	Двунаправленный, оптимизированный вариант сортировки пузырьком	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$
Сортировка вставками (англ. Insertion sort)	Элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$
Гномья сортировка (англ. Gnome sort)	Гибрид сортировки вставками и сортировки пузырьком	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$	Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков
Сортировка слиянием (англ. Merge sort)	Рекурсивно сортирует половины массива, а затем объединяет их в один	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$
Сортировка с помощью двоичного дерева (англ. Tree sort)	На основе исходных данных строится двоичное дерево поиска, из которого последовательно извлекаются минимальные значения	$O(n^{2})$	$O(n\log n)$	$O(n\log n)$	$O(n)$
Timsort (англ. Timsort)	Гибрид сортировки вставками и сортировки слиянием. Основан на предположении, что при решении практических задач входной массив зачастую состоит из отсортированных подмассивов	$O(n\log n)$	$O(n\log n)$	$O(n)$	$O(n)$	Используется в стандартных библиотеках Python, Java и Android
Алгоритмы неустойчивой сортировки
Сортировка выбором (англ. Selection sort)	Делит входной массив на упорядоченную и неупорядоченную части. Затем последовательно переносит в первую часть наименьшие элементы из второй	$O(n^{2})$	$O(n^{2})$	$O(n^{2})$	$O(1)$
Сортировка расчёской (англ. Comb sort)	Модификация сортировки пузырьком, в которой расстояние между сравниваемыми парами значений отлично от 1	$O(n^{2})$	$O(n\log n)$	$O(n\log n)$	$O(1)$
Сортировка Шелла (англ. Shell sort)	Модификация сортировки вставками, в которой расстояние между сравниваемыми парами значений отлично от 1	$O(n^{2})$	$O(n\log ^{2}n)$	$O(n\log n)$	$O(1)$
Пирамидальная сортировка (англ. Heapsort)	На основе исходных данных строится двоичная куча, из которой последовательно извлекаются минимальные значения	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$
Плавная сортировка (англ. Smoothsort)	Модификация пирамидальной сортировки, оптимизирующая сортировку частично упорядоченного массива	$O(n\log n)$	$O(n\log n)$	$O(n)$	$O(1)$
Быстрая сортировка (англ. Quicksort)	Выбирается опорный элемент p. Все ключи, меньшие p, перемещаются влево от него, а все ключи, большие либо равные p, — вправо. Далее алгоритм рекурсивно применяется к каждой из частей	$O(n^{2})$	$O(n\log n)$	$O(n\log n)$	$O(\log n)$
Интроспективная сортировка (англ. Introsort)	Гибрид быстрой сортировки, пирамидальной сортировки и сортировки вставками. При превышении глубины рекурсии переключается на пирамидальную сортировку	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(\log n)$	Используется в реализациях C++ (STL)
Придурковатая сортировка (англ. Stooge sort)	Меняет местами первый и последний элементы массива, если необходимо. Затем делит массив на три части, в каждой из которых запускается рекурсивно	$O(n^{2{,}709\dots })$	$O(n^{2{,}709\dots })$	$O(n^{2{,}709\dots })$	$O(n)$	Метод назван в честь американской комик-группы «Three Stooges»
Непрактичные алгоритмы сортировки
Bogosort	Массив произвольно перемешивается до тех пор, пока не окажется отсортированным	Неограниченно	$O(n\cdot n!)$	$O(n)$	$O(1)$	Используется только в академических целях
Сортировка перестановкой	Генерируются все возможные последовательности массива, из которых выбирается упорядоченная	$O(n\cdot n!)$	$O(n\cdot n!)$	$O(n)$	$O(n)$	Используется только в академических целях
Гравитационная сортировка (англ. Bead sort)	Числа представляются в виде бусинок на штырях, затем сортируются под действием гравитации	$O(n\cdot m)$	$O(n\cdot m)$	$O(n\cdot m)$	$O(n\cdot m)$	$m$ — максимальное значение элемента. Требуется специализированное аппаратное обеспечение
Алгоритмы, не основывающиеся на сравнениях
Блочная сортировка (англ. Bucket sort)	Элементы распределяются по блокам согласно диапазону значений, каждый из которых затем сортируется	$O(n^{2})$	$O(n+k)$	$O(n+k)$	$O(n+k)$	$k$ — количество корзин
Поразрядная сортировка (англ. Radix sort)	Массив сортируется с помощью поразрядного сравнения чисел	$O(w\cdot n)$	$O(w\cdot n)$	$O(w\cdot n)$	$O(n+k)$	$w$ — количество разрядов ключа; $k$ — размер алфавита
Сортировка подсчётом (англ. Counting sort)	Подсчитывается количество вхождений каждого целого числа из диапазона ключей в массив, после чего элементы выводятся для всех ненулевых счётчиков	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	$k$ — максимальное значение ключа
Параллельные и распределённые алгоритмы сортировки
Параллельная сортировка слиянием (англ. Parallel merge sort)	Массив разбивается на части, каждая из которых сортируется в отдельном потоке; результаты сливаются параллельно	$O(n\log n)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O(n)$	$p$ — число доступных процессоров (потоков). Устойчивый алгоритм
Samplesort (англ. Samplesort)	Из входных данных извлекается выборка, по которой определяются границы диапазонов. Элементы распределяются по блокам, которые сортируются независимо	$O(n\log n)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O(n)$	$p$ — число процессоров. Широко применяется в высокопроизводительных системах
TeraSort	Распределённая сортировка на основе выборки и разбиения по диапазонам; каждый узел кластера сортирует свой диапазон ключей	$O(n\log n)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O\!\left({\dfrac {n\log n}{p}}\right)$	$O(n)$	Разработан для сортировки сверхбольших наборов данных в кластерах (Apache Hadoop)

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

Для алгоритмов такого типа важны не только асимптотические оценки, но и:

балансировка нагрузки между ядрами;
стоимость синхронизации между потоками;
локальность обращений к памяти;
влияние кэш-памяти и архитектуры NUMA;
минимизация ложного совместного использования кэш-линий (англ. false sharing).

Основные подходы

Параллельная сортировка слиянием — массив разбивается на несколько частей, каждая из которых сортируется независимо, после чего отсортированные блоки сливаются. Метод хорошо масштабируется и удобен для реализации в многопоточной среде, однако требует дополнительной памяти для этапов слияния.
Параллельная быстрая сортировка — после выбора опорного элемента массив разбивается на подмассивы, которые затем сортируются параллельно. Эффективность такого подхода сильно зависит от качества выбора опорного элемента и равномерности разбиения.
Samplesort — из входных данных выбирается выборка, по которой определяются границы диапазонов. Затем элементы распределяются по блокам, сортируемым независимо. Такой метод часто применяется в высокопроизводительных параллельных реализациях.
Параллельная поразрядная сортировка — используется главным образом для целочисленных ключей и строк фиксированного формата. Она хорошо подходит для многопроцессорной обработки благодаря тому, что отдельные разряды или блоки значений могут обрабатываться независимо.
Сортирующие сети — применяются главным образом для небольших массивов, а также в задачах, где важно заранее известное расписание сравнений. Такие методы удобны для SIMD-обработки и аппаратной реализации, но в общем случае уступают более адаптивным алгоритмам.

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

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

Обычно распределённая сортировка включает несколько этапов:

локальная сортировка фрагментов данных на отдельных узлах;
выбор границ диапазонов ключей или разбиение данных на корзины;
перераспределение данных между узлами по диапазонам значений;
окончательная локальная сортировка или многопутевое слияние.

Типичные методы

Распределённая сортировка слиянием — каждый узел сортирует свой фрагмент данных, после чего выполняется слияние результатов. Метод близок к внешней сортировке и удобен при работе с большими файлами.
Распределённый samplesort — на основе выборки оценивается распределение ключей, после чего данные перераспределяются между узлами так, чтобы каждый узел получил свой диапазон значений. После этого узлы выполняют локальную сортировку. Такой подход хорошо подходит для кластеров и систем массовой обработки данных.
Сортировка в модели MapReduce — данные разбиваются на части на этапе map, затем перераспределяются на этапе shuffle и сортируются или сливаются на этапе reduce. Подобные схемы используются в системах Apache Hadoop и Apache Spark.
TeraSort — практический вариант распределённой сортировки на основе выборки и разбиения по диапазонам, разработанный для сортировки очень больших наборов данных в кластерах.

Для распределённых алгоритмов часто важнее не число сравнений как таковое, а:

объём сетевого обмена;
число проходов по данным;
стоимость операций чтения и записи на диске;
устойчивость к сбоям узлов;
равномерность распределения данных между участниками вычисления.

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

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

Чаще всего гибридные алгоритмы:

переключаются на простой метод сортировки для малых подмассивов;
используют один алгоритм в среднем случае и другой — в качестве гарантии от деградации;
учитывают частичную упорядоченность входных данных;
подбирают стратегию в зависимости от типа ключей и структуры входа.

Наиболее известные гибридные алгоритмы

Introsort — сочетает быструю сортировку, пирамидальную сортировку и обычно сортировку вставками для малых подмассивов. В обычных условиях работает как быстрая сортировка, но при слишком большой глубине рекурсии переключается на пирамидальную, что обеспечивает сложность худшего случая $O(n\log n)$ .
Timsort — гибрид сортировки слиянием и сортировки вставками, ориентированный на реальные данные, в которых нередко уже присутствуют частично упорядоченные участки. Алгоритм устойчив и особенно эффективен на входах с естественными сериями.
Spreadsort — семейство алгоритмов, сочетающих идеи поразрядной сортировки и сортировки сравнениями. Применяется прежде всего для числовых ключей и строк.
Библиотечные гибриды — во многих стандартных библиотеках сортировка реализуется как комбинация нескольких методов с порогами переключения, оптимизациями выбора опорного элемента, а также специальной обработкой коротких и почти упорядоченных последовательностей.

Практическое значение

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

лучше учитывают особенности реальных входных данных;
снижают вероятность вырожденных случаев;
эффективнее используют кэш-память;
позволяют совместить высокую среднюю производительность с хорошими гарантиями в худшем случае.

Именно поэтому в современных программных библиотеках нередко используются не классические алгоритмы в их исходном виде, а их гибридные модификации, адаптированные к архитектуре процессора, размеру данных и требованиям к устойчивости сортировки.

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

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

↑ ¹ ² Кнут, 2007, с. 416.
↑ Кнут, 2007, с. 417.
↑ Кнут, 2007, с. 417—418.
↑ ¹ ² ³ Кнут, 2007, с. 418.
↑ ¹ ² Кнут, 2007, с. 419.
↑ Кнут, 2007, с. 420.
↑ Кнут, 2007, с. 420—421.
↑ Кнут, 2007, с. 421.
↑ ¹ ² Кнут, 2007, с. 422.
↑ ¹ ² ³ ⁴ Кнут, 2007, с. 22.
↑ Кнут, 2007, с. 23.
↑ 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.
↑ Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.
↑ Кнут, 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
Анимированное сравнение алгоритмов сортировки (англ.)

[_9cb2dd92f5f74c0f-1] ¹ ² Кнут, 2007, с. 416.

[_9cb2dd92f5f74c0e-2] Кнут, 2007, с. 417.

[_7046a1d91e7be6fb-3] Кнут, 2007, с. 417—418.

[_9cb2dd92f5f74c01-4] ¹ ² ³ Кнут, 2007, с. 418.

[_9cb2dd92f5f74c00-5] ¹ ² Кнут, 2007, с. 419.

[_9cb2da92f5f74710-6] Кнут, 2007, с. 420.

[_1c5faf64c32dea21-7] Кнут, 2007, с. 420—421.

[_9cb2da92f5f74711-8] Кнут, 2007, с. 421.

[_9cb2da92f5f74712-9] ¹ ² Кнут, 2007, с. 422.

[_2c8618e252f4c212-10] ¹ ² ³ ⁴ Кнут, 2007, с. 22.

[_2c8618e252f4c213-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.

[13] Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.

[_63deeb926b89e866-14] Кнут, 2007.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Алгоритмы сортировки
Теория	Сложность О-нотация Отношение порядка Типы сортировки Устойчивая Внутренняя Внешняя
Обменные	Пузырьком Перемешиванием Гномья Быстрая Расчёской Сортировка чёт-нечет Поразрядная
Выбором	Выбором Пирамидальная Плавная
Вставками	Вставками Шелла Деревом
Слиянием	Слиянием
Без сравнений	Подсчётом Блочная
Гибридные	Introsort Timsort
Прочее	Топологическая Сети Битонная
Непрактичные	Bogosort Stooge sort Блинная Медленная

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

История

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

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

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

Свойства и классификация

Обзор алгоритмов сортировки

Сортировка на многоядерных процессорах

Основные подходы

Сортировка в распределённых системах

Типичные методы

Гибридные алгоритмы сортировки

Наиболее известные гибридные алгоритмы

Практическое значение

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

Примечания

Литература

Ссылки

Дополнительно по теме

Категории