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

Основная идея алгоритма

Быстрая сортировка использует стратегию "разделяй и властвуй", чтобы эффективно упорядочить данные. Основные шаги алгоритма следующие:

1. Выбор опорного элемента: Из массива выбирается один элемент, называемый "опорным". Этот выбор может быть случайным, фиксированным (например, первый или последний элемент) или более сложным (медиана трёх и т.д.).

2. Разбиение: Массив перераспределяется таким образом, что элементы меньше опорного перемещаются перед ним, а большие или равные — после. Этот процесс называется "разбиением".

3. Рекурсивная сортировка: Алгоритм рекурсивно применяется к двум подмассивам: элементам до и после опорного.

Процесс разбиения

Наиболее критичной частью быстрой сортировки является процесс разбиения. В классическом варианте разбиения (метод Хоара):

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

Пример:

```cpp
#include <iostream>
#include <vector>

void quickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[right];  // Опорный элемент
    int i = left;            // Начало массива
    int j = right - 1;       // Конец массива, исключая опорный элемент

    while (i <= j) {
        while (i <= j && arr[i] < pivot) i++;
        while (i <= j && arr[j] > pivot) j--;
        if (i <= j) {
            std::swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    std::swap(arr[i], arr[right]);  // Меняем местами опорный элемент с элементом на позиции i

    quickSort(arr, left, i - 1);    // Рекурсивная сортировка левой части
    quickSort(arr, i + 1, right);   // Рекурсивная сортировка правой части
}

int main() {
    std::vector<int> data = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    quickSort(data, 0, data.size() - 1);

    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}
```

Сложность алгоритма

• Лучший случай: O(n log n), когда разбиения делят массив на равные части.
• Средний случай: O(n log n), что делает его очень эффективным для большинства наборов данных.
• Худший случай: O(n²), который возникает, когда каждое разбиение делит массив так, что одна часть содержит все элементы, кроме одного.

Быстрая сортировка часто предпочтительнее других алгоритмов из-за её эффективности в среднем и лучшем случае и хорошей адаптивности к различным наборам данных.

April 20, 2024, easyoffer