Расскажи подробнее про любой алгоритм сортировки

Быстрая сортировка (Quicksort) — это эффективный алгоритм сортировки, основанный на стратегии «разделяй и властвуй». В среднем случае его сложность составляет O(n log n), а в худшем — O(n²), хотя на практике это редкая ситуация.

Основной принцип:

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

Ключевое преимущество — сортировка выполняется на месте, требуя лишь O(log n) дополнительной памяти для стека вызовов (в среднем случае).

Пример реализации на C++:

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // выбираем последний элемент как опорный
    int i = low - 1; // индекс меньшего элемента
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(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);
    }
}

Когда использовать: Quicksort отлично подходит для сортировки больших массивов в памяти благодаря своей скорости и экономии памяти. Однако для данных, где важна стабильность (сохранение порядка равных элементов), или в системах с жесткими требованиями к времени выполнения в худшем случае лучше подойдет сортировка слиянием.