Визуализация
Данные: Случайные
Схема: Хоара
Легенда цветов
Как работает быстрая сортировка
Идея алгоритма. Быстрая сортировка следует стратегии "разделяй и властвуй". Один элемент участка объявляется опорным, а остальные переставляются так, чтобы слева от опорного оказались элементы не больше него, а справа - не меньше. Эта операция называется разбиением (partition). После нее опорный стоит на своем окончательном месте, а левую и правую части сортируем тем же способом рекурсивно, пока не дойдем до участков из одного элемента.
Немного истории. Алгоритм придумал английский ученый Тони Хоар (Tony Hoare) в 1959 году. Любопытный факт: он разработал его во время стажировки в МГУ, когда работал над машинным переводом текстов с русского на английский - слова нужно было быстро сортировать для поиска в словаре.
Две схемы разбиения. Когда говорят про реализацию быстрой сортировки в коде, обычно имеют в виду конкретную схему разбиения массива. Основных схем две, и в анимации их можно переключать кнопками "Хоара" и "Ломуто" - счетчики наглядно покажут разницу.
Схема Хоара. Это оригинальная схема самого автора. Два указателя стартуют с краев участка и движутся навстречу: левый останавливается на элементе не меньше опорного, правый - на элементе не больше. Найденную "чужую" пару меняют местами. На практике эта схема экономнее: в среднем она делает примерно втрое меньше обменов и лучше держится на массивах, где много одинаковых элементов.
Схема Ломуто. Более поздний и упрощенный вариант, предложенный Нико Ломуто. Опорным берут последний элемент участка, а сам участок проходят один раз слева направо, накапливая "малые" элементы в левой части. Код получается компактнее, поэтому именно схему Ломуто чаще показывают в учебниках. Расплата - больше обменов и полное вырождение до O(n²), когда массив уже отсортирован или состоит из одинаковых чисел. Проверьте сами: выберите схему "Ломуто" и набор "Отсортированные" - глубина рекурсии дотянется до числа элементов.
- Случайные - типичный средний случай, разбиения в среднем сбалансированы: O(n log n).
- В обратном порядке - для схемы Хоара это по-прежнему быстрый случай, а Ломуто вырождается.
- Отсортированные - опасный случай для схемы Ломуто: разбиения максимально однобокие.
- Почти отсортированные - схема Хоара с опорным из середины почти не замечает подвоха.
- Одинаковые - Хоар делит участок пополам, а Ломуто скатывается в квадратичную сложность.
Сложность алгоритма
Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Ресурса у алгоритма два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
Показывает, как растет число операций (здесь это сравнения и обмены) при росте n. Лейбл "Сложность" под визуализацией - время, которое получилось фактически на ваших данных.
| Случай | Время | Комментарий |
|---|---|---|
| Лучший | O(n log n) | Опорный делит участок примерно пополам на каждом уровне |
| Средний | O(n log n) | На случайных данных разбиения в среднем сбалансированы |
| Худший | O(n²) | Разбиения однобокие: каждое откалывает лишь один элемент (схема Ломуто на отсортированных или равных данных) |
По памяти
Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(log n) | Сортировка на месте: вспомогательный массив не нужен, память уходит только на стек рекурсии - в среднем log n, в худшем случае до n |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов. Пример: сортируем учеников по оценке, а внутри одной оценки они уже стояли по алфавиту. Устойчивая сортировка сохранит алфавитный порядок внутри каждой оценки, неустойчивая - может перемешать.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Нет | Разбиение переставляет элементы через большие расстояния, поэтому равные элементы легко меняются местами и теряют исходный порядок |
Примеры реализации быстрой сортировки (Quick Sort)
Ниже представлены реализации алгоритма с использованием обеих схем разбиения: Хоара (она работает в анимации по умолчанию) и Ломуто. Вы можете сравнить их реализацию на разных языках.
Код на C (Схема Хоара)
// Разбиение по схеме Хоара: опорный - средний элемент участка
int hoare_partition(int arr[], int lo, int hi) {
int pivot = arr[(lo + hi) / 2];
int i = lo - 1, j = hi + 1;
while (1) {
// Левый указатель ищет элемент не меньше опорного
do { i++; } while (arr[i] < pivot);
// Правый указатель ищет элемент не больше опорного
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
// Оба в чужих частях - меняем местами
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
void quick_sort(int arr[], int lo, int hi) {
if (lo >= hi) return;
int p = hoare_partition(arr, lo, hi);
quick_sort(arr, lo, p);
quick_sort(arr, p + 1, hi);
}Код на Python (Схема Хоара)
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return arr
# Разбиение по схеме Хоара: опорный - средний элемент
pivot = arr[(lo + hi) // 2]
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: # ищем слева элемент не меньше опорного
i += 1
j -= 1
while arr[j] > pivot: # ищем справа элемент не больше опорного
j -= 1
if i >= j:
break
arr[i], arr[j] = arr[j], arr[i]
quick_sort(arr, lo, j)
quick_sort(arr, j + 1, hi)
return arrКод на JavaScript (Схема Хоара)
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
// Разбиение по схеме Хоара: опорный - средний элемент
const pivot = arr[(lo + hi) >> 1];
let i = lo - 1, j = hi + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // элемент не меньше опорного
do { j--; } while (arr[j] > pivot); // элемент не больше опорного
if (i >= j) break;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
quickSort(arr, lo, j);
quickSort(arr, j + 1, hi);
return arr;
}Код на C (Схема Ломуто)
int partition_lomuto(int arr[], int lo, int hi) {
// Опорный - последний элемент, идем одним проходом слева направо
int pivot = arr[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
i++;
}
}
// Ставим опорный на границу частей
int temp = arr[i]; arr[i] = arr[hi]; arr[hi] = temp;
return i;
}
void quick_sort_lomuto(int arr[], int lo, int hi) {
if (lo >= hi) return;
int p = partition_lomuto(arr, lo, hi);
quick_sort_lomuto(arr, lo, p - 1);
quick_sort_lomuto(arr, p + 1, hi);
}Код на Python (Схема Ломуто)
def partition_lomuto(arr, lo, hi):
# Опорный - последний элемент, идем одним проходом слева направо
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
# Ставим опорный на границу частей
arr[i], arr[hi] = arr[hi], arr[i]
return i
def quick_sort_lomuto(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return arr
p = partition_lomuto(arr, lo, hi)
quick_sort_lomuto(arr, lo, p - 1)
quick_sort_lomuto(arr, p + 1, hi)
return arrКод на JavaScript (Схема Ломуто)
function partitionLomuto(arr, lo, hi) {
// Опорный - последний элемент, идем одним проходом слева направо
const pivot = arr[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
// Ставим опорный на границу частей
[arr[i], arr[hi]] = [arr[hi], arr[i]];
return i;
}
function quickSortLomuto(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const p = partitionLomuto(arr, lo, hi);
quickSortLomuto(arr, lo, p - 1);
quickSortLomuto(arr, p + 1, hi);
return arr;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок Сортировка Хоара - с подробной теорией, задачами и проверочными вопросами.