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

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

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

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

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

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

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

С самого начала компьютерных вычислений проблема сортировки привлекала большое количество исследований, возможно, из-за сложности ее эффективного решения, несмотря на ее простую и знакомую формулировку. Среди авторов первых алгоритмов сортировки примерно в 1951 году была Бетти Холбертон , работавшая над ENIAC и UNIVAC . Пузырьковая сортировка была проанализирована еще в 1956 году. Асимптотически оптимальные алгоритмы известны с середины 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 — количество записей, подлежащих сортировке. В столбцах «Лучший», «Средний» и «Худший» указана временная сложность в каждом случае при условии, что длина каждого ключа постоянна и, следовательно, все сравнения, замены и другие операции могут выполняться за постоянное время. «Память» обозначает объем дополнительной памяти, необходимой в дополнение к той, которая используется самим списком, при том же предположении. Перечисленные время выполнения и требования к памяти указаны внутри нотации большого О , поэтому основание логарифмов не имеет значения. обозначений Журнал ² n означает (log n ) ² .

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

Ниже представлена ​​таблица сравнения сортов . Сортировка сравнением не может работать лучше, чем O ( n log n ) . в среднем

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

Имя	Лучший	Средний	Худший	Память	Стабильный	Метод	Другие примечания
Сортировка слиянием на месте	—	—	$n\log ^{2}n$	1	Да	Слияние	Может быть реализована как стабильная сортировка на основе стабильного слияния на месте.
пирамидальная сортировка	$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 ) с использованием алгоритма трех венгров).
Сортировка турниров	$n\log n$	$n\log n$	$n\log n$	н	Нет	Выбор	Вариант пирамидальной сортировки.
Сортировка дерева	$n\log n$	$n\log n$	$n\log n$(сбалансированный)	н	Да	Вставка	При использовании самобалансирующегося двоичного дерева поиска .
Блочная сортировка	н	$n\log n$	$n\log n$	1	Да	Вставка и объединение	Объедините блочную $O(n)$ алгоритм слияния на месте с сортировкой слиянием снизу вверх .
Гладкая сортировка	н	$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 ) . стека
Сортировка библиотеки	$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)$ дополнительное пространство при использовании связанных списков или при использовании варианта сортировки вставками вместо замены двух элементов.
Обменная сортировка	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Обмен	Небольшой размер кода.
Циклическая сортировка	$n^{2}$	$n^{2}$	$n^{2}$	1	Нет	Выбор	На месте с теоретически оптимальным количеством операций записи.

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

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

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

Имя	Лучший	Средний	Худший	Память	Стабильный	п ≪ 2 к	Примечания
Сортировка по ячейкам	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	Да	Да	Невозможно сортировать нецелые числа.
Сортировка сегментами (единые ключи)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	Да	Нет	Предполагает равномерное распределение элементов из домена в массиве. Также не может сортироваться нецелые числа.
Сортировка сегментами (целочисленные ключи)	—	$n+r$	$n+r$	$n+r$	Да	Да	Если р ​ $O(n)$, то средняя временная сложность равна $O(n)$.
Подсчет сортировки	—	$n+r$	$n+r$	$n+r$	Да	Да	Если р ​ $O(n)$, то средняя временная сложность равна $O(n)$.
Поразрядная сортировка LSD	$n$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Да	Нет	${\frac {k}{d}}$ уровни рекурсии, 2 д для массива счетчиков. В отличие от большинства видов распределения, здесь можно сортировать нецелые числа.
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$ сравнения	Варьируется	Нет	Да	Делает очень мало сравнений в худшем случае по сравнению с другими алгоритмами сортировки. В основном представляет теоретический интерес из-за сложности реализации и неоптимального перемещения данных.
«Я не могу поверить, что это может сортировать»	$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	Нет	Да	Случайное перетасовывание. Используется только в качестве примера, поскольку даже ожидаемое время выполнения в лучшем случае ужасно. В худшем случае при использовании рандомизации нет ограничений, но детерминированная версия гарантирует $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)}$	н	Нет	Да	Алгоритм «умножай и сдавай», аналогичный алгоритму «разделяй и властвуй» .
метод Франческини	$-$	$n\log n$	$n\log n$	1	Да	Да	O ( n ) . В худшем случае перемещает данные Обладает асимптотическими границами идеального сравнения, но представляет лишь теоретический интерес.

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

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

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

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

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

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

Простые сортировки

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

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

Основная статья: Сортировка вставками

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

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

Основная статья: Сортировка выбором

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

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

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

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

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

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

Основная статья: Сортировка слиянием

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

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

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

Основная статья: Пирамидальная сортировка

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

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

Основная статья: Быстрая сортировка

Быстрая сортировка — это алгоритм «разделяй и властвуй» , основанный на операции разделения : для разделения массива элемент, называемый опорной точкой . выбирается Все элементы, меньшие, чем опорная точка, перемещаются перед ней, а все элементы большего размера перемещаются после нее. Это можно сделать эффективно за линейное время и на месте . Затем меньший и больший подсписки рекурсивно сортируются. Это дает среднюю временную сложность 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 ), есть простая модификация, позволяющая добиться этого. Идея Массера состоит в том, чтобы установить ограничение на максимальную глубину рекурсии. Если этот предел превышен, сортировка продолжается с использованием алгоритма пирамидальной сортировки. Массер предположил, что предел должен быть $1+2\lfloor \log _{2}(n)\rfloor$, что примерно в два раза превышает максимальную глубину рекурсии, которую можно было бы ожидать в среднем для случайно упорядоченного массива .

Шеллсорт

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

Основная статья: Шеллсорт

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

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

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

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

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

Пузырьковая сортировка — алгоритм сортировки, который непрерывно проходит по списку, меняя местами элементы, пока они не появятся в правильном порядке.

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

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

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

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

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

Сортировка по обмену

Обменную сортировку иногда путают с пузырьковой сортировкой, хотя на самом деле алгоритмы различаются. Сортировка по обмену работает путем сравнения первого элемента со всеми элементами над ним, меняя их местами, где это необходимо, тем самым гарантируя, что первый элемент соответствует окончательному порядку сортировки; затем он продолжает делать то же самое для второго элемента и так далее. Ему не хватает того преимущества, которое имеет пузырьковая сортировка, заключающаяся в обнаружении за один проход, если список уже отсортирован, но она может быть быстрее, чем пузырьковая сортировка, в постоянный коэффициент (на один проход меньше по сортируемым данным; вдвое меньше общего количества сравнений) в худшие ситуации. Как и любой простой 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 на месте не стабильна. обычно Алгоритм сортировки подсчетом используется внутри поразрядной сортировки. Гибридный подход к сортировке, например использование сортировки вставками для небольших ячеек, значительно повышает производительность поразрядной сортировки.

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

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

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

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

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

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

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

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

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

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

См. также

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

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

• Кнут, Дональд Э. (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 .