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

Простые сортировки
Эффективные сортировки
Сортировки без сравнений
1. Блочная сортировка
2. Сортировка подсчётом
3. Поразрядная сортировка

Статья в процессе обновления

Определение

Алгоритмы сортировки — это алгоритмы, которые берут некоторую последовательность из $n$ элементов $a_1, a_2,..., a_n$ и переставляют элементы таким образом, чтобы получившаяся последовательность $a'_1,a'_2,...,a'_n$ удовлетворяла условию: $a'_1 \leqslant a'_2 \leqslant ... \leqslant a'_n$ .

Визуализация алгоритмов сортировки

toptal.com

Классификация алгоритмов

Алгоритмы сортировки можно классифицировать по:

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

Простые сортировки

Сортировка выборкой

Визуализация | Худшее время: $O(n^2)$ | Лучшее время: $O(n^2)$ | В среднем: $O(n^2)$ | in-place, неустойчивая

Самая простая сортировка, которая для каждой позиции в последовательности ищет минимальный элемент, после чего меняет элементы с индексами текущей позиции и найденного элемента:

for j = 0 to A.length do
    min = j
    for i = j + 1 to A.length do
        if A[min] > A[i] then
            min = i
        end if
    end for
    swap A[min], A[j]
end for

Пузырьковая сортировка

Визуализация | Худшее время: $O(n^2)$ | Лучшее время: $O(n)$ | В среднем: $O(n^2)$ | in-place, устойчивая, адаптивная

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

for j = 0 to A.length do
    swapped = false
    for i = A.length - 1 downto j do
        if A[i - 1] > A[i] then
            swap A[i - 1], A[i]
            swapped = true
        end if
    end for
    break if not swapped
end for

Сортировка вставками

Визуализация | Худшее время: $O(n^2)$ | Лучшее время: $O(n)$ | В среднем: $O(n^2)$ | in-place, устойчивая, адаптивная

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

Вот алгоритм на псевдокоде:

for j = 1 to A.length do 
    value = A[j]
    i = j - 1
    while i >= 0 and A[i] > value do 
        A[i + 1] = A[i]
        A[i] = value
        i = i - 1
    end while
end for

Утверждение, что в начале каждой итерации цикла оператора for, подмассив A[0..j − 1], которые раньше находились в этом подмассиве, состоит из тех же элементов, но теперь в отсортированном порядке, называется инвариантом цикла. Инварианты позволяют понять, корректно ли работает алгоритм, и обладают 3-мя свойствами:

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

Разберём это определение инвариантов на примере приведённого выше алгоритма:

Инициализация. Перед первой итерацией, когда $j = 1$ , подмассив A[0..j − 1] состоит из единственного элемента A[0], что является тривиальным случаем, и, очевидно, такой подмассив отсортирован.
Сохранение. На каждом последующем этапе осуществляется сдвиг элементов A[j], A[j − 1] и т.д. на одну позицию вправо, освобождая место для A[j] элемента до тех пор, пока не найдётся подходящее место для него. После завершения итерации подмассив A[0..j] состоит из тех же элементов в отсортированном порядке.
Завершение. Цикл завершается в том случае, когда j ≥ n, где n — количество элементов в исходном массиве. Поскольку подмассив A[0..j], который по существу является теперь подмассивом A[0..n] отсортирован, а подмассив A[0..n] и есть исходный массив A, то приведённый алгоритм работает правильно.

Важная особенность работы этого алгоритма заключается в том, что при уже отсортированных исходных данных цикл while не будет выполняться вовсе, т.к. проверка условия A[i] > value будет срабатывать сразу. Это позволяет алгоритму выполнить не $c_1n^2$ команд, а только $c_2n$ , чем пользуются другие, более сложные алгоритмы.

Эффективные сортировки

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

Визуализация | Худшее время: $O(n \lg n)$ | Лучшее время: $O(n \lg n)$ | В среднем: $O(n \lg n)$ | Требует памяти: $O(n)$

Многие алгоритмы имеют рекурсивную структуру: для решения поставленной задачи они вызывают сами себя несколько раз, решая вспомогательные подзадачи. Обычно, разбиение происходит на подзадачи, сходные с исходной, но имеющим меньший объём. Далее они рекурсивно решаются, после чего полученные решения комбинируются для получения решения исходной задачи. Такой подход к решению задачи называется методом «разделяй и властвуй». Этот метод включает в себя 3 пункта:

Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи.
Властвование над подзадачами путём их рекурсивного решения. Если размер задач становится достаточно мал, то они могут быть решены непосредственно.
Комбинирование решений подзадач в решение исходной задачи.

Типичный пример этого метода — сортировка методом слияния, суть которой заключается в следующем:

Разделение $n$ -элементной сортируемой последовательности на две подпоследовательности по $n / 2$ элементов.
Рекурсивная сортировка подпоследовательности с использованием сортировки методом слияния.
Соединение 2-х отсортированных подпоследовательности для получения окончательного отсортированного ответа.

Рекурсия останавливается тогда, когда длина сортируемой подпоследовательности становится равной 1, поскольку любая такая последовательность уже является отсортированной (тривиальный случай). Главной операцией является объединение двух отсортированных последовательностей в ходе комбинирования. Её суть заключается в том, что из двух отсортированных последовательностей выбираются элементы в порядке их возрастания. Поскольку каждая из последовательностей уже отсортирована, то выбор осуществляется между 2-я значениями из разных подпоследовательностей, после чего наименьшее значение перемещается из своей подпоследовательности в комбинируемую.

Алгоритм на псевдокоде:

Merge-Sort(A, p, r)
    if p < r then
        q =  ⌊(p + r) / 2⌋
        Merge-Sort(A, p, q)
        Merge-Sort(A, q + 1, r)
        Merge(A, p, q, r)

Merge(A, p, q, r)
    // подпоследовательности с дополнительным элементом
    LEFT = copyof A[p, q + 2]
    RIGHT = copyof A[q + 1, r + 2]
    LEFT[LEFT.length - 1] = ∞
    RIGHT[RIGHT.length - 1] = ∞

    i = 0
    j = 0
    for k = p to r
        if LEFT[i] <= RIGHT[j] then
            A[k] = LEFT[i]
            i = i + 1
        else 
            A[k] = RIGHT[j]
            j = j + 1
        end if
    end for

Быстрая сортировка

Визуализация | Худшее время: $O(n^2)$ | Лучшее время: $O(n \lg n)$ | В среднем: $O(n \lg n)$

Основной алгоритм работы

Выбрать опорный элемент (pivot).
Разделение: изменить порядок элементов последовательностей таким образом, чтобы все элементы большие или равные, чем опорный элемент, находились после опорного элемента. После разделения опорный элемент будет находиться на своём месте.
Рекурсивно повторить предыдущие два шага обеих образовавшихся подпоследовательностей («слева» и «справа» от выбранного опорного элемента).

Недостатки алгоритма

Предложенный ниже алгоритм использует разбиение Ломуто, где опорным элементом для каждой последовательности, будет выступать последний её элемент. На отсортированной последовательности алгоритм деградирует до $O(n^2)$ .

Quicksort(A, p, r)
    if p < r then
        q =  Partition(A, p, r)
        Quicksort(A, p, q - 1)
        Quicksort(A, q + 1, r)
    end if

Partition(A, p, r)
    i = p - 1
    for j = p to r
        if A[j] < A[r] then
            swap A[++i], A[j]
        end if
    end for
    swap A[++i], A[r]
    return i

Пирамидальная сортировка

Визуализация | Худшее время: $O(n \lg n)$ | Лучшее время: $O(n \lg n)$ | В среднем: $O(n \lg n)$

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

Значение в любом узле не меньше, чем в любом из его потомков
Бинарное дерево является полным

Для представления дерева через массив можно использовать следующую идею: на первой позиции находится корень бинарного дерева, тогда для каждого потомка будет верно, что его индекс определяется как $2n + 1$ для левого потомка и $2n + 2$ для правого потомка:

Алгоритм сводится к следующим шагам:

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

Функция, которая перемещает элемент вниз по дереву для восстановления свойств дерева будем называть Heapify:

Heapsort(A)
    BuildHeap(A)
    for i = A.length - 1 downto 0
        swap A[i], A[0]
        Heapify(A, i, 0)
    end for

BuildHeap(A)
    for i = (A.length - 1) / 2 downto 0
        Heapify(A, A.length, i)

Heapify(A, heapSize, i)
    while true
        LEFT = 2 * i + 1
        RIGHT = 2 * i + 2
        LARGEST = i
        if A[LEFT] > A[LARGEST] and LEFT < heapSize then LARGEST = LEFT
        if A[RIGHT] > A[LARGEST] and RIGHT < heapSize then LARGEST = RIGHT
        if (LARGEST != i) then
            swap A[i], A[LARGEST]
            i = LARGEST
        else
            break
        end if
    end while

...продолжение следует.

* здесь можно найти реализации всех приведённых алгоритмов на Java

Нашли ошибку в тексте? Выделите ошибку в тексте и нажмите Ctrl + Enter на любой странице сайта.