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