Адаптивная сортировка

Алгоритм сортировки попадает в семейство адаптивной сортировки, если он использует существующий порядок на входных данных. Он выигрывает от предварительной сортировки входной последовательности (или ограниченного количества беспорядка для различных определений мер беспорядка) и сортируется быстрее. Адаптивная сортировка обычно выполняется путем модификации существующих алгоритмов сортировки.

Мотивация

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

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

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

Примеры

Классическим примером адаптивного алгоритма сортировки является сортировка вставками . В этом алгоритме сортировки входные данные сканируются слева направо, неоднократно находя позицию текущего элемента и вставляя его в массив ранее отсортированных элементов.

Ниже приведен псевдокод для алгоритма сортировки вставками (массив X начинается с нуля ):

procedure Insertion Sort (X):
    for j = 1 to length(X) - 1 do
        t ← X[j]
        i ← j
        while i > 0 and X[i - 1] > t do
            X[i] ← X[i - 1]
            i ← i - 1
        end
        X[i] ← t
    end

Производительность этого алгоритма можно описать количеством инверсий на входе, а затем ⁠ $T(n)$⁠ будет примерно равен ⁠ $I(A)+(n-1)$⁠ , где ⁠ $I(A)$⁠ — количество инверсий. Используя эту меру предварительной сортировки (относительную к количеству инверсий), сортировка вставкой занимает меньше времени для сортировки, чем ближе массив данных к сортировке.

Другими примерами адаптивных алгоритмов сортировки являются адаптивная пирамидальная сортировка , адаптивная сортировка слиянием , терпеливная сортировка . Сортировка Шелла , гладкая сортировка , расширенная сортировка , Тимсорт и декартова древовидная сортировка .

См. также

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

Ссылки

• Хагеруп, Торбен; Юрки Катьяйнен (2004). Теория алгоритмов – SWAT 2004 . Берлин Гейдельберг: Springer-Verlag. стр. 221–222. ISBN  3-540-22339-8 .
• Мехта, Динеш П.; Сартадж Сахни (2005). Структуры данных и приложения . США: Чепмен и Холл/CRC. стр. 11–8–11–9. ISBN  1-58488-435-5 .
• Петерссон, Ола; Алистер Моффат (1992). Фреймворк для адаптивной сортировки . Конспекты лекций по информатике. Том. 621. Берлин: Springer Berlin/Heidelberg. стр. 422–433. дои : 10.1007/3-540-55706-7_38 . ISBN  978-3-540-55706-7 . ISSN   1611-3349 .