Алгоритм сортировки попадает в семейство адаптивной сортировки , если он использует существующий порядок на входе. Он извлекает выгоду из предварительной сортировки во входной последовательности — или ограниченного количества беспорядка для различных определений мер беспорядка — и сортирует быстрее. Адаптивная сортировка обычно выполняется путем модификации существующих алгоритмов сортировки.
Алгоритмы сортировки на основе сравнения традиционно имели дело с достижением оптимальной границы O ( n log n ) при работе со сложностью времени . Адаптивная сортировка использует существующий порядок ввода, чтобы попытаться достичь лучших времен, так что время, необходимое алгоритму для сортировки, является плавно растущей функцией размера последовательности и беспорядка в последовательности. Другими словами, чем более предварительно отсортирован ввод, тем быстрее он должен сортироваться.
Это привлекательная функция для алгоритма сортировки, поскольку последовательности, которые почти отсортированы, распространены на практике. Таким образом, производительность существующих алгоритмов сортировки может быть улучшена за счет учета существующего порядка на входе.
Большинство алгоритмов сортировки в худшем случае, которые работают оптимально в худшем случае, особенно сортировка кучей и сортировка слиянием , не учитывают существующий порядок во входных данных, хотя этот недостаток легко исправить в случае сортировки слиянием , проверив, является ли последний элемент левой группы меньшим (или равным) первому элементу правой группы, в этом случае операция слияния может быть заменена простой конкатенацией — модификацией, которая вполне соответствует задаче сделать алгоритм адаптивным.
Классическим примером адаптивного алгоритма сортировки является сортировка вставкой . [1] В этом алгоритме сортировки входные данные сканируются слева направо, повторно находя позицию текущего элемента и вставляя его в массив ранее отсортированных элементов.
Ниже приведен псевдокод для алгоритма сортировки вставкой (массив X начинается с нуля ):
процедура сортировки вставкой (X): для j = 1 до длины (X) - 1 сделать т ← X[j] я ← й пока i > 0 и X[i - 1] > t делать X[i] ← X[i - 1] я ← я - 1 конец X[i] ← т конец
Производительность этого алгоритма можно описать в терминах количества инверсий во входных данных, и тогда будет примерно равна , где — количество инверсий. Используя эту меру предварительной сортировки — относительно количества инверсий — сортировка вставками занимает тем меньше времени, чем ближе массив данных к сортировке.
Другими примерами адаптивных алгоритмов сортировки являются адаптивная сортировка кучей , адаптивная сортировка слиянием , терпеливая сортировка , [2] сортировка Шелла , гладкая сортировка , сплайсинговая сортировка , сортировка Тима и сортировка декартовым деревом . [3]
