Сортировка — фундаментальная операция в информатике, и существуют различные алгоритмы для эффективного выполнения этой задачи. Одним из популярных алгоритмов сортировки является быстрая сортировка, известная своей простотой и эффективностью. В этой статье мы рассмотрим быструю сортировку на C++ и обсудим несколько методов ее реализации. По ходу дела мы будем предоставлять примеры кода, которые помогут вам лучше понять концепцию.

Метод 1: базовый алгоритм быстрой сортировки
Базовый алгоритм быстрой сортировки основан на подходе «разделяй и властвуй». Он выбирает опорный элемент, разбивает массив вокруг опорного элемента и рекурсивно применяет тот же процесс к подмассивам. Вот код:

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}
int partition(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]);
    return i + 1;
}

Метод 2: рандомизированная быстрая сортировка
Рандомизированная быстрая сортировка улучшает базовый алгоритм, выбирая случайный опорный элемент вместо того, чтобы всегда выбирать последний элемент в качестве опорного. Это помогает избежать худших сценариев. Вот пример:

int randomizedPartition(int arr[], int low, int high) {
    int randomIndex = low + rand() % (high - low + 1);
    swap(arr[randomIndex], arr[high]);
    return partition(arr, low, high);
}
void randomizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = randomizedPartition(arr, low, high);
        randomizedQuickSort(arr, low, pivot - 1);
        randomizedQuickSort(arr, pivot + 1, high);
    }
}

Метод 3: оптимизированная быстрая сортировка
К быстрой сортировке можно применить оптимизацию, чтобы еще больше повысить ее производительность. Одним из таких улучшений является переключение на сортировку вставками для небольших подмассивов, поскольку накладные расходы на быструю сортировку становятся значительными для крошечных разделов. Вот пример:

const int INSERTION_SORT_THRESHOLD = 10;
void optimizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        if (high - low + 1 <= INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, low, high);
        } else {
            int pivot = partition(arr, low, high);
            optimizedQuickSort(arr, low, pivot - 1);
            optimizedQuickSort(arr, pivot + 1, high);
        }
    }
}
void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Быстрая сортировка – это универсальный и эффективный алгоритм сортировки, который можно реализовать различными способами. В этой статье мы рассмотрели три метода реализации быстрой сортировки на C++: базовый алгоритм, рандомизированную быструю сортировку и оптимизированную версию с сортировкой вставками для небольших подмассивов. Понимая эти методы и примеры их кода, вы сможете эффективно сортировать массивы в своих программах на C++.