Что такое быстрая сортировка

1️⃣ Как кратко ответить

Быстрая сортировка (QuickSort) — это алгоритм сортировки, использующий метод "разделяй и властвуй". Он выбирает опорный элемент (пивот), разделяет массив на две части: элементы меньше пивота и элементы больше пивота, и рекурсивно сортирует обе части. Это один из самых эффективных алгоритмов сортировки с ожидаемой сложностью O(n log n).

2️⃣ Подробное объяснение темы

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

Принцип работы

1. Выбор опорного элемента (пивота):

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

2. Разделение массива:

   • Массив перестраивается так, чтобы все элементы, меньшие пивота, оказались слева от него, а все элементы, большие пивота, — справа. Пивот оказывается на своем окончательном месте в отсортированном массиве.

3. Рекурсивная сортировка:

   • Процесс повторяется рекурсивно для подмассивов слева и справа от пивота.

Пример кода на C++

#include <iostream>
#include <vector>
​
// Функция для обмена двух элементов
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
​
// Функция для разделения массива и возвращения индекса пивота
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Выбор последнего элемента в качестве пивота
    int i = low - 1; // Индекс меньшего элемента
​
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) { // Если текущий элемент меньше пивота
            i++; // Увеличиваем индекс меньшего элемента
            swap(arr[i], arr[j]); // Меняем местами элементы
        }
    }
    swap(arr[i + 1], arr[high]); // Меняем местами пивот и элемент на позиции i+1
    return (i + 1); // Возвращаем индекс пивота
}
​
// Основная функция быстрой сортировки
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // Индекс пивота после разделения
​
        quickSort(arr, low, pi - 1); // Рекурсивно сортируем элементы до пивота
        quickSort(arr, pi + 1, high); // Рекурсивно сортируем элементы после пивота
    }
}
​
int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    std::cout << "Отсортированный массив: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Объяснение кода

• Функция swap: Меняет местами два элемента. Используется для перестановки элементов массива.
• Функция partition:
  • Выбирает последний элемент как пивот.
  • Переставляет элементы массива так, чтобы элементы меньше пивота оказались слева, а больше — справа.
  • Возвращает индекс, по которому находится пивот после перестановки.
• Функция quickSort:
  • Рекурсивно сортирует подмассивы, используя partition для разделения.
  • Базовый случай рекурсии — когда подмассив содержит один или ноль элементов.

Применение

Быстрая сортировка широко используется в стандартных библиотеках языков программирования благодаря своей эффективности. Она подходит для сортировки больших объемов данных и часто используется в системах, где важна скорость выполнения. Однако в худшем случае (например, при неудачном выборе пивота) её сложность может достигать O(n²), поэтому в некоторых реализациях применяются улучшения, такие как случайный выбор пивота.