Ответ
Быстрая сортировка (Quicksort) — это эффективный алгоритм сортировки, основанный на стратегии «разделяй и властвуй». В среднем случае его сложность составляет O(n log n), а в худшем — O(n²), хотя на практике это редкая ситуация.
Основной принцип:
- Выбор опорного элемента (pivot) — обычно средний, последний или случайный элемент массива.
- Разделение (partitioning) — перераспределение элементов так, чтобы все элементы меньше опорного оказались слева от него, а все большие — справа.
- Рекурсивная сортировка — алгоритм рекурсивно применяется к левому и правому подмассивам.
Ключевое преимущество — сортировка выполняется на месте, требуя лишь 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 отлично подходит для сортировки больших массивов в памяти благодаря своей скорости и экономии памяти. Однако для данных, где важна стабильность (сохранение порядка равных элементов), или в системах с жесткими требованиями к времени выполнения в худшем случае лучше подойдет сортировка слиянием.
Ответ 18+ 🔞
А, быстрая сортировка! Ну это, блядь, классика жанра, ебать мои старые костыли. Алгоритм, который реально работает, если его не кошмарить худшими случаями. В общем, принцип проще пареной репы: взял массив, ткнул пальцем в какой-то элемент — это твой «пивот», опорный. Всё, что меньше него — кидаешь налево, всё, что больше — направо. А потом ту же самую песню заводишь для левой и правой кучи, пока всё не встанет по полочкам. В среднем он летает как угорелый, O(n log n), но если не повезёт с выбором пивота, может и в O(n²) упереться, хотя это редкость, ёпта.
Как оно внутри колбасится:
- Выбрать пивот. Можно брать последний элемент, средний или вообще рандомный — да похуй, главное не брать всегда один и тот же, а то будет вам хиросима на отсортированном массиве.
- Разделение. Вот тут вся магия. Бежим по массиву, мелкие элементы — налево, крупные — направо. Пивот в итоге встаёт на своё законное место, как хуй с горы.
- Рекурсия. Берём две получившиеся кучи и делаем с ними то же самое. Рекурсивно, пока не останутся кусочки по одному элементу — их уже и сортировать не надо.
Главный плюс — он на месте всё делает, дополнительной памяти овердохуища не жрёт, только стек вызовов подъедает, что в среднем 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, быстрая и эффективная.