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

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

Формально выходные данные любого алгоритма сортировки должны удовлетворять двум условиям:

Вывод осуществляется в монотонном порядке (каждый элемент не меньше/больше предыдущего элемента в соответствии с требуемым порядком).
Выходные данные представляют собой перестановку (переупорядочение с сохранением всех исходных элементов) входных данных.

Для оптимальной эффективности входные данные должны храниться в структуре данных , допускающей произвольный доступ , а не в структуре, допускающей только последовательный доступ .

История и концепции

С самого начала компьютерных вычислений проблема сортировки привлекала большое количество исследований, возможно, из-за сложности ее эффективного решения, несмотря на ее простую и знакомую формулировку. Среди авторов первых алгоритмов сортировки примерно в 1951 году была Бетти Холбертон , работавшая над ENIAC и UNIVAC . ^[1]^[2] Пузырьковая сортировка была проанализирована еще в 1956 году. ^[3] Асимптотически оптимальные алгоритмы известны с середины 20 века – новые алгоритмы изобретаются до сих пор: широко используемый Тимсорт датируется 2002 годом, а библиотечная сортировка впервые опубликована в 2006 году.

Алгоритмы сортировки сравнения имеют фундаментальное требование сравнений Ω( n log n ) (некоторые входные последовательности потребуют сравнений, кратных n log n , где n — количество элементов в массиве, подлежащих сортировке). Алгоритмы, не основанные на сравнениях, такие как сортировка по подсчету , могут иметь более высокую производительность.

Алгоритмы сортировки широко распространены на вводных занятиях по информатике , где обилие алгоритмов для решения задачи обеспечивает мягкое введение в различные основные концепции алгоритмов, такие как нотация большого числа O , алгоритмы «разделяй и властвуй» , структуры данных , такие как кучи и двоичные данные. деревья , рандомизированные алгоритмы , наилучшего, наихудшего и среднего случая анализ , компромисс между временем и пространством , а также верхние и нижние границы .

Оптимальная (с наименьшим количеством сравнений и замен) или быстрая сортировка небольших массивов (т. е. с учетом особенностей машины) по-прежнему остается открытой исследовательской проблемой, решения которой известны только для очень маленьких массивов (<20 элементов). Аналогично оптимальная (по разным определениям) сортировка на параллельной машине является открытой темой исследования.

Классификация

Алгоритмы сортировки можно классифицировать по:

Вычислительная сложность
- Лучшее, худшее и среднее поведение с точки зрения размера списка. Для типичных алгоритмов последовательной сортировки хорошее поведение — O( n log n ), а параллельная сортировка — за O(log ² n ), а плохое поведение — O( n ²). Идеальное поведение для серийной сортировки — O( n ), но в среднем случае это невозможно. Оптимальная параллельная сортировка — O(log n ).
- Обмены на «местные» алгоритмы.
Использование памяти (и использование других ресурсов компьютера). В частности, некоторые алгоритмы сортировки являются « на месте ». Строго говоря, для сортировки на месте требуется только O(1) памяти, помимо сортируемых элементов; иногда дополнительная память O(log n ) считается «на месте».
Рекурсия. Некоторые алгоритмы являются либо рекурсивными, либо нерекурсивными, тогда как другие могут быть и тем, и другим (например, сортировка слиянием).
Стабильность: стабильные алгоритмы сортировки поддерживают относительный порядок записей с одинаковыми ключами (т. е. значениями).
Независимо от того, являются ли они сортом сравнения . Сортировка сравнением проверяет данные только путем сравнения двух элементов с помощью оператора сравнения.
Общий метод: вставка, обмен, выбор, объединение и т. д. Сортировки обмена включают пузырьковую сортировку и быструю сортировку. Сортировки выбором включают циклическую сортировку и пирамидальную сортировку.
Является ли алгоритм последовательным или параллельным. Остальная часть этого обсуждения почти исключительно концентрируется на последовательных алгоритмах и предполагает последовательную работу.
Адаптивность: влияет ли предварительная сортировка входных данных на время работы. Алгоритмы, учитывающие это, известны как адаптивные .
Онлайн: такой алгоритм, как сортировка вставками, который находится в сети, может сортировать постоянный поток входных данных.

Стабильность

Стабильные алгоритмы сортировки сортируют одинаковые элементы в том же порядке, в котором они появляются во входных данных. Например, в примере сортировки карт справа карты сортируются по их рангу, а их масть игнорируется. Это позволяет иметь несколько разных правильно отсортированных версий исходного списка. Стабильные алгоритмы сортировки выбирают один из них в соответствии со следующим правилом: если два элемента сравниваются как равные (например, две карты с пятью картами), то их относительный порядок будет сохранен, т. е. если один из них идет перед другим во входных данных, он придет перед другим на выходе.

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

Более формально сортируемые данные можно представить в виде записи или кортежа значений, а часть данных, которая используется для сортировки, называется ключом . В примере с картой карты представлены в виде записи (ранг, масть), а ключом является ранг. Алгоритм сортировки стабилен, если всякий раз, когда есть две записи R и S с одинаковым ключом и R появляется перед S в исходном списке, тогда R всегда будет появляться перед S в отсортированном списке.

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

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

Одним из применений стабильных алгоритмов сортировки является сортировка списка с использованием первичного и вторичного ключа. Например, предположим, что мы хотим отсортировать карточную комбинацию так, чтобы масти были расположены в следующем порядке: трефы (♣), бубны ( ♦ ), червы ( ♥ ), пики (♠), а внутри каждой масти карты сортируются по классифицировать. Это можно сделать, сначала отсортировав карты по рангу (используя любую сортировку), а затем выполнив стабильную сортировку по масти:

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

Сравнение алгоритмов

В этих таблицах $n$ — количество записей, подлежащих сортировке. В столбцах «Лучший», «Средний» и «Худший» указана временная сложность в каждом случае при условии, что длина каждого ключа постоянна и, следовательно, все сравнения, замены и другие операции могут выполняться за постоянное время. «Память» обозначает объем дополнительной памяти, необходимой в дополнение к той, которая используется самим списком, при том же предположении. Перечисленные время выполнения и требования к памяти указаны внутри нотации большого О , поэтому основание логарифмов не имеет значения. обозначений $Журнал 2 n$ означает $(log n) 2$ .

Сортировки сравнения

Ниже представлена таблица сравнения сортов . Математический анализ показывает, что сортировка сравнением не может работать в среднем лучше, чем $O (n log n)$ . ^[4]

Сортировки сравнения
Имя	Лучший	Средний	Худший	Память	Стабильный	Метод	Другие примечания
Сортировка слиянием на месте	—	—	$n\log ^{2}n$	1	Да	Слияние	Может быть реализована как стабильная сортировка на основе стабильного слияния на месте. ^[5]
пирамидальная сортировка	$n\log n$	$n\log n$	$n\log n$	1	Нет	Выбор
Интросорт	$n\log n$	$n\log n$	$n\log n$	$\log n$	Нет	Разделение и выбор	Используется в нескольких реализациях STL .
Идет судьба	$n\log n$	$n\log n$	$n\log n$	$н$	Да	Слияние	Высокая распараллеливаемость (до $O (log n)$ с использованием алгоритма трех венгров). ^[6]
Сортировка турниров	$n\log n$	$n\log n$	$n\log n$	$н$ ^[7]	Нет	Выбор	Вариант пирамидальной сортировки.
Сортировка дерева	$n\log n$	$n\log n$	$n\log n$ (сбалансированный)	$н$	Да	Вставка	При использовании самобалансирующегося двоичного дерева поиска .
Блочная сортировка	$н$	$n\log n$	$n\log n$	1	Да	Вставка и объединение	на основе блоков Объедините ⁠ $O(n)$ ⁠ алгоритм слияния на месте ^[8] с сортировкой слиянием снизу вверх .
Гладкая сортировка	$н$	$n\log n$	$n\log n$	1	Нет	Выбор	Адаптивный последовательности вариант пирамидальной сортировки, основанный на Леонардо, а не на традиционной двоичной куче .
Тимсорт	$н$	$n\log n$	$n\log n$	$н$	Да	Вставка и объединение	Выполняет сравнения n-1 , когда данные уже отсортированы или отсортированы обратно.
Сортировка терпения	$н$	$n\log n$	$n\log n$	$н$	Нет	Вставка и выбор	Находит все самые длинные возрастающие подпоследовательности за $O (n log n)$ .
Кубосорт	$н$	$n\log n$	$n\log n$	$н$	Да	Вставка	Выполняет сравнения n-1 , когда данные уже отсортированы или отсортированы обратно.
Быстрая сортировка	$n\log n$	$n\log n$	$n^{2}$	$\log n$	Нет	Разделение	Быстрая сортировка обычно выполняется на месте с использованием $O (log n) .$ стека ^[9]^[10]
Сортировка библиотеки	$n\log n$	$n\log n$	$n^{2}$	$н$	Нет	Вставка	Похоже на сортировку вставкой с пробелами. Он требует случайной перестановки входных данных, чтобы гарантировать временные рамки с высокой вероятностью, что делает его нестабильным.
Шеллсорт	$n\log n$	$n^{4/3}$	$n^{3/2}$	1	Нет	Вставка	Небольшой размер кода.
Гребенчатая сортировка	$n\log n$	$n^{2}$	$n^{2}$	1	Нет	Обмен	В среднем быстрее, чем пузырьковая сортировка.
Сортировка вставкой	$н$	$n^{2}$	$n^{2}$	1	Да	Вставка	$O (n + d)$ , в худшем случае для последовательностей, имеющих d инверсий .
Пузырьковая сортировка	$н$	$n^{2}$	$n^{2}$	1	Да	Обмен	Небольшой размер кода.
Сорт коктейльного шейкера	$н$	$n^{2}$	$n^{2}$	1	Да	Обмен	Вариант пузырьковой сортировки, который хорошо справляется с небольшими значениями в конце списка.
Гном сортирует	$н$	$n^{2}$	$n^{2}$	1	Да	Обмен	Небольшой размер кода.
Нечетно-четный сорт	$н$	$n^{2}$	$n^{2}$	1	Да	Обмен	Легко может быть запущен на параллельных процессорах.
Простой вид блинов	$н$	$n^{2}$	$n^{2}$	1	Нет	Выбор	Вариант сортировки выбором, в котором после каждого сканирования выбора используются перестановки вместо простой замены двух элементов.
Сортировка прядей	$н$	$n^{2}$	$n^{2}$	$н$	Да	Выбор
Сортировка выбором	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Выбор	Стабильно с ⁠ $O(n)$ ⁠ дополнительное пространство при использовании связанных списков или при использовании варианта сортировки вставками вместо замены двух элементов местами. ^[11]
Обменная сортировка	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Обмен	Небольшой размер кода.
Циклическая сортировка	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Выбор	На месте с теоретически оптимальным количеством операций записи.

Сортировки без сравнения

В следующей таблице описаны алгоритмы сортировки целых чисел и другие алгоритмы сортировки, не являющиеся сортировками сравнения . По сути, они не ограничены Ω ( n log n ) . ^[12] Приведенные ниже сложности предполагают, что $n$ нужно отсортировать $элементов с ключами размера k$ , размером цифр $d$ и $r$ — диапазоном чисел, подлежащих сортировке. Многие из них основаны на предположении, что размер ключа достаточно велик, чтобы все записи имели уникальные значения ключей и, следовательно, $n ≪ 2. к$ , где ≪ означает «намного меньше». с единичной стоимостью В модели машины произвольного доступа алгоритмы со временем работы $\scriptstyle n\cdot {\frac {k}{d}}$ , такие как поразрядная сортировка, по-прежнему требуют времени, пропорционального $Θ(n log n)$ , поскольку $n$ ограничено значением не более $2^{\frac {k}{d}}$ , а большее количество элементов для сортировки потребует большего $k$ для хранения их в памяти. ^[13]

Сортировки без сравнения
Имя	Лучший	Средний	Худший	Память	Стабильный	$п ≪ 2 к$	Примечания
Сортировка по ячейкам	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	Да	Да	Невозможно сортировать нецелые числа.
Сортировка сегментами (единые ключи)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	Да	Нет	Предполагает равномерное распределение элементов из домена в массиве. ^[14] Также не может сортироваться нецелые числа.
Сортировка сегментами (целочисленные ключи)	—	$n+r$	$n+r$	$n+r$	Да	Да	Если г равно ⁠ $O(n)$ ⁠ , то средняя временная сложность равна ⁠ $O(n)$ ⁠ . ^[15]
Подсчет сортировки	—	$n+r$	$n+r$	$n+r$	Да	Да	Если г равно ⁠ $O(n)$ ⁠ , то средняя временная сложность равна ⁠ $O(n)$ ⁠ . ^[14]
Поразрядная сортировка LSD	$n$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Да	Нет	${\frac {k}{d}}$ уровни рекурсии, 2 ^д для массива счетчиков. ^[14]^[15] В отличие от большинства видов распределения, здесь можно сортировать нецелые числа.
MSD поразрядная сортировка	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Да	Нет	Стабильная версия использует внешний массив размера $n$ для хранения всех ячеек. Как и вариант LSD, он может сортировать нецелые числа.
MSD Radix Sort (на месте)	—	$n\cdot {\frac {k}{1}}$	$n\cdot {\frac {k}{1}}$	$2^{1}$	Нет	Нет	d=1 для на месте, $k/1$ уровни рекурсии, нет массива счетчиков.
Спред-сортировка	$н$	$n\cdot {\frac {k}{d}}$	$n\cdot \left({{\frac {k}{s}}+d}\right)$	${\frac {k}{d}}\cdot 2^{d}$	Нет	Нет	Асимптотики основаны на предположении, что $n ≪ 2 к$ , но алгоритм этого не требует.
Пакетная сортировка	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	Нет	Нет	Имеет лучший постоянный коэффициент, чем поразрядная сортировка, для сортировки строк. Хотя в некоторой степени полагается на особенности часто встречающихся строк.
Флэш-сортировка	$н$	$n+r$	$n^{2}$	$н$	Нет	Нет	Требуется равномерное распределение элементов из домена в массиве для работы в линейном времени. Если распределение сильно искажено, оно может стать квадратичным, если базовая сортировка является квадратичной (обычно это сортировка вставками). Версия на месте не стабильна.
сортировка почтальона	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	—	Нет	Вариант сортировки по сегментам, который работает очень похоже на поразрядную сортировку MSD. Специально для нужд почтовой службы.

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

Другие

Некоторые алгоритмы медленны по сравнению с рассмотренными выше, например, богосортировка с неограниченным временем выполнения и марионеточная сортировка , у которой O ( n ^2.7) время работы. Эти виды обычно описываются в образовательных целях, чтобы продемонстрировать, как оценивается время работы алгоритмов. В следующей таблице описаны некоторые алгоритмы сортировки, которые непрактичны для реального использования в традиционных контекстах программного обеспечения из-за чрезвычайно низкой производительности или особых требований к оборудованию.

Имя	Лучший	Средний	Худший	Память	Стабильный	Сравнение	Другие примечания
Сортировка бисера	$н$	$С$	$С$	$n^{2}$	—	Нет	Работает только с положительными целыми числами. Для гарантированной работы требуется специализированное оборудование ⁠ $O(n)$ ⁠ время. Есть возможность программной реализации, но время работы составит ⁠ $O(S)$ ⁠ , где $S$ — сумма всех целых чисел, подлежащих сортировке; в случае малых целых чисел его можно считать линейным.
Сортировка слиянием-вставкой	$n\log n$ сравнения	$n\log n$ сравнения	$n\log n$ сравнения	Варьируется	Нет	Да	Делает очень мало сравнений в худшем случае по сравнению с другими алгоритмами сортировки. В основном представляет теоретический интерес из-за сложности реализации и неоптимального перемещения данных.
«Я не могу поверить, что это может сортировать» ^[16]	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Да	Примечателен прежде всего тем, что представляет собой ошибочную реализацию сортировки вставками или сортировки обменом .
Спагетти (Опрос) сортировка	$н$	$н$	$н$	$n^{2}$	Да	Опрос	Это аналоговый алгоритм сортировки последовательности элементов с линейным временем, требующий стекового пространства O ( n ), и сортировка является стабильной. Для этого требуется n параллельных процессоров. См. сортировку спагетти#Анализ .
Сортировочная сеть	Варьируется	Варьируется	Варьируется	Варьируется	Варьируется (стабильные сортировочные сети требуют большего количества сравнений)	Да	Порядок сравнений устанавливается заранее на основе фиксированного размера сети. ^{[ оспаривается – обсуждаем ]}
Битонический сортировщик	$\log ^{2}n$ параллельный	$\log ^{2}n$ параллельный	$n\log ^{2}n$ непараллельный	1	Нет	Да	Эффективный вариант Сортировочных сетей. ^{[ оспаривается – обсуждаем ]}
Богосорт	$н$	$(n\times n!)$	Неограниченный	1	Нет	Да	Случайное перетасовывание. Используется только в качестве примера, поскольку даже ожидаемое время выполнения в лучшем случае ужасно. ^[17] В худшем случае при использовании рандомизации нет ограничений, но детерминированная версия гарантирует $O(n\times n!)$ худший случай.
марионетка сортировка	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$н$	Нет	Да	Медленнее большинства алгоритмов сортировки (даже наивных) с временной сложностью $O (n журнал 3 / журнал 1,5) = О (п 2.7095...)$ Можно сделать стабильным, а также есть сортировочная сеть .
медленная сортировка	$n^{\Omega (\log n)}$	$n^{\Omega (\log n)}$	$n^{\Omega (\log n)}$	$н$	Нет	Да	Алгоритм «умножай и сдавай», аналогичный алгоритму «разделяй и властвуй» .
метод Франческини ^[18]	$-$	$n\log n$	$n\log n$	1	Да	Да	O $(n) .$ В худшем случае перемещает данные за Обладает асимптотическими границами идеального сравнения, но представляет лишь теоретический интерес.

Ученые-теоретики-компьютерщики подробно описали другие алгоритмы сортировки, которые обеспечивают временную сложность выше O ( n log n ), предполагая дополнительные ограничения, в том числе:

Алгоритм Торупа — рандомизированный алгоритм сортировки ключей из области конечного размера, занимающий $время O (n log log n)$ и пространство O ( n ). ^[19]
Алгоритм рандомизированной целочисленной сортировки, принимающий $O\left(n{\sqrt {\log \log n}}\right)$ ожидаемое время и пространство O ( n ). ^[20]
Один из авторов ранее упомянутого алгоритма также утверждает, что открыл алгоритм, принимающий $O\left(n{\sqrt {\log n}}\right)$ время и O ( n ) пространство, сортировка действительных чисел. ^[21] Далее утверждается, что без каких-либо дополнительных предположений на входных данных его можно изменить для достижения $O\left(n\log n/{\sqrt {\log \log n}}\right)$ время и O ( n ) пространство.

Популярные алгоритмы сортировки

Хотя существует большое количество алгоритмов сортировки, в практических реализациях преобладают лишь несколько алгоритмов. Сортировка вставками широко используется для небольших наборов данных, тогда как для больших наборов данных используется асимптотически эффективная сортировка, в первую очередь пирамидальная сортировка, сортировка слиянием или быстрая сортировка. В эффективных реализациях обычно используется гибридный алгоритм , сочетающий асимптотически эффективный алгоритм общей сортировки с сортировкой вставками для небольших списков в нижней части рекурсии. В тщательно настроенных реализациях используются более сложные варианты, такие как Timsort (сортировка слиянием, сортировка вставками и дополнительная логика), используемый в Android , Java и Python , и интросортировка (быстрая сортировка и пирамидальная сортировка), используемая (в вариантах) в некоторых сортировках C++. реализации и в .NET .

Для более ограниченных данных, таких как числа в фиксированном интервале, сортировки по распределению, широко используются такие как сортировка по подсчету или поразрядная сортировка. Пузырьковая сортировка и ее варианты редко используются на практике, но часто встречаются в преподавании и теоретических дискуссиях.

При физической сортировке объектов (например, документов, тестов или книг в алфавитном порядке) люди интуитивно обычно используют сортировку вставками для небольших наборов. Для более крупных наборов люди часто сначала группируют, например, по начальной букве, а множественное группирование позволяет практично сортировать очень большие наборы. Часто пространство обходится относительно дешево, например, когда объекты раскладываются по полу или на большой площади, но операции обходятся дорого, особенно перемещение объекта на большое расстояние — локальность привязки важна . Сортировка слиянием также практична для физических объектов, особенно потому, что можно использовать две руки, по одной для каждого списка для слияния, в то время как другие алгоритмы, такие как пирамидальная сортировка или быстрая сортировка, плохо подходят для использования человеком. Другие алгоритмы, такие как библиотечная сортировка , вариант сортировки вставками, оставляющий пробелы, также практичны для физического использования.

Простые сорта

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

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

Сортировка вставками — это простой алгоритм сортировки, который относительно эффективен для небольших списков и в основном отсортированных списков и часто используется как часть более сложных алгоритмов. Он работает, беря элементы из списка один за другим и вставляя их в правильное положение в новый отсортированный список, аналогично тому, как кто-то кладет деньги в свой кошелек. ^[22] В массивах новый список и оставшиеся элементы могут разделять пространство массива, но вставка требует больших затрат и требует сдвига всех последующих элементов на один. Сортировка Шелл — это вариант сортировки вставками, который более эффективен для больших списков.

Сортировка выбором

Сортировка выбором — это на месте сортировка сравнением . Он имеет O ( n ²) сложность, что делает ее неэффективной для больших списков и, как правило, работает хуже, чем аналогичная сортировка вставкой . Сортировка выбором отличается своей простотой, а также в определенных ситуациях имеет преимущества в производительности по сравнению с более сложными алгоритмами.

Алгоритм находит минимальное значение, заменяет его значением в первой позиции и повторяет эти шаги для оставшейся части списка. ^[23] Он выполняет не более n свопов и поэтому полезен там, где обмен очень дорог.

Эффективные сортировки

Практические алгоритмы общей сортировки почти всегда основаны на алгоритме со средней временной сложностью (и, как правило, в худшем случае) O( n log n ), из которых наиболее распространенными являются пирамидальная сортировка, сортировка слиянием и быстрая сортировка. У каждого из них есть свои преимущества и недостатки, наиболее значимым из которых является то, что простая реализация сортировки слиянием использует дополнительное пространство O( n ), а простая реализация быстрой сортировки требует O( n). ²) сложность наихудшего случая. Эти проблемы можно решить или улучшить за счет более сложного алгоритма.

Хотя эти алгоритмы асимптотически эффективны на случайных данных, для практической эффективности на реальных данных используются различные модификации. Во-первых, накладные расходы этих алгоритмов становятся значительными при работе с меньшими данными, поэтому часто используется гибридный алгоритм, который обычно переключается на сортировку вставкой, когда данные становятся достаточно маленькими. Во-вторых, алгоритмы часто плохо работают с уже отсортированными или почти отсортированными данными — они часто встречаются в реальных данных и могут быть отсортированы за время O( n ) с помощью соответствующих алгоритмов. Наконец, они также могут быть нестабильными , а стабильность часто является желательным свойством сорта. Поэтому часто используются более сложные алгоритмы, такие как Тимсорт (на основе сортировки слиянием) или интросорт (на основе быстрой сортировки с возвратом к пирамидальной сортировке).

Идет судьба

Сортировка слиянием позволяет легко объединить уже отсортированные списки в новый отсортированный список. Он начинается со сравнения каждых двух элементов (т. е. 1 с 2, затем 3 с 4...) и замены их местами, если первый должен идти после второго. Затем он объединяет каждый из полученных списков из двух в списки из четырех, затем объединяет эти списки из четырех и так далее; пока, наконец, два списка не будут объединены в окончательный отсортированный список. ^[24] Из описанных здесь алгоритмов это первый, который хорошо масштабируется для очень больших списков, поскольку время его работы в худшем случае составляет O( n log n ). Его также легко применить к спискам, а не только к массивам, поскольку требуется только последовательный, а не произвольный доступ. Однако он имеет дополнительную пространственную сложность O( n ) и включает большое количество копий в простых реализациях.

Сортировка слиянием сравнительно недавно стала популярнее для практических реализаций благодаря ее использованию в сложном алгоритме Timsort , который используется для стандартной процедуры сортировки в языках программирования Python. ^[25] и Java (начиная с JDK7 ^[26]). Сортировка слиянием сама по себе является стандартной процедурой в Perl . ^[27] среди прочего, и использовался в Java по крайней мере с 2000 года в JDK1.3 . ^[28]

пирамидальная сортировка

Пирамидальная сортировка — гораздо более эффективная версия сортировки выбором . Он также работает, определяя самый большой (или наименьший) элемент списка, помещая его в конец (или начало) списка, а затем продолжая работу с остальной частью списка, но эффективно выполняет эту задачу, используя структуру данных, называемую куча — особый тип двоичного дерева . ^[29] После того как список данных преобразован в кучу, корневой узел гарантированно будет самым большим (или наименьшим) элементом. Когда он удаляется и помещается в конец списка, куча переупорядочивается так, что самый большой оставшийся элемент перемещается в корень. При использовании кучи поиск следующего по величине элемента занимает время O(log n ) вместо O( n ) для линейного сканирования, как при простой сортировке выбором. Это позволяет пирамидальной сортировке выполняться за время O( n log n ), и это также сложность наихудшего случая.

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

Быстрая сортировка — это алгоритм «разделяй и властвуй» , основанный на операции разделения : для разделения массива элемент, называемый опорной точкой . выбирается ^[30]^[31] Все элементы, меньшие, чем опорная точка, перемещаются перед ней, а все элементы большего размера перемещаются после нее. Это можно сделать эффективно за линейное время и на месте . Затем меньший и больший подсписки рекурсивно сортируются. Это дает среднюю временную сложность O( n log n ) с низкими накладными расходами, и, таким образом, это популярный алгоритм. Эффективные реализации быстрой сортировки (с разделением на месте) обычно являются нестабильными и несколько сложными, но на практике являются одними из самых быстрых алгоритмов сортировки. Благодаря скромному использованию пространства O(log n ), быстрая сортировка является одним из самых популярных алгоритмов сортировки и доступна во многих стандартных библиотеках программирования.

Важным предостережением относительно быстрой сортировки является то, что ее производительность в худшем случае равна O( n ²); хотя это случается редко, в простых реализациях (выбор первого или последнего элемента в качестве опорного) это происходит для отсортированных данных, что является распространенным случаем. Таким образом, наиболее сложной проблемой быстрой сортировки является выбор хорошего опорного элемента, поскольку постоянно неудачный выбор опорных элементов может привести к значительному замедлению O( n ²) производительность, но хороший выбор опорных точек дает производительность O( n log n ), что является асимптотически оптимальным. Например, если на каждом шаге в качестве опорной выбрана медиана , то алгоритм работает за O( n log n ). Однако поиск медианы, например, с помощью медианы медиан алгоритма выбора , является операцией O ( n ) для несортированных списков и, следовательно, требует значительных накладных расходов при сортировке. На практике выбор случайного центра почти наверняка дает производительность O( n log n ).

Если важна гарантия производительности O( n log n ), есть простая модификация, позволяющая добиться этого. Идея Массера состоит в том, чтобы установить ограничение на максимальную глубину рекурсии. ^[32] Если этот предел превышен, сортировка продолжается с использованием алгоритма пирамидальной сортировки. Массер предположил, что предел должен быть $1+2\lfloor \log _{2}(n)\rfloor$ , что примерно в два раза превышает максимальную глубину рекурсии, которую можно было бы ожидать в среднем для случайно упорядоченного массива .

Шеллсорт

Сортировка Шелл была изобретена Дональдом Шеллом в 1959 году. ^[33] Он улучшает сортировку вставкой, перемещая неупорядоченные элементы более чем на одну позицию за раз. Концепция Shellsort заключается в том, что сортировка вставками выполняется в ⁠ $O(kn)$ ⁠ время, где k — наибольшее расстояние между двумя неуместными элементами. Это означает, что обычно они работают за O ( n ²), но для данных, которые в основном отсортированы и содержат лишь несколько неуместных элементов, они работают быстрее. Таким образом, если сначала сортировать элементы на большом расстоянии и постепенно сокращать промежуток между сортируемыми элементами, окончательная сортировка будет выполняться намного быстрее. Одну реализацию можно описать как организацию последовательности данных в двумерном массиве и последующую сортировку столбцов массива с использованием сортировки вставками.

Временная сложность сортировки Шелла в наихудшем случае является открытой проблемой и зависит от используемой последовательности пробелов с известной сложностью в диапазоне от O ( n ²) до O ( n ^4/3) и Θ( n log ² н ). Это, в сочетании с тем фактом, что Shellsort выполняется на месте , требует лишь относительно небольшого объема кода и не требует использования стека вызовов , делает его полезным в ситуациях, когда память ограничена, например, во встроенных системах. и ядра операционной системы .

Пузырьковая сортировка и варианты

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

Пузырьковая сортировка

Пузырьковая сортировка — это простой алгоритм сортировки. Алгоритм начинается с начала набора данных. Он сравнивает первые два элемента и, если первый больше второго, меняет их местами. Он продолжает делать это для каждой пары соседних элементов до конца набора данных. Затем он начинается снова с первых двух элементов, повторяя до тех пор, пока на последнем проходе не произойдет никаких замен. ^[34] Среднее время и производительность этого алгоритма в наихудшем случае составляют O( n ²), поэтому он редко используется для сортировки больших неупорядоченных наборов данных. Пузырьковая сортировка может использоваться для сортировки небольшого количества элементов (при этом ее асимптотическая неэффективность не является серьезным штрафом). Пузырьковую сортировку также можно эффективно использовать для списка любой длины, который практически отсортирован (т. е. элементы не располагаются не на своих местах). Например, если какое-либо количество элементов неуместно только на одну позицию (например, 0123546789 и 1032547698), обмен пузырьковой сортировкой приведет их в порядок на первом проходе, второй проход найдет все элементы по порядку, поэтому сортировка будет займите всего 2 н времени.

^[35]

Гребенчатая сортировка

Гребенчатая сортировка — это относительно простой алгоритм сортировки, основанный на пузырьковой сортировке и первоначально разработанный Влодзимежем Добосевичем в 1980 году. ^[36] Позже он был заново открыт и популяризирован Стивеном Лэйси и Ричардом Боксом в Byte статье журнала Magazine , опубликованной в апреле 1991 года. Основная идея состоит в том, чтобы исключить черепахи или небольшие значения в конце списка, поскольку при пузырьковой сортировке они замедляют сортировку. чрезвычайно. ( Кролики , большие значения в начале списка, не создают проблем при пузырьковой сортировке.) Это достигается путем первоначальной замены элементов, которые находятся на определенном расстоянии друг от друга в массиве, а не только замены элементов, если они находятся рядом с друг друга, а затем уменьшая выбранное расстояние до тех пор, пока оно не начнет работать как обычная пузырьковая сортировка. Таким образом, если сортировку Шелла можно рассматривать как обобщенную версию сортировки вставками, которая меняет местами элементы, расположенные на определенном расстоянии друг от друга, гребенчатую сортировку можно рассматривать как то же обобщение, применяемое к пузырьковой сортировке.

Обменная сортировка

Обменную сортировку иногда путают с пузырьковой сортировкой, хотя на самом деле алгоритмы различаются. ^[37]^[38] Сортировка по обмену работает путем сравнения первого элемента со всеми элементами над ним, меняя их местами, где это необходимо, тем самым гарантируя, что первый элемент соответствует окончательному порядку сортировки; затем он продолжает делать то же самое для второго элемента и так далее. Ему не хватает того преимущества, которое имеет пузырьковая сортировка, заключающаяся в обнаружении за один проход, если список уже отсортирован, но она может быть быстрее, чем пузырьковая сортировка, в постоянный коэффициент (на один проход меньше по сортируемым данным; вдвое меньше общего количества сравнений) в худшие ситуации. Как и любой простой O( n ²) сортировка может быть достаточно быстрой для очень маленьких наборов данных, хотя в целом сортировка вставкой будет быстрее.

Виды распределения

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

Подсчет сортировки

Сортировка подсчетом применима, когда известно, что каждый вход принадлежит определенному набору S возможностей. Алгоритм работает за время O(| S | + n ) и в памяти O(| S |), где n — длина входных данных. Он работает путем создания целочисленного массива размером | С | и использование i- го интервала для подсчета вхождений i- го члена S во входных данных. Затем каждый вход подсчитывается путем увеличения значения соответствующего интервала. После этого массив счетчиков обрабатывается циклически, чтобы упорядочить все входные данные по порядку. Этот алгоритм сортировки часто нельзя использовать, поскольку для того, чтобы алгоритм был эффективным, S должно быть достаточно малым, но он чрезвычайно быстр и демонстрирует отличное асимптотическое поведение при увеличении n . Его также можно изменить для обеспечения стабильного поведения.

Сортировка ведром

Сортировка сегментами — это алгоритм сортировки по принципу «разделяй и властвуй» , который обобщает сортировку подсчетом путем разделения массива на конечное число сегментов. Затем каждая корзина сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки корзин.

Сортировка по сегментам работает лучше всего, когда элементы набора данных равномерно распределены по всем сегментам.

Поразрядная сортировка

Поразрядная сортировка — это алгоритм, который сортирует числа путем обработки отдельных цифр. n чисел, состоящих из k цифр каждое, сортируются за время O( n · k ). Поразрядная сортировка может обрабатывать цифры каждого числа, начиная с младшей значащей цифры (LSD) или начиная со старшей значащей цифры (MSD). Алгоритм LSD сначала сортирует список по младшему разряду, сохраняя при этом их относительный порядок, используя стабильную сортировку. Затем он сортирует их по следующей цифре и так далее от наименее значимого к наиболее значимому, в результате чего получается отсортированный список. В то время как поразрядная сортировка LSD требует использования стабильной сортировки, алгоритм поразрядной сортировки MSD этого не требует (если не требуется стабильная сортировка). Поразрядная сортировка MSD на месте не стабильна. обычно Алгоритм сортировки подсчетом используется внутри поразрядной сортировки. Гибридный подход к сортировке, например использование сортировки вставками для небольших ячеек, значительно повышает производительность поразрядной сортировки.

Шаблоны использования памяти и сортировка индексов

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

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

Один из способов обойти эту проблему, который хорошо работает, когда сложные записи (например, в реляционной базе данных ) сортируются по относительно небольшому ключевому полю, — это создать индекс в массиве, а затем отсортировать его, а не весь массив. множество. (Отсортированную версию всего массива можно затем создать за один проход, читая из индекса, но часто даже в этом нет необходимости, поскольку достаточно иметь отсортированный индекс.) Поскольку индекс намного меньше, чем весь массив, он может легко помещается в памяти там, где не помещается весь массив, эффективно устраняя проблему замены дисков. Эту процедуру иногда называют «сортировкой тегов». ^[39]

Другой метод решения проблемы размера памяти — использование внешней сортировки . Например, один из способов — объединить два алгоритма таким образом, чтобы использовать преимущества каждого из них для повышения общей производительности. Например, массив может быть разделен на фрагменты, размер которых помещается в ОЗУ, содержимое каждого фрагмента сортируется с использованием эффективного алгоритма (например, быстрой сортировки ), а результаты объединяются с использованием k -способа слияния, аналогичного тому, который используется в сортировка слиянием . Это быстрее, чем выполнять сортировку слиянием или быструю сортировку по всему списку. ^[40]^[41]

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

Связанные алгоритмы

Связанные проблемы включают приблизительную сортировку (сортировку последовательности с точностью до определенного порядка ), частичную сортировку (сортировку только k наименьших элементов списка или поиск k наименьших элементов, но неупорядоченных) и отбор (вычисление k наименьших элементов списка). наименьший элемент). Их можно неэффективно решить с помощью полной сортировки, но существуют более эффективные алгоритмы, часто получаемые путем обобщения алгоритма сортировки. Наиболее ярким примером является быстрый выбор , который связан с быстрой сортировкой . И наоборот, некоторые алгоритмы сортировки могут быть получены путем многократного применения алгоритма выбора; Быструю сортировку и быстрый выбор можно рассматривать как одно и то же поворотное движение, отличающееся только тем, выполняется ли оно с обеих сторон (быстрая сортировка, разделяй и властвуй ) или с одной стороны (быстрый выбор, уменьшение и властвуй ).

Своеобразной противоположностью алгоритма сортировки является алгоритм перетасовки . Они принципиально отличаются, поскольку требуют источника случайных чисел. Перетасовку также можно реализовать с помощью алгоритма сортировки, а именно случайной сортировки: присвоения случайного числа каждому элементу списка и последующей сортировки на основе случайных чисел. Однако на практике этого обычно не делают, и существует хорошо известный простой и эффективный алгоритм перетасовки: перетасовка Фишера-Йейтса .

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

См. также

Сопоставление – сбор письменной информации в стандартном порядке.
K-отсортированная последовательность
Преобразование Шварца - идиома программирования для эффективной сортировки списка по вычисленному ключу.
Алгоритм поиска – любой алгоритм, решающий задачу поиска.
Квантовая сортировка - алгоритмы сортировки для квантовых компьютеров.

Ссылки

^ «Познакомьтесь с« дамами-холодильниками », которые запрограммировали ENIAC» . Ментальная нить . 13 октября 2013 г. Архивировано из оригинала 08.10.2018 . Проверено 16 июня 2016 г.
^ Лор, Стив (17 декабря 2001 г.). «Фрэнсис Э. Холбертон, 84 года, один из первых программистов» . Нью-Йорк Таймс. Архивировано из оригинала 16 декабря 2014 года . Проверено 16 декабря 2014 г.
^ Демут, Ховард Б. (1956). Электронная сортировка данных (кандидатская диссертация). Стэнфордский университет. ПроКвест 301940891 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009), «8», «Введение в алгоритмы» (3-е изд.), Кембридж, Массачусетс: MIT Press, стр. 167, ISBN 978-0-262-03293-3
^ Хуанг, Британская Колумбия; Лэнгстон, Массачусетс (декабрь 1992 г.). «Быстрое стабильное слияние и сортировка в постоянном дополнительном пространстве». Вычислить. Дж. 35 (6): 643–650. CiteSeerX 10.1.1.54.8381 . дои : 10.1093/comjnl/35.6.643 .
^ Аджтай, М. ; Комлос, Дж .; Семереди, Э. (1983). O $(n log n)$ Сортировочная сеть . СТОК '83. Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 1–9. дои : 10.1145/800061.808726 . ISBN 0-89791-099-0 .
^ Проф. Э. Рам. «Сортьеверфарен» (PDF) . Dbs.uni-leipzig.de . Архивировано (PDF) из оригинала 23 августа 2022 года . Проверено 1 марта 2022 г.
^ Ким, PS; Куцнер, А. (2008). Стабильное слияние на месте на основе соотношений . TAMC 2008. Теория и применение моделей вычислений . ЛНКС . Том. 4978. стр. 246–257. CiteSeerX 10.1.1.330.2641 . дои : 10.1007/978-3-540-79228-4_22 . ISBN 978-3-540-79227-7 .
^ Седжвик, Роберт (1 сентября 1998 г.). Алгоритмы на языке C: основы, структуры данных, сортировка, поиск, части 1–4 (3-е изд.). Пирсон Образование. ISBN 978-81-317-1291-7 . Проверено 27 ноября 2012 г.
^ Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Комм. АКМ . 21 (10): 847–857. дои : 10.1145/359619.359631 . S2CID 10020756 .
^ «СОРТИРОВКА ВЫБОРОМ (Java, C++) – Алгоритмы и структуры данных» . Алголист.нет . Архивировано из оригинала 9 декабря 2012 года . Проверено 14 апреля 2018 г.
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «8», « Введение в алгоритмы» (2-е изд.), Кембридж, Массачусетс: MIT Press, стр. 165, ИСБН 0-262-03293-7
^ Нильссон, Стефан (2000). «Самый быстрый алгоритм сортировки?» . Доктор Добб . Архивировано из оригинала 8 июня 2019 г. Проверено 23 ноября 2015 г.
^ Перейти обратно: ^а ^б ^с Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 .
^ Перейти обратно: ^а ^б Гудрич, Майкл Т .; Тамассия, Роберто (2002). «4.5 Ведрообразная и поразрядная сортировка». Разработка алгоритмов: основы, анализ и примеры из Интернета . Джон Уайли и сыновья. стр. 241–243. ISBN 978-0-471-38365-9 .
^ Фунг, Стэнли П.Ю. (3 октября 2021 г.). «Это самый простой (и самый удивительный) алгоритм сортировки?». arXiv : 2110.01111 [ cs.DS ].
^ Грубер, Х.; Хольцер, М.; Руепп, О. (2007), «Медленная сортировка: анализ извращенно ужасных алгоритмов рандомизированной сортировки», 4-я Международная конференция по развлечениям с алгоритмами, Кастильончелло, Италия, 2007 (PDF) , Конспекты лекций по информатике, том. 4475, Springer-Verlag, стр. 183–197, номер документа : 10.1007/978-3-540-72914-3_17 , ISBN. 978-3-540-72913-6 , заархивировано (PDF) из оригинала 29 сентября 2020 г. , получено 27 июня 2020 г.
^ Франческини, Г. (июнь 2007 г.). «Стабильная сортировка на месте, с помощью O(n log n) сравнений и O(n) перемещений». Теория вычислительных систем . 40 (4): 327–353. дои : 10.1007/s00224-006-1311-1 .
^ Торуп, М. (февраль 2002 г.). «Рандомизированная сортировка во времени O (n log log n) и линейном пространстве с использованием сложения, сдвига и побитовых логических операций». Журнал алгоритмов . 42 (2): 205–230. дои : 10.1006/jagm.2002.1211 . S2CID 9700543 .
^ Хан, Ицзе; Торуп, М. (2002). Целочисленная сортировка за ожидаемое время O(n√(log log n)) и линейное пространство . 43-й ежегодный симпозиум IEEE по основам информатики . стр. 135–144. дои : 10.1109/SFCS.2002.1181890 . ISBN 0-7695-1822-2 .
^ Хан, Ицзе (01 апреля 2020 г.). «Сортировка действительных чисел во времени $$O\big (n\sqrt{\log n}\big)$$ и линейном пространстве» . Алгоритмика . 82 (4): 966–978. дои : 10.1007/s00453-019-00626-0 . ISSN 1432-0541 .
^ Вирт, Никлаус (1986). Алгоритмы и структуры данных . Река Аппер-Сэддл, Нью-Джерси: Прентис-Холл. стр. 76–77. ISBN 978-0130220059 .
^ Вирт 1986 , стр. 79–80.
^ Вирт 1986 , стр. 101–102.
^ «Оригинальное описание тимсорта Тимом Питерсом» . python.org . Архивировано из оригинала 22 января 2018 года . Проверено 14 апреля 2018 г.
^ «TimSort.java OpenJDK» . java.net . Архивировано из оригинала 14 августа 2011 года . Проверено 14 апреля 2018 г.
^ «сортировка – perldoc.perl.org» . perldoc.perl.org . Архивировано из оригинала 14 апреля 2018 года . Проверено 14 апреля 2018 г.
^ Сортировка слиянием в Java 1.3 , Sun. Архивировано 4 марта 2009 г. в Wayback Machine.
^ Вирт 1986 , стр. 87–89.
^ Вирт 1986 , с. 93
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009), Введение в алгоритмы (3-е изд.), Кембридж, Массачусетс: MIT Press, стр. 171–172, ISBN. 978-0262033848
^ Массер, Дэвид Р. (1997), «Алгоритмы интроспективной сортировки и выбора», Software: Practice and Experience , 27 (8): 983–993, doi : 10.1002/(SICI)1097-024X(199708)27:8<983 ::AID-SPE117>3.0.CO;2-#
^ Шелл, Д.Л. (1959). «Процедура высокоскоростной сортировки» (PDF) . Коммуникации АКМ . 2 (7): 30–32. дои : 10.1145/368370.368387 . S2CID 28572656 . Архивировано из оригинала (PDF) 30 августа 2017 г. Проверено 23 марта 2020 г.
^ Вирт 1986 , стр. 81–82.
^ "ядро/группы.c" . Гитхаб . Архивировано из оригинала 25 февраля 2021 г. Проверено 5 мая 2012 г.
^ Брейова, Б. (15 сентября 2001 г.). «Анализ вариантов сортировки Шелла». Инф. Процесс. Летт. 79 (5): 223–227. дои : 10.1016/S0020-0190(00)00223-4 .
^ «Алгоритм обменной сортировки» . Учебники по программированию на CodingUnit . Архивировано из оригинала 10 июля 2021 г. Проверено 10 июля 2021 г.
^ «Обменная сортировка» . JavaBitsNotebook.com . Архивировано из оригинала 10 июля 2021 г. Проверено 10 июля 2021 г.
^ «Определение сортировки тегов из энциклопедии журнала PC Magazine» . Pcmag.com . Архивировано из оригинала 6 октября 2012 года . Проверено 14 апреля 2018 г.
^ Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 248–379.
^ Эллис Горовиц и Сартадж Сахни , Основы структур данных , Х. Фриман и компания, ISBN 0-7167-8042-9 .

Дальнейшее чтение

Кнут, Дональд Э. (1998), Сортировка и поиск , Искусство компьютерного программирования, том. 3 (2-е изд.), Бостон: Аддисон-Уэсли, ISBN 0-201-89685-0
Седжвик, Роберт (1980), «Эффективная сортировка с помощью компьютера: введение» , «Вычислительная вероятность » , Нью-Йорк: Academic Press, стр. 101–130 , ISBN 0-12-394680-8

Внешние ссылки

Сортировка анимаций алгоритмов в Wayback Machine (архивировано 3 марта 2015 г.).
Алгоритмы последовательной и параллельной сортировки . Объяснения и анализ многих алгоритмов сортировки.
Словарь алгоритмов, структур данных и проблем - Словарь алгоритмов, методов, общих функций и проблем.
Слегка скептический взгляд на алгоритмы сортировки – обсуждает несколько классических алгоритмов и продвигает альтернативы алгоритму быстрой сортировки .
15 алгоритмов сортировки за 6 минут (Youtube) – Визуализация и «аудибилизация» 15 алгоритмов сортировки за 6 минут.
Последовательность A036604 в базе данных OEIS под названием «Сортировка чисел: минимальное количество сравнений, необходимых для сортировки n элементов» – выполняется алгоритмом Форда – Джонсона .
Алгоритмы сортировки, используемые на известных картинах (Youtube) — визуализация алгоритмов сортировки на многих известных картинах.
Сравнение алгоритмов сортировки — запускает серию тестов 9 основных алгоритмов сортировки с использованием Python timeit и Google Colab .

[refrigerator-1] «Познакомьтесь с« дамами-холодильниками », которые запрограммировали ENIAC» . Ментальная нить . 13 октября 2013 г. Архивировано из оригинала 08.10.2018 . Проверено 16 июня 2016 г.

[NYTimes-2] Лор, Стив (17 декабря 2001 г.). «Фрэнсис Э. Холбертон, 84 года, один из первых программистов» . Нью-Йорк Таймс. Архивировано из оригинала 16 декабря 2014 года . Проверено 16 декабря 2014 г.

[3] Демут, Ховард Б. (1956). Электронная сортировка данных (кандидатская диссертация). Стэнфордский университет. ПроКвест 301940891 .

[4] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009), «8», «Введение в алгоритмы» (3-е изд.), Кембридж, Массачусетс: MIT Press, стр. 167, ISBN 978-0-262-03293-3

[5] Хуанг, Британская Колумбия; Лэнгстон, Массачусетс (декабрь 1992 г.). «Быстрое стабильное слияние и сортировка в постоянном дополнительном пространстве». Вычислить. Дж. 35 (6): 643–650. CiteSeerX 10.1.1.54.8381 . дои : 10.1093/comjnl/35.6.643 .

[6] Аджтай, М. ; Комлос, Дж .; Семереди, Э. (1983). O $(n log n)$ Сортировочная сеть . СТОК '83. Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . стр. 1–9. дои : 10.1145/800061.808726 . ISBN 0-89791-099-0 .

[7] Проф. Э. Рам. «Сортьеверфарен» (PDF) . Dbs.uni-leipzig.de . Архивировано (PDF) из оригинала 23 августа 2022 года . Проверено 1 марта 2022 г.

[8] Ким, PS; Куцнер, А. (2008). Стабильное слияние на месте на основе соотношений . TAMC 2008. Теория и применение моделей вычислений . ЛНКС . Том. 4978. стр. 246–257. CiteSeerX 10.1.1.330.2641 . дои : 10.1007/978-3-540-79228-4_22 . ISBN 978-3-540-79227-7 .

[9] Седжвик, Роберт (1 сентября 1998 г.). Алгоритмы на языке C: основы, структуры данных, сортировка, поиск, части 1–4 (3-е изд.). Пирсон Образование. ISBN 978-81-317-1291-7 . Проверено 27 ноября 2012 г.

[sedgewickQsortPaper-10] Седжвик, Р. (1978). «Реализация программ быстрой сортировки». Комм. АКМ . 21 (10): 847–857. дои : 10.1145/359619.359631 . S2CID 10020756 .

[11] «СОРТИРОВКА ВЫБОРОМ (Java, C++) – Алгоритмы и структуры данных» . Алголист.нет . Архивировано из оригинала 9 декабря 2012 года . Проверено 14 апреля 2018 г.

[12] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «8», « Введение в алгоритмы» (2-е изд.), Кембридж, Массачусетс: MIT Press, стр. 165, ИСБН 0-262-03293-7

[13] Нильссон, Стефан (2000). «Самый быстрый алгоритм сортировки?» . Доктор Добб . Архивировано из оригинала 8 июня 2019 г. Проверено 23 ноября 2015 г.

[clrs-14] Перейти обратно: ^а ^б ^с Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 .

[gt-15] Перейти обратно: ^а ^б Гудрич, Майкл Т .; Тамассия, Роберто (2002). «4.5 Ведрообразная и поразрядная сортировка». Разработка алгоритмов: основы, анализ и примеры из Интернета . Джон Уайли и сыновья. стр. 241–243. ISBN 978-0-471-38365-9 .

[16] Фунг, Стэнли П.Ю. (3 октября 2021 г.). «Это самый простой (и самый удивительный) алгоритм сортировки?». arXiv : 2110.01111 [ cs.DS ].

[Fun07-17] Грубер, Х.; Хольцер, М.; Руепп, О. (2007), «Медленная сортировка: анализ извращенно ужасных алгоритмов рандомизированной сортировки», 4-я Международная конференция по развлечениям с алгоритмами, Кастильончелло, Италия, 2007 (PDF) , Конспекты лекций по информатике, том. 4475, Springer-Verlag, стр. 183–197, номер документа : 10.1007/978-3-540-72914-3_17 , ISBN. 978-3-540-72913-6 , заархивировано (PDF) из оригинала 29 сентября 2020 г. , получено 27 июня 2020 г.

[18] Франческини, Г. (июнь 2007 г.). «Стабильная сортировка на месте, с помощью O(n log n) сравнений и O(n) перемещений». Теория вычислительных систем . 40 (4): 327–353. дои : 10.1007/s00224-006-1311-1 .

[19] Торуп, М. (февраль 2002 г.). «Рандомизированная сортировка во времени O (n log log n) и линейном пространстве с использованием сложения, сдвига и побитовых логических операций». Журнал алгоритмов . 42 (2): 205–230. дои : 10.1006/jagm.2002.1211 . S2CID 9700543 .

[20] Хан, Ицзе; Торуп, М. (2002). Целочисленная сортировка за ожидаемое время O(n√(log log n)) и линейное пространство . 43-й ежегодный симпозиум IEEE по основам информатики . стр. 135–144. дои : 10.1109/SFCS.2002.1181890 . ISBN 0-7695-1822-2 .

[21] Хан, Ицзе (01 апреля 2020 г.). «Сортировка действительных чисел во времени $$O\big (n\sqrt{\log n}\big)$$ и линейном пространстве» . Алгоритмика . 82 (4): 966–978. дои : 10.1007/s00453-019-00626-0 . ISSN 1432-0541 .

[22] Вирт, Никлаус (1986). Алгоритмы и структуры данных . Река Аппер-Сэддл, Нью-Джерси: Прентис-Холл. стр. 76–77. ISBN 978-0130220059 .

[23] Вирт 1986 , стр. 79–80.

[24] Вирт 1986 , стр. 101–102.

[25] «Оригинальное описание тимсорта Тимом Питерсом» . python.org . Архивировано из оригинала 22 января 2018 года . Проверено 14 апреля 2018 г.

[26] «TimSort.java OpenJDK» . java.net . Архивировано из оригинала 14 августа 2011 года . Проверено 14 апреля 2018 г.

[27] «сортировка – perldoc.perl.org» . perldoc.perl.org . Архивировано из оригинала 14 апреля 2018 года . Проверено 14 апреля 2018 г.

[mergesort_in_jdk13-28] Сортировка слиянием в Java 1.3 , Sun. Архивировано 4 марта 2009 г. в Wayback Machine.

[29] Вирт 1986 , стр. 87–89.

[30] Вирт 1986 , с. 93

[31] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009), Введение в алгоритмы (3-е изд.), Кембридж, Массачусетс: MIT Press, стр. 171–172, ISBN. 978-0262033848

[32] Массер, Дэвид Р. (1997), «Алгоритмы интроспективной сортировки и выбора», Software: Practice and Experience , 27 (8): 983–993, doi : 10.1002/(SICI)1097-024X(199708)27:8<983 ::AID-SPE117>3.0.CO;2-#

[Shell-33] Шелл, Д.Л. (1959). «Процедура высокоскоростной сортировки» (PDF) . Коммуникации АКМ . 2 (7): 30–32. дои : 10.1145/368370.368387 . S2CID 28572656 . Архивировано из оригинала (PDF) 30 августа 2017 г. Проверено 23 марта 2020 г.

[34] Вирт 1986 , стр. 81–82.

[35] "ядро/группы.c" . Гитхаб . Архивировано из оригинала 25 февраля 2021 г. Проверено 5 мая 2012 г.

[BB-36] Брейова, Б. (15 сентября 2001 г.). «Анализ вариантов сортировки Шелла». Инф. Процесс. Летт. 79 (5): 223–227. дои : 10.1016/S0020-0190(00)00223-4 .

[37] «Алгоритм обменной сортировки» . Учебники по программированию на CodingUnit . Архивировано из оригинала 10 июля 2021 г. Проверено 10 июля 2021 г.

[38] «Обменная сортировка» . JavaBitsNotebook.com . Архивировано из оригинала 10 июля 2021 г. Проверено 10 июля 2021 г.

[39] «Определение сортировки тегов из энциклопедии журнала PC Magazine» . Pcmag.com . Архивировано из оригинала 6 октября 2012 года . Проверено 14 апреля 2018 г.

[40] Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 248–379.

[41] Эллис Горовиц и Сартадж Сахни , Основы структур данных , Х. Фриман и компания, ISBN 0-7167-8042-9 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

v т и Структуры данных и алгоритмы
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms

v т и Алгоритмы сортировки
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort