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

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

Необходимость изучения существующих компьютерных алгоритмов связана с использованием ограниченных вычислительных ресурсов компьютера: память, процессов, скорость чтения данных с диска и запись на диск и др. Эффективность алгоритма напрямую связана с тем, сколько ресурсов компьютеру придётся затратить для решения поставленной задачи. Например, для решения задачи сортировки вставками требуется примерно c_1n^2 операций (здесь n — количество элементов данных, а c_1 — независящая от этих данных константа). Для сортировки слиянием требуется уже порядком c_2n\lg n операций (здесь \lg n — краткая запись \log_2n, а c_2 — некоторая другая константа). Скорость работы второго алгоритма выше, а наглядный пример приводит Кормэн в книге «Алгоритмы. Построение и анализ» (стр.: 34):

…рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нём работает алгоритм сортировкой вставкой, а компьютер Б более медленный, и на нём работает алгоритм методом слияния. Оба компьютеры должны выполнить сортировку множества, состоящего из десяти миллионов чисел. (…) Предположим, что компьютер А выполняет десять миллиардов команд в секунду, а компьютер Б — только 9 миллионов команд в секунду, так что компьютер А в тысячу раз быстрее компьютера Б. Чтобы различие стало ещё большим, предположим, что код для метода вставок (т.е. для компьютера А) написан лучшим в мире программистом на машинном языке и для сортировке n чисел надо выполнить 2n^2 команд. Сортировка же методом слияния (на компьютере Б) выполнена программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50n\lg n команд. Для сортировки десяти миллионов чисел компьютера А понадобиться: \frac{2 * (10^7)^2}{10^{10}} = 20 000 секунд (более 5,5 часов), в то время как компьютеру Б потребуется \frac{50 * 10^7\lg 10^7}{10^7} \approx 1163 секунд (менее 20 минут).

Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует более чем 17 раз меньше процессорного времени!

Определение

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

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

  1. sorting.at
  2. toptal.com

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

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

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

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

Визуализация | Худшее время: 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-мя свойствами:

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

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

  1. Инициализация. Перед первой итерации, когда j = 1, подмассив A[0..j − 1] состоит из единственного элемента A[0], что является тривиальным случаем, и, очевидно, такой подмассив отсортирован.
  2. Сохранение. На каждом последующем этапе осуществляется сдвиг элементов A[j], A[j − 1] и т.д. на одну позицию вправо, освобождая место для A[j] элемента до тех пор, пока не найдётся подходящее место для него. После завершения итерации подмассив A[0..j] состоит из тех же элементов в отсортированном порядке.
  3. Завершение. Цикл завершается в том случае, когда 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 пункта:

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

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

  1. Разделение n-элементной сортируемой последовательности на две подпоследовательности по n / 2 элементов.
  2. Рекурсивная сортировка подпоследовательностей с использованием сортировки методом слияния.
  3. Соединение 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)

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

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

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

Предложенный ниже алгоритм использует разбиение Ломуто, где опорным элементом для каждой последовательности, будет выступать последний её элемент. На отсортированной последовательности алгоритм деградирует до 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)

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

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

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


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

  1. Элементы входной последовательности необходимо переставить таким образом, чтобы они удовлетворяли условиям для бинарной кучи
  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] then LARGEST = LEFT
        if A[RIGHT] > A[LARGEST] then LARGEST = RIGHT
        if (LARGEST != i) then
            swap A[i], A[LARGEST]
            i = LARGEST
        else
            break
        end if
    end while

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

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

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

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: