Ответ
QuickSort — это эффективный алгоритм сортировки сравнением, работающий по принципу «разделяй и властвуй». Его ключевая идея — выбрать опорный элемент (pivot) и переупорядочить массив так, чтобы все элементы меньше pivot оказались слева от него, а все большие или равные — справа (процедура partition). Затем алгоритм рекурсивно применяется к двум полученным подмассивам.
Реализация на C++ (итеративная с использованием стека для избежания глубокой рекурсии):
#include <iostream>
#include <stack>
#include <utility>
// Функция разделения (partition) по схеме Ломуто
int partition(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;
std::swap(arr[i], arr[j]);
}
}
// Помещаем pivot на правильную позицию
std::swap(arr[i + 1], arr[high]);
return i + 1; // Возвращаем индекс pivot
}
// Итеративная QuickSort (использует явный стек вместо рекурсии)
void quickSortIterative(int arr[], int low, int high) {
std::stack<std::pair<int, int>> stack;
stack.push({low, high});
while (!stack.empty()) {
auto [l, h] = stack.top();
stack.pop();
if (l >= h) continue; // Базовый случай рекурсии
int p = partition(arr, l, h); // Индекс разбиения
// Кладем в стек диапазоны для сортировки, начиная с меньшего
// Это оптимизация, ограничивающая глубину стека.
if (p - 1 > l) {
stack.push({l, p - 1});
}
if (p + 1 < h) {
stack.push({p + 1, h});
}
}
}
int main() {
int data[] = {10, 7, 8, 9, 1, 5, 3, 12, 4};
int n = sizeof(data) / sizeof(data[0]);
quickSortIterative(data, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
return 0;
}Характеристики и важные детали:
- Средняя временная сложность: O(n log n). Это делает QuickSort одним из самых быстрых алгоритмов на практике для сортировки массивов в памяти.
- Худший случай O(n²) возникает при неудачном выборе pivot (например, всегда минимальный или максимальный элемент) на уже отсортированном или почти отсортированном массиве. Способы борьбы:
- Выбор медианы трех (первого, среднего и последнего элементов) как pivot.
- Случайный выбор pivot (
std::swap(arr[high], arr[low + rand() % (high - low + 1)]);).
- Пространственная сложность: В среднем O(log n) для стека вызовов (или явного стека, как в примере). В худшем случае O(n).
- Неустойчивость: QuickSort не сохраняет относительный порядок равных элементов.
- In-place: Алгоритм сортирует данные в исходном массиве, используя лишь небольшой объем дополнительной памяти.
Когда использовать: QuickSort — отличный выбор для сортировки больших массивов примитивных типов в памяти, где важна скорость. Для сортировки связанных списков или в ситуациях, где требуется стабильность, лучше подходят MergeSort или TimSort.
Ответ 18+ 🔞
А, QuickSort, классика жанра! Ну что за зверь такой, сейчас разберёмся. Представь, что у тебя куча барахла в комнате валяется, и тебе надо её разобрать. QuickSort — это как взять первую попавшуюся хуйню (допустим, старый кроссовок), назвать её «опорным элементом» и сказать: «Всё, что мельче этого кроссовка — налево, всё, что крупнее или такое же — направо». Потом ты смотришь на эти две новые кучи и делаешь с ними то же самое. Разделяй и властвуй, ёпта! Пока не останутся кучки из одного предмета — вот тогда порядок и наступит.
Вот как это выглядит в коде на C++ (итеративная версия, чтобы стек не взорвать):
#include <iostream>
#include <stack>
#include <utility>
// Функция, которая раскидывает элементы вокруг опорного (pivot)
int partition(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;
std::swap(arr[i], arr[j]);
}
}
// Ставим сам pivot на правильное, заслуженное место
std::swap(arr[i + 1], arr[high]);
return i + 1; // Возвращаем индекс, где теперь сидит pivot
}
// А вот и сам QuickSort, но без рекурсии, на стеке
void quickSortIterative(int arr[], int low, int high) {
std::stack<std::pair<int, int>> stack;
stack.push({low, high});
while (!stack.empty()) {
auto [l, h] = stack.top();
stack.pop();
if (l >= h) continue; // Если массив пустой или из одного элемента — похуй, пропускаем
int p = partition(arr, l, h); // Делим на части
// Сначала кладём в стек меньший диапазон — это хитрая жопа, чтобы стек не раздуло до овердохуища
if (p - 1 > l) {
stack.push({l, p - 1});
}
if (p + 1 < h) {
stack.push({p + 1, h});
}
}
}
int main() {
int data[] = {10, 7, 8, 9, 1, 5, 3, 12, 4};
int n = sizeof(data) / sizeof(data[0]);
quickSortIterative(data, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
return 0;
}А теперь, чувак, главные фишки и подводные камни:
- Скорость: В среднем он летает как угорелый — O(n log n). На практике часто самый шустрый для обычных массивов.
- А вот хуйня случается в худшем случае — O(n²). Представь, ты как лузер всегда выбираешь самый маленький или самый большой элемент как опорный. Если массив уже почти отсортирован, он будет работать пиздец как медленно. Как бороться?
- Медиана трёх: Бери не просто последний элемент, а смотри на первый, средний и последний, и выбирай из них среднее значение. Умнее.
- Рандом: Просто рандомно меняй последний элемент с каким-нибудь другим перед тем как выбрать pivot. И всё, проблема в пизду.
- Память: В среднем жрёт O(log n) дополнительной памяти на стек вызовов (или на свой явный стек, как у нас). В том самом худшем случае — O(n), но с оптимизацией «сначала меньший диапазон» это маловероятно.
- Нестабильный он: Если у тебя есть два одинаковых элемента, QuickSort может переставить их местами относительно друг друга. Если порядок одинаковых важен — это не твой алгоритм.
- In-place: Сортирует прямо там, где лежит, почти не требуя дополнительной памяти. Красота.
Короче, когда использовать: Когда надо быстро причесать большой массив чисел в оперативке. Если нужна стабильность или сортируешь связный список — иди на MergeSort, не позорься. QuickSort — это как спортивная тачка: быстрая, резкая, но если рулить как говно, врежешься в O(n²).
