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

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

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

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

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

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

История [ править ]

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

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

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

Классификация [ править ]

Алгоритмы сортировки часто классифицируются по:

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

Стабильность [ править ]

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

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

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

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

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

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

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

Сравнение алгоритмов [ править ]

В этой таблице n - количество сортируемых записей. Столбцы «Среднее» и «Худшее» дают временную сложность в каждом случае при условии, что длина каждого ключа постоянна, и, следовательно, все сравнения, замены и другие необходимые операции могут выполняться за постоянное время. «Память» обозначает объем вспомогательной памяти, необходимый сверх того, который используется самим списком, при том же предположении. Следует понимать, что время выполнения и требования к памяти, перечисленные ниже, находятся в нотации большой O , поэтому основание логарифмов не имеет значения; запись log ² n означает (log n ) ² .

Сортировка сравнения [ править ]

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

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

Имя	Лучший	Средний	Наихудший	объем памяти	Стабильный	Метод	Прочие примечания
Быстрая сортировка	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle \log n}$	Нет	Разбиение	Быстрая сортировка обычно выполняется на месте с объемом стека O (log n ) . [5] [6]
Сортировка слиянием	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	п	да	Слияние	Высокая степень распараллеливания (до O (log n ) с использованием алгоритма трех венгров). [7]
Сортировка слиянием на месте	-	-	${\displaystyle n\log ^{2}n}$	1	да	Слияние	Может быть реализована как стабильная сортировка на основе стабильного слияния на месте. [8]
Интросорт	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle \log n}$	Нет	Разбиение и выбор	Используется в нескольких реализациях STL .
Heapsort	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	Нет	Выбор
Вставка сортировки	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	да	Вставка	O ( n + d ) , в худшем случае по последовательностям, имеющим d инверсий .
Блочная сортировка	п	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	да	Вставка и слияние	Объедините блочный алгоритм слияния на месте [9] с сортировкой слияния снизу вверх .${\displaystyle O(n)}$
Quadsort	п	${\displaystyle n\log n}$	${\displaystyle n\log n}$	п	да	Слияние	Использует сортировочную сеть с 4 входами . [10]
Тимсорт	п	${\displaystyle n\log n}$	${\displaystyle n\log n}$	п	да	Вставка и слияние	Выполняет n сравнений, когда данные уже отсортированы или отсортированы обратным образом.
Выборочная сортировка	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Нет	Выбор	Стабильно с дополнительным пространством или при использовании связанных списков. [11]${\displaystyle O(n)}$
Cubesort	п	${\displaystyle n\log n}$	${\displaystyle n\log n}$	п	да	Вставка	Выполняет n сравнений, когда данные уже отсортированы или отсортированы обратным образом.
Shellsort	${\displaystyle n\log n}$	${\displaystyle n^{4/3}}$	${\displaystyle n^{3/2}}$	1	Нет	Вставка	Небольшой размер кода.
Пузырьковая сортировка	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	да	Обмен	Крошечный размер кода.
Сортировка дерева	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$(сбалансированный)	п	да	Вставка	При использовании самобалансирующегося двоичного дерева поиска .
Цикл сортировки	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Нет	Вставка	На месте с теоретически оптимальным количеством операций записи.
Сортировка библиотеки	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	п	Нет	Вставка	Аналогично сортировке вставкой с разрывом. Это требует случайной перестановки входных данных, чтобы гарантировать с высокой вероятностью временные границы, что делает его нестабильным.
Сортировка терпения	п	-	${\displaystyle n\log n}$	п	Нет	Вставка и выбор	Находит все самые длинные возрастающие подпоследовательности за O ( n log n ) .
Smoothsort	п	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	Нет	Выбор	Адаптивный вариант пирамидальной сортировки основан на последовательности Leonardo , а не традиционной двоичной кучи .
Сортировка прядей	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	п	да	Выбор
Сортировка турнира	${\displaystyle n\log n}$	${\displaystyle n\log n}$	${\displaystyle n\log n}$	n [12]	Нет	Выбор	Вариант сортировки кучи.
Сорт коктейльный шейкер	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	да	Обмен	Вариант Bubblesort, который хорошо работает с небольшими значениями в конце списка
Сортировка гребней	${\displaystyle n\log n}$	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	Нет	Обмен	В среднем быстрее, чем пузырьковая сортировка.
Сортировка гномов	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	да	Обмен	Крошечный размер кода.
Неупорядочить сортировку [13]	п	кн	кн	п	Нет	Распространение и слияние	Обмены не производятся. Параметр k пропорционален энтропии на входе. k = 1 для упорядоченного или обратного ввода.
Метод Франческини [14]	-	${\displaystyle n\log n}$	${\displaystyle n\log n}$	1	да	?	Выполняет O ( n ) перемещений данных.
Нечетно-четная сортировка	п	${\displaystyle n^{2}}$	${\displaystyle n^{2}}$	1	да	Обмен	Легко запускается на параллельных процессорах.

Сортировки без сравнения [ править ]

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

Несравнительные сорта

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

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

Другое [ править ]

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

Имя	Лучший	Средний	Наихудший	объем памяти	Стабильный	Сравнение	Прочие примечания
Сортировка бисера	п	S	S	${\displaystyle n^{2}}$	Нет данных	Нет	Работает только с положительными целыми числами. Требуется специализированное оборудование для гарантированной работы. Возможна программная реализация, но время выполнения будет , где S - сумма всех целых чисел, подлежащих сортировке, в случае малых целых чисел его можно считать линейным.${\displaystyle O(n)}$${\displaystyle O(S)}$
Блины простые	-	п	п	${\displaystyle \log n}$	Нет	да	Счетчик - это количество переворотов.
Сортировка спагетти (опрос)	п	п	п	${\displaystyle n^{2}}$	да	Опрос	Это аналоговый алгоритм с линейным временем для сортировки последовательности элементов, требующий пространства стека O ( n ), и сортировка является стабильной. Для этого требуется n параллельных процессоров. См. Сорт спагетти # Анализ .
Сортировочная сеть	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle n\log ^{2}n}$	Варьируется (стабильные сортировочные сети требуют большего количества сравнений)	да	Порядок сравнений устанавливается заранее исходя из фиксированного размера сети. Нецелесообразно для более 32 позиций. [ спорный - обсудить ]
Bitonic сортировщик	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle \log ^{2}n}$	${\displaystyle n\log ^{2}n}$	Нет	да	Эффективный вариант Сортировочных сетей.
Богосорт	п	${\displaystyle (n\times n!)}$	неограниченный (определенный), (ожидаемый)${\displaystyle (n\times n!)}$	1	Нет	да	Случайное перемешивание. Используется только в качестве примера, так как даже ожидаемое время выполнения в лучшем случае ужасно. [19]
Stooge sort	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	${\displaystyle n^{\log 3/\log 1.5}}$	п	Нет	да	Медленнее, чем большинство алгоритмов сортировки (даже наивных), с временной сложностью O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ) .

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

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

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

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

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

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

Простые сортировки [ править ]

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

Вставка сортировки [ править ]

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

Сортировка выбора [ править ]

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

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

Эффективные сортировки [ править ]

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

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

Сортировка слиянием [ править ]

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

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

Heapsort [ править ]

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

Быстрая сортировка [ править ]

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

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

Shellsort [ править ]

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

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

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

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

Сортировка пузырьков [ править ]

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

^[34]

Сортировка гребней [ править ]

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

Сортировка распределения [ править ]

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

Подсчет сортировки [ править ]

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

Сортировка по сегменту [ править ]

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

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

Radix sort [ править ]

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

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

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

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

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

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

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

Связанные алгоритмы [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

• Кнут, Дональд Э. (1998), Сортировка и поиск , Искусство компьютерного программирования, 3 (2-е изд.), Бостон: Addison-Wesley, ISBN 0-201-89685-0
• Седжвик, Роберт (1980), «Эффективная сортировка с помощью компьютера: введение», Computational Probability , New York: Academic Press, стр.  101–130 , ISBN 0-12-394680-8

Внешние ссылки [ править ]

Реализация алгоритма Викибука имеет страницу на тему: Алгоритмы сортировки

В Wikibook A-level Mathematics есть страница по теме: Алгоритмы сортировки

Викискладе есть медиафайлы, связанные с алгоритмами сортировки .

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