Сортировка Хоара (Hoare's Quick Sort)

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

Алгоритм

Алгоритм сортировки Хоара работает следующим образом:

1. Выбираем опорный элемент из массива (обычно первый, последний или средний элемент).
2. Разделяем массив на две части: элементы меньше опорного перемещаются влево, а больше - вправо.
3. Опорный элемент не обязательно оказывается в своей конечной позиции после первого разделения.
4. Рекурсивно применяем те же шаги к подмассивам слева и справа от опорного элемента.

Анализ сложности

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

Реализация

Приведём примеры реализации сортировки Хоара:

Python

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

def quickSort(arr, low, high):
    if low < high:
        pi = hoare_partition(arr, low, high)
        quickSort(arr, low, pi)
        quickSort(arr, pi + 1, high)

C++

#include <vector>

int hoarePartition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        do {
            j--;
        } while (arr[j] > pivot);
        if (i >= j)
            return j;
        std::swap(arr[i], arr[j]);
    }
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = hoarePartition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

Java

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = hoarePartition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

private int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        do {
            j--;
        } while (arr[j] > pivot);
        if (i >= j)
            return j;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Заключение

Сортировка Хоара остается одним из самых быстрых и эффективных алгоритмов сортировки, особенно для больших массивов данных. Её способность быстро обрабатывать данные делает её предпочтительным выбором во многих приложениях, где требуется высокая производительность сортировки.