Быстрая сортировка (Quicksort)

Один из самых эффективных алгоритмов сортировки. Принцип «разделяй и властвуй»: разбиваем массив на две части относительно опорного элемента и рекурсивно сортируем каждую.

Идея алгоритма

Выбираем опорный элемент (pivot) — средний элемент массива
Разделяем массив: элементы меньше опорного — влево, больше — вправо
Рекурсивно сортируем обе части
Когда части станут длиной 0 или 1 — они уже отсортированы

Разбор

Выбор опорного и начальная расстановка указателей

i := л
j := р
опор := A[div(л + р, 2)]

л и р — левая и правая границы сортируемого участка
опор — значение среднего элемента (не индекс, а именно значение)
i движется слева направо, j — справа налево

Разделение (partition)

нц пока i <= j
    нц пока A[i] < опор
        i := i + 1
    кц
    нц пока A[j] > опор
        j := j - 1
    кц
    если i <= j то
        tmp := A[i]
        A[i] := A[j]
        A[j] := tmp
        i := i + 1
        j := j - 1
    все
кц

Ищем слева элемент, который $\ge$ опорного (A[i] < опор — пропускаем)
Ищем справа элемент, который $\le$ опорного (A[j] > опор — пропускаем)
Меняем их местами и сдвигаем оба указателя
Когда i > j — разделение завершено: всё левее j не больше опорного, всё правее i не меньше

Рекурсивные вызовы

если л < j то
    quicksort(n, A, л, j)
все
если i < р то
    quicksort(n, A, i, р)
все

Сортируем левую и правую части, если в них больше одного элемента.

Сложность: $O(n \log n)$ в среднем, $O(n^2)$ в худшем случае (но при выборе среднего элемента как опорного это маловероятно).

Полная программа

алг main(цел n)
нач
    если n <= 0 то
        вывод "Размер массива должен быть положительным", нс
        выход
    все

    цел таб A[0:n-1]
    заполнить_случайными(n, A)

    вывод "Исходный массив:", нс
    печать_массива(n, A)

    quicksort(n, A, 0, n - 1)

    вывод "Отсортированный массив:", нс
    печать_массива(n, A)
кон

алг quicksort(цел n, цел таб A[0:n-1], цел л, цел р)
нач
    цел i, j, m, опор, tmp
    i := л
    j := р
    опор := A[div(л + р, 2)]
    нц пока i <= j
        нц пока A[i] < опор
            i := i + 1
        кц
        нц пока A[j] > опор
            j := j - 1
        кц
        если i <= j то
            tmp := A[i]
            A[i] := A[j]
            A[j] := tmp
            i := i + 1
            j := j - 1
        все
    кц
    если л < j то
        quicksort(n, A, л, j)
    все
    если i < р то
        quicksort(n, A, i, р)
    все
кон

алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        A[i] := irnd(100)
    кц
кон

алг печать_массива(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        вывод A[i], " "
    кц
    вывод нс
кон

▶ Запустить пример