В информатике алгоритм сортировки — это алгоритм , который упорядочивает элементы списка . Наиболее часто используемые порядки — это числовой и лексикографический , а также возрастающий или убывающий. Эффективная сортировка важна для оптимизации эффективности других алгоритмов (таких как алгоритмы поиска и слияния ), которые требуют , чтобы входные данные находились в отсортированных списках. Сортировка также часто полезна для канонизации данных и для создания вывода, удобного для восприятия человеком.
Формально результат любого алгоритма сортировки должен удовлетворять двум условиям:
Хотя некоторые алгоритмы предназначены для последовательного доступа , наиболее эффективные алгоритмы предполагают, что данные хранятся в структуре данных , допускающей произвольный доступ .
С самого начала вычислений проблема сортировки привлекала большое количество исследований, возможно, из-за сложности ее эффективного решения, несмотря на ее простую, знакомую формулировку. Среди авторов ранних алгоритмов сортировки около 1951 года была Бетти Холбертон , работавшая над ENIAC и UNIVAC . [1] [2] Пузырьковая сортировка была проанализирована еще в 1956 году. [3] Асимптотически оптимальные алгоритмы известны с середины 20-го века — новые алгоритмы все еще изобретаются, причем широко используемый Timsort датируется 2002 годом, а библиотечная сортировка была впервые опубликована в 2006 году.
Алгоритмы сортировки сравнений имеют фундаментальное требование Ω( n log n ) сравнений (некоторые входные последовательности потребуют кратного n log n сравнений, где n — количество элементов в массиве, подлежащем сортировке). Алгоритмы, не основанные на сравнениях, такие как сортировка подсчетом , могут иметь лучшую производительность.
Алгоритмы сортировки широко распространены на вводных занятиях по информатике , где обилие алгоритмов для решения этой задачи обеспечивает плавное введение в различные основные концепции алгоритмов, такие как нотация «О» большое , алгоритмы «разделяй и властвуй» , структуры данных , такие как кучи и двоичные деревья , рандомизированные алгоритмы , анализ наилучшего, наихудшего и среднего случая , компромиссы между временем и пространством , а также верхние и нижние границы .
Оптимальная сортировка небольших массивов (с наименьшим количеством сравнений и обменов) или быстрая (т.е. с учетом особенностей машины) все еще является открытой исследовательской проблемой, решения которой известны только для очень маленьких массивов (<20 элементов). Аналогично оптимальная (по разным определениям) сортировка на параллельной машине является открытой исследовательской темой.
Алгоритмы сортировки можно классифицировать по:
Стабильные алгоритмы сортировки сортируют равные элементы в том же порядке, в котором они появляются во входных данных. Например, в примере сортировки карт справа карты сортируются по их рангу, а их масть игнорируется. Это допускает возможность нескольких различных правильно отсортированных версий исходного списка. Стабильные алгоритмы сортировки выбирают один из них в соответствии со следующим правилом: если два элемента сравниваются как равные (например, две карты по 5), то их относительный порядок будет сохранен, т. е. если один идет перед другим во входных данных, он будет идти перед другим и на выходе.
Стабильность важна для сохранения порядка при нескольких сортировках одного и того же набора данных . Например, предположим, что записи студентов, состоящие из раздела имени и класса, сортируются динамически, сначала по имени, затем по разделу класса. Если в обоих случаях используется стабильный алгоритм сортировки, операция сортировки по разделу класса не изменит порядок имен; при нестабильной сортировке может случиться так, что сортировка по разделу перетасует порядок имен, что приведет к неалфавитному списку студентов.
Более формально, сортируемые данные могут быть представлены как запись или кортеж значений, а часть данных, которая используется для сортировки, называется ключом . В примере с картами карты представлены как запись (ранг, масть), а ключом является ранг. Алгоритм сортировки является устойчивым, если всякий раз, когда есть две записи R и S с одинаковым ключом, и R появляется перед S в исходном списке, то R всегда будет появляться перед S в отсортированном списке.
Когда одинаковые элементы неразличимы, например, в случае целых чисел или, в более общем смысле, любых данных, где весь элемент является ключом, стабильность не является проблемой. Устойчивость также не является проблемой, если все ключи различны.
Нестабильные алгоритмы сортировки могут быть специально реализованы, чтобы быть стабильными. Один из способов сделать это — искусственно расширить сравнение ключей, так что сравнения между двумя объектами с в остальном равными ключами будут решаться с использованием порядка записей в исходном списке входных данных в качестве решающего фактора. Однако запоминание этого порядка может потребовать дополнительного времени и места.
Одним из приложений для алгоритмов стабильной сортировки является сортировка списка с использованием первичного и вторичного ключа. Например, предположим, что мы хотим отсортировать руку карт таким образом, чтобы масти были в следующем порядке: трефы (♣), бубны ( ♦ ), червы ( ♥ ), пики (♠), и в каждой масти карты были бы отсортированы по рангу. Это можно сделать, сначала отсортировав карты по рангу (используя любую сортировку), а затем выполнив стабильную сортировку по масти:
В пределах каждой масти стабильная сортировка сохраняет упорядочение по рангу, которое уже было сделано. Эту идею можно распространить на любое количество ключей и использовать в сортировке по радиксу . Того же эффекта можно добиться с нестабильной сортировкой, используя лексикографическое сравнение ключей, которое, например, сначала сравнивает по масти, а затем сравнивает по рангу, если масти одинаковы.
В этом анализе предполагается, что длина каждого ключа постоянна и что все сравнения, обмены и другие операции могут выполняться за постоянное время.
Легенда:
Ниже приведена таблица сравнительных сортировок . Математический анализ показывает, что сравнительная сортировка не может работать лучше, чем O ( n log n ) в среднем. [4]
В следующей таблице описаны алгоритмы сортировки целых чисел и другие алгоритмы сортировки, которые не являются сортировками сравнения . Эти алгоритмы не ограничены Ω ( n log n ) , если только они не соответствуют модели машины случайного доступа с единичной стоимостью, как описано ниже. [12]
Samplesort можно использовать для распараллеливания любой несравнительной сортировки, эффективно распределяя данные по нескольким сегментам и затем передавая сортировку нескольким процессорам, без необходимости объединения, поскольку сегменты уже отсортированы друг между другом.
Некоторые алгоритмы медленнее, чем те, что обсуждались выше, например, сортировка bogosort с неограниченным временем выполнения и сортировка stooge , которая имеет время выполнения O ( n 2.7 ). Эти сортировки обычно описываются в образовательных целях, чтобы продемонстрировать, как оценивается время выполнения алгоритмов. В следующей таблице описаны некоторые алгоритмы сортировки, которые непрактичны для реального использования в традиционных программных контекстах из-за крайне низкой производительности или специальных требований к оборудованию.
Теоретики-компьютерщики подробно описали другие алгоритмы сортировки, которые обеспечивают временную сложность выше O ( n log n ), предполагая дополнительные ограничения, в том числе:
Хотя существует большое количество алгоритмов сортировки, в практических реализациях преобладают несколько алгоритмов. Сортировка вставкой широко используется для небольших наборов данных, в то время как для больших наборов данных используется асимптотически эффективная сортировка, в первую очередь пирамидальная сортировка, сортировка слиянием или быстрая сортировка. Эффективные реализации обычно используют гибридный алгоритм , объединяющий асимптотически эффективный алгоритм для общей сортировки с сортировкой вставкой для небольших списков в нижней части рекурсии. Высоко настроенные реализации используют более сложные варианты, такие как Timsort (сортировка слиянием, сортировка вставкой и дополнительная логика), используемый в Android , Java и Python , и introsort (быстрая сортировка и пирамидальная сортировка), используемый (в различных формах) в некоторых реализациях сортировки на C++ и в .NET .
Для более ограниченных данных, таких как числа в фиксированном интервале, широко используются сортировки распределения, такие как сортировка подсчетом или сортировка по основанию. Пузырьковая сортировка и ее варианты редко используются на практике, но часто встречаются в обучении и теоретических дискуссиях.
При физической сортировке объектов (например, при сортировке по алфавиту документов, тестов или книг) люди интуитивно обычно используют сортировку вставкой для небольших наборов. Для больших наборов люди часто сначала группируют, например, по начальной букве, а множественная группировка позволяет практично сортировать очень большие наборы. Часто пространство относительно дешево, например, при разбрасывании объектов по полу или на большой площади, но операции дороги, особенно перемещение объекта на большое расстояние — важна локальность ссылки . Сортировка слиянием также практична для физических объектов, особенно поскольку можно использовать две руки, по одной для каждого списка для слияния, в то время как другие алгоритмы, такие как пирамидальная сортировка или быстрая сортировка, плохо подходят для использования человеком. Другие алгоритмы, такие как библиотечная сортировка , вариант сортировки вставкой, который оставляет пробелы, также практичны для физического использования.
Две из самых простых сортировок — это сортировка вставкой и сортировка выбором, обе эффективны на небольших данных из-за низких накладных расходов, но неэффективны на больших данных. Сортировка вставкой, как правило, быстрее, чем сортировка выбором на практике из-за меньшего количества сравнений и хорошей производительности на почти отсортированных данных, и поэтому предпочтительнее на практике, но сортировка выбором использует меньше записей и поэтому используется, когда производительность записи является ограничивающим фактором.
Сортировка вставкой — это простой алгоритм сортировки, который относительно эффективен для небольших списков и в основном отсортированных списков и часто используется как часть более сложных алгоритмов. Он работает, беря элементы из списка один за другим и вставляя их в правильные позиции в новый отсортированный список, подобно тому, как человек кладет деньги в свой кошелек. [22] В массивах новый список и оставшиеся элементы могут совместно использовать пространство массива, но вставка обходится дорого, требуя сдвига всех последующих элементов на один. Сортировка Шелла — это вариант сортировки вставкой, который более эффективен для больших списков.
Сортировка выбором — это сортировка сравнением на месте . Она имеет сложность O ( n 2 ), что делает ее неэффективной на больших списках, и, как правило, работает хуже, чем похожая сортировка вставкой . Сортировка выбором известна своей простотой, а также имеет преимущества в производительности по сравнению с более сложными алгоритмами в определенных ситуациях.
Алгоритм находит минимальное значение, меняет его местами со значением в первой позиции и повторяет эти шаги для оставшейся части списка. [23] Он делает не более n обменов, и поэтому полезен там, где обмен очень дорог.
Практические общие алгоритмы сортировки почти всегда основаны на алгоритме со средней временной сложностью (и, как правило, сложностью в худшем случае) O( n log n ), из которых наиболее распространенными являются пирамидальная сортировка, сортировка слиянием и быстрая сортировка. У каждого есть свои преимущества и недостатки, наиболее существенным из которых является то, что простая реализация сортировки слиянием использует O( n ) дополнительного пространства, а простая реализация быстрой сортировки имеет сложность в худшем случае O( n 2 ). Эти проблемы можно решить или улучшить за счет более сложного алгоритма.
Хотя эти алгоритмы асимптотически эффективны на случайных данных, для практической эффективности на реальных данных используются различные модификации. Во-первых, накладные расходы этих алгоритмов становятся значительными на меньших данных, поэтому часто используется гибридный алгоритм, обычно переключаясь на сортировку вставкой, когда данные становятся достаточно маленькими. Во-вторых, алгоритмы часто плохо работают на уже отсортированных данных или почти отсортированных данных — они распространены в реальных данных и могут быть отсортированы за время 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]
Пирамидальная сортировка — гораздо более эффективная версия сортировки выбором . Она также работает, определяя наибольший (или наименьший) элемент списка, помещая его в конец (или начало) списка, а затем продолжая с остальной частью списка, но выполняет эту задачу эффективно, используя структуру данных, называемую кучей , особый тип двоичного дерева . [29] После того, как список данных был преобразован в кучу, корневой узел гарантированно будет наибольшим (или наименьшим) элементом. Когда он удаляется и помещается в конец списка, куча перестраивается так, что наибольший оставшийся элемент перемещается в корень. Используя кучу, поиск следующего наибольшего элемента занимает время O(log n ), вместо O( n ) для линейного сканирования, как в простой сортировке выбором. Это позволяет выполнять пирамидальную сортировку за время O( n log n ), и это также наихудшая сложность случая.
Быстрая сортировка — это алгоритм «разделяй и властвуй» , который основан на операции разбиения : для разбиения массива выбирается элемент, называемый опорным элементом . [30] [31] Все элементы, меньшие опорного элемента, перемещаются перед ним, а все большие элементы перемещаются после него. Это можно сделать эффективно за линейное время и на месте . Затем меньшие и большие подсписки рекурсивно сортируются. Это дает среднюю временную сложность O( n log n ) с низкими накладными расходами, и, таким образом, это популярный алгоритм. Эффективные реализации быстрой сортировки (с разбиением на месте) обычно являются нестабильными сортировками и довольно сложными, но являются одними из самых быстрых алгоритмов сортировки на практике. Вместе с его скромным использованием пространства O(log n ) быстрая сортировка является одним из самых популярных алгоритмов сортировки и доступна во многих стандартных библиотеках программирования.
Важное предостережение относительно быстрой сортировки заключается в том, что ее худшая производительность составляет O( n 2 ); хотя это бывает редко, в наивных реализациях (выбор первого или последнего элемента в качестве опорного) это происходит для отсортированных данных, что является обычным случаем. Таким образом, наиболее сложной проблемой в быстрой сортировке является выбор хорошего опорного элемента, поскольку постоянно плохой выбор опорных элементов может привести к значительно более низкой производительности O( n 2 ), но хороший выбор опорных элементов дает производительность O( n log n ), что является асимптотически оптимальным. Например, если на каждом шаге в качестве опорного элемента выбирается медиана , то алгоритм работает за O( n log n ). Нахождение медианы, например, с помощью алгоритма выбора медианы медиан, однако, является операцией O( n ) на несортированных списках и, следовательно, требует значительных накладных расходов при сортировке. На практике выбор случайного опорного элемента почти наверняка дает производительность O( n log n ).
Если важна гарантия производительности O( n log n ), есть простая модификация для ее достижения. Идея, принадлежащая Массеру, заключается в том, чтобы установить предел максимальной глубины рекурсии. [32] Если этот предел превышен, то сортировка продолжается с использованием алгоритма пирамидальной сортировки. Массер предложил, чтобы предел был , что примерно вдвое больше максимальной глубины рекурсии, которую можно было бы ожидать в среднем для случайно упорядоченного массива.
Сортировка Шелла была изобретена Дональдом Шеллом в 1959 году. [33] Она улучшает сортировку вставкой, перемещая элементы не по порядку более чем на одну позицию за раз. Концепция, лежащая в основе сортировки Шелла, заключается в том, что сортировка вставкой выполняется за время , где k — наибольшее расстояние между двумя элементами не на своих местах. Это означает, что, как правило, они выполняются за O ( n 2 ), но для данных, которые в основном отсортированы, только с несколькими элементами не на своих местах, они выполняются быстрее. Таким образом, сначала сортируя элементы, находящиеся далеко, и постепенно сокращая разрыв между сортируемыми элементами, окончательная сортировка вычисляется намного быстрее. Одна из реализаций может быть описана как упорядочивание последовательности данных в двумерном массиве, а затем сортировка столбцов массива с помощью сортировки вставкой.
Сложность Шеллсортинга в худшем случае является открытой проблемой и зависит от используемой последовательности пробелов, с известными сложностями в диапазоне от O ( n 2 ) до O ( n 4/3 ) и Θ( n log 2 n ). Это, в сочетании с тем фактом, что Шеллсортинг выполняется на месте , требует относительно небольшого количества кода и не требует использования стека вызовов , делает его полезным в ситуациях, когда память имеет первостепенное значение, например, во встроенных системах и ядрах операционных систем .
Сортировка пузырьком и ее варианты, такие как сортировка гребенкой и сортировка коктейлем , являются простыми, крайне неэффективными алгоритмами сортировки. Они часто встречаются во вводных текстах из-за простоты анализа, но редко используются на практике.
Пузырьковая сортировка — это простой алгоритм сортировки. Алгоритм начинается с начала набора данных. Он сравнивает первые два элемента, и если первый больше второго, он меняет их местами. Он продолжает делать это для каждой пары соседних элементов до конца набора данных. Затем он снова начинает с первых двух элементов, повторяя до тех пор, пока не произойдет ни одной замены на последнем проходе. [34] Среднее время и наихудшая производительность этого алгоритма составляет O( n 2 ), поэтому он редко используется для сортировки больших неупорядоченных наборов данных. Пузырьковая сортировка может использоваться для сортировки небольшого количества элементов (где ее асимптотическая неэффективность не является высоким штрафом). Пузырьковая сортировка также может эффективно использоваться для списка любой длины, который почти отсортирован (то есть элементы не находятся значительно не на своих местах). Например, если какое-либо количество элементов смещено всего на одну позицию (например, 0123546789 и 1032547698), то пузырьковая сортировка упорядочит их за первый проход, а второй проход найдет все элементы упорядоченными, поэтому сортировка займет всего 2 n времени.
[35]
Сортировка гребнем — относительно простой алгоритм сортировки, основанный на пузырьковой сортировке и первоначально разработанный Влодзимежом Добосевичем в 1980 году. [36] Позднее он был заново открыт и популяризирован Стивеном Лейси и Ричардом Боксом в статье в журнале Byte Magazine, опубликованной в апреле 1991 года. Основная идея заключается в устранении черепах , или небольших значений вблизи конца списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. ( Кролики , большие значения вблизи начала списка, не представляют проблемы в пузырьковой сортировке). Он достигает этого, изначально меняя местами элементы, которые находятся на определенном расстоянии друг от друга в массиве, а не только меняя местами элементы, которые находятся рядом друг с другом, а затем сокращая выбранное расстояние до тех пор, пока он не будет работать как обычная пузырьковая сортировка. Таким образом, если сортировку Шелла можно рассматривать как обобщенную версию сортировки вставкой, которая меняет местами элементы, находящиеся на определенном расстоянии друг от друга, сортировку гребнем можно рассматривать как то же обобщение, примененное к пузырьковой сортировке.
Сортировку обменом иногда путают с пузырьковой сортировкой, хотя на самом деле эти алгоритмы различны. [37] [38] Сортировка обменом работает, сравнивая первый элемент со всеми элементами выше него, меняя их местами, где это необходимо, тем самым гарантируя, что первый элемент является правильным для окончательного порядка сортировки; затем она продолжает делать то же самое для второго элемента и т. д. У нее нет преимущества пузырьковой сортировки, заключающегося в обнаружении за один проход, если список уже отсортирован, но она может быть быстрее пузырьковой сортировки на постоянный множитель (на один проход меньше по данным для сортировки; вдвое меньше общего числа сравнений) в худших ситуациях. Как и любая простая сортировка O( n 2 ), она может быть достаточно быстрой для очень маленьких наборов данных, хотя в общем случае сортировка вставкой будет быстрее.
Сортировка распределения относится к любому алгоритму сортировки, в котором данные распределяются от их входа к нескольким промежуточным структурам, которые затем собираются и помещаются на выходе. Например, и сортировка ведром , и флэш-сортировка являются алгоритмами сортировки на основе распределения. Алгоритмы сортировки распределения могут использоваться на одном процессоре, или они могут быть распределенным алгоритмом , в котором отдельные подмножества сортируются отдельно на разных процессорах, а затем объединяются. Это позволяет выполнять внешнюю сортировку данных, слишком больших для того, чтобы поместиться в память одного компьютера.
Сортировка подсчетом применима, когда известно, что каждый вход принадлежит определенному набору S возможностей. Алгоритм выполняется за время O(| S | + n ) и память O(| S |), где n — длина входа. Он работает, создавая целочисленный массив размером | S | и используя i -ю ячейку для подсчета вхождений i -го члена S во входе. Затем каждый вход подсчитывается путем увеличения значения его соответствующей ячейки. После этого подсчитывающий массив циклически проходит по всем входам, чтобы упорядочить все входы. Этот алгоритм сортировки часто нельзя использовать, поскольку S должно быть достаточно малым для эффективности алгоритма, но он чрезвычайно быстр и демонстрирует отличное асимптотическое поведение при увеличении n . Его также можно модифицировать для обеспечения стабильного поведения.
Сортировка по ведру — это алгоритм сортировки «разделяй и властвуй» , который обобщает сортировку подсчетом , разбивая массив на конечное число ведров. Затем каждый ведёрко сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо рекурсивно применяя алгоритм сортировки по ведру.
Сортировка по блокам работает лучше всего, когда элементы набора данных равномерно распределены по всем блокам.
Сортировка по основанию — это алгоритм, который сортирует числа, обрабатывая отдельные цифры. n чисел, состоящих из k цифр каждое, сортируются за время O( n · k ). Сортировка по основанию может обрабатывать цифры каждого числа, начиная с наименее значащей цифры (LSD) или начиная со наиболее значащей цифры (MSD). Алгоритм LSD сначала сортирует список по наименее значащей цифре, сохраняя их относительный порядок с помощью устойчивой сортировки. Затем он сортирует их по следующей цифре и так далее от наименее значащей к наиболее значащей, в результате чего получается отсортированный список. В то время как сортировка по основанию LSD требует использования устойчивой сортировки, алгоритм сортировки по основанию MSD этого не делает (если только не требуется устойчивая сортировка). Сортировка по основанию MSD на месте не является устойчивой. Алгоритм сортировки подсчетом часто используется внутри сортировки по основанию. Гибридный подход сортировки, такой как сортировка вставкой для небольших ячеек, значительно повышает производительность сортировки по основанию.
Когда размер сортируемого массива приближается или превышает доступную первичную память, так что (гораздо медленнее) необходимо использовать диск или пространство подкачки, модель использования памяти алгоритма сортировки становится важной, и алгоритм, который мог бы быть довольно эффективным, когда массив легко помещался в ОЗУ, может стать непрактичным. В этом сценарии общее количество сравнений становится (относительно) менее важным, а количество раз, которое разделы памяти должны быть скопированы или переставлены на диск и с него, может доминировать над характеристиками производительности алгоритма. Таким образом, количество проходов и локализация сравнений могут быть важнее, чем чистое количество сравнений, поскольку сравнения соседних элементов друг с другом происходят на скорости системной шины (или, с кэшированием, даже на скорости ЦП ), что по сравнению со скоростью диска является практически мгновенным.
Например, популярный рекурсивный алгоритм быстрой сортировки обеспечивает вполне приемлемую производительность при достаточном объеме оперативной памяти, но из-за рекурсивного способа копирования частей массива он становится гораздо менее практичным, когда массив не помещается в оперативной памяти, поскольку это может привести к ряду медленных операций копирования или перемещения на диск и с диска. В этом случае другой алгоритм может оказаться предпочтительнее, даже если он требует большего общего количества сравнений.
Один из способов обойти эту проблему, который хорошо работает, когда сложные записи (например, в реляционной базе данных ) сортируются по относительно небольшому ключевому полю, — это создать индекс в массиве и затем отсортировать индекс, а не весь массив. (Затем отсортированную версию всего массива можно создать за один проход, считывая данные из индекса, но часто даже это не нужно, поскольку достаточно иметь отсортированный индекс.) Поскольку индекс намного меньше всего массива, он может легко поместиться в памяти, где весь массив не поместился бы, эффективно устраняя проблему подкачки дисков. Эту процедуру иногда называют «сортировкой по тегам». [39]
Другой метод преодоления проблемы размера памяти — использование внешней сортировки , например, один из способов — объединить два алгоритма таким образом, чтобы использовать силу каждого из них для повышения общей производительности. Например, массив может быть разделен на фрагменты такого размера, который поместится в ОЗУ, содержимое каждого фрагмента может быть отсортировано с использованием эффективного алгоритма (например, быстрой сортировки ), а результаты объединены с использованием k -стороннего слияния, аналогичного используемому в сортировке слиянием . Это быстрее, чем выполнение сортировки слиянием или быстрой сортировки по всему списку. [40] [41]
Методы также могут быть объединены. Для сортировки очень больших наборов данных, которые значительно превышают системную память, даже индекс может потребоваться отсортировать с использованием алгоритма или комбинации алгоритмов, разработанных для разумной работы с виртуальной памятью , т. е. для уменьшения объема требуемой подкачки.
Связанные проблемы включают приблизительную сортировку (сортировку последовательности в пределах определенного количества правильного порядка), частичную сортировку (сортировку только k наименьших элементов списка или нахождение k наименьших элементов, но неупорядоченных) и выбор (вычисление k -го наименьшего элемента). Они могут быть решены неэффективно с помощью полной сортировки, но существуют более эффективные алгоритмы, часто получаемые путем обобщения алгоритма сортировки. Наиболее ярким примером является quickselect , который связан с quicksort . Наоборот, некоторые алгоритмы сортировки могут быть получены путем повторного применения алгоритма выбора; quicksort и quickselect можно рассматривать как один и тот же поворотный ход, отличающийся только тем, рекурсия ли выполняется с обеих сторон (quicksort, divided-and-conquer ) или с одной стороны (quickselect, reduce-and-conquer ).
Своего рода противоположностью алгоритму сортировки является алгоритм тасования . Они принципиально отличаются, поскольку требуют источника случайных чисел. Тасование также может быть реализовано с помощью алгоритма сортировки, а именно случайной сортировки: присвоение случайного числа каждому элементу списка и последующая сортировка на основе случайных чисел. Однако на практике это обычно не делается, и существует хорошо известный простой и эффективный алгоритм тасования: тасование Фишера–Йетса .
Алгоритмы сортировки неэффективны для поиска порядка во многих ситуациях. Обычно, когда элементы не имеют надежной функции сравнения (предпочтения, полученные с помощью краудсорсинга, такие как системы голосования ), сравнения очень затратны ( спорт ), или когда невозможно попарно сравнить все элементы по всем критериям ( поисковые системы ). В этих случаях проблема обычно называется ранжированием , и цель состоит в том, чтобы найти «лучший» результат для некоторых критериев в соответствии с вероятностями, выведенными из сравнений или ранжирований. Типичным примером являются шахматы, где игроки ранжируются с помощью системы рейтинга Эло , а рейтинги определяются турнирной системой вместо алгоритма сортировки.
