Быстрая сортировка
Описание
Быстрая сортировка (Quick Sort) — это эффективный алгоритм сортировки, использующий стратегию «разделяй и властвуй». Он выбирает опорный элемент (pivot) и разделяет массив на два подмассива: элементы, меньшие или равные опорному, и элементы, большие опорного. Затем подмассивы сортируются рекурсивно.
Зачем это нужно
Быстрая сортировка — один из наиболее широко используемых алгоритмов сортировки на практике. Она является стандартным алгоритмом сортировки во многих языках программирования и стандартных библиотеках. Понимание быстрой сортировки помогает освоить парадигму «разделяй и властвуй», которая лежит в основе многих эффективных алгоритмов.
Визуализация
Как работает алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй»: выбирается опорный элемент, массив разделяется вокруг него так, что меньшие элементы уходят влево, а большие — вправо, затем обе стороны сортируются рекурсивно.
1. Выбор опорного элемента
Выбирается элемент массива в качестве опорного (pivot). Распространённые стратегии: последний элемент, первый элемент, случайный элемент или медиана из трёх. Выбор опорного элемента влияет на производительность, но не на корректность.
2. Разделение массива (partition)
Элементы переставляются так, чтобы все значения, меньшие или равные опорному, оказались слева от него, а большие — справа. После разделения опорный элемент находится на своей итоговой позиции.
3. Рекурсивная сортировка подмассивов
Быстрая сортировка применяется к левому подмассиву (элементы до опорного) и правому подмассиву (элементы после опорного):
- Левый подмассив: все элементы ≤ опорного — сортируем рекурсивно.
- Правый подмассив: все элементы > опорного — сортируем рекурсивно.
4. Базовый случай
Когда подмассив содержит 0 или 1 элементов, он уже отсортирован — рекурсия останавливается. После завершения всех рекурсивных вызовов весь массив отсортирован.
Разделение: [10, 30, 40, 50] < 70 < [80, 90]. Опорный элемент 70 теперь на позиции 4 (итоговое место).
Рекурсия влево: [10, 30, 40, 50] → уже разделён. Рекурсия вправо: [80, 90] → 80 < 90, готово. Результат: [10, 30, 40, 50, 70, 80, 90].
Сложность
Анализ сложности
Временная сложность
O(n log n) — лучший случай, когда опорный элемент всегда делит массив на две примерно равные половины. Это даёт log₂ n уровней рекурсии, каждый выполняет O(n) работы по разделению.
O(n log n) — в среднем быстрая сортировка работает очень хорошо. Случайный выбор опорного элемента обеспечивает ожидаемую глубину рекурсии O(log n), что даёт O(n log n) общей работы.
O(n²) — худший случай, когда опорный элемент всегда оказывается наименьшим или наибольшим (например, отсортированный массив с выбором последнего элемента). Это создаёт n уровней рекурсии с O(n) работы на каждом.
Пространственная сложность
O(log n) — быстрая сортировка работает на месте (без дополнительных массивов), но стек рекурсии использует O(log n) памяти в среднем. В худшем случае стек может вырасти до O(n).
Нестабильная сортировка — равные элементы могут изменить относительный порядок при разделении. Если нужна стабильность, предпочтительнее сортировка слиянием.
Выбор опорного элемента критически влияет на производительность. Последний/первый элемент — просто, но O(n²) на отсортированных данных. Случайный элемент — хорошая ожидаемая производительность. Медиана из трёх — проверяет первый, средний и последний элементы и выбирает медиану, обеспечивая хорошую практическую производительность. Introselect (используется в std::sort) — переключается на пирамидальную сортировку, если глубина рекурсии превышает 2·log(n).
Пример кода
function quickSort(arr: number[], low = 0, high = arr.length - 1): void {if (low < high) {const pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}function partition(arr: number[], low: number, high: number): number {const pivot = arr[high];let i = low - 1;for (let j = low; j < high; j++) {if (arr[j] <= pivot) {i++;[arr[i], arr[j]] = [arr[j], arr[i]];}}// Place pivot in its final position[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];return i + 1;}// Usage exampleconst unsorted = [38, 27, 43, 3, 9, 82, 10];const sorted = [...unsorted]; // Copy to avoid mutating originalquickSort(sorted);console.log(sorted); // [3, 9, 10, 27, 38, 43, 82]
Примеры использования в реальных задачах
Стандартная библиотечная сортировка
Многие языки программирования используют быструю сортировку (или её гибридные варианты) в качестве алгоритма сортировки по умолчанию. C qsort(), C++ std::sort (introsort — быстрая + пирамидальная), Java Arrays.sort() для примитивных типов — все основаны на быстрой сортировке.
Оптимизация запросов в базах данных
Базы данных используют быструю сортировку для сортировки результатов запросов в оперативной памяти. Когда оптимизатор выбирает план с сортировкой, эффективность кэша быстрой сортировки делает её быстрее сортировки слиянием для данных, помещающихся в RAM.
Порядковые статистики (K-й элемент)
Quickselect — вариант быстрой сортировки — находит k-й наименьший элемент за O(n) в среднем. Используется для нахождения медиан, перцентилей и top-K элементов без полной сортировки данных.
Численные алгоритмы
Быстрая сортировка и её варианты используются в вычислительной геометрии (сортировка точек для выпуклой оболочки), обработке сигналов и численном анализе, где критична сортировка на месте с хорошей производительностью кэша.
Задачи разделения
Шаг разделения быстрой сортировки — самостоятельная полезная операция: отделение сдавших/не сдавших студентов, разделение данных на группы выше/ниже порога или реализация задачи «голландский национальный флаг» (Sort Colors на LeetCode).