Quick Sort: быстрая сортировка

Quick Sort (быстрая сортировка) — один из самых эффективных алгоритмов для сортировки массивов в памяти. Его придумал Тони Хоар в 1959 году, и спустя десятилетия он остается стандартом во многих языках программирования (в том числе в Go).

Принцип работы (разделяй и властвуй):

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

Ключевая особенность: алгоритм работает «на месте» (in-place), не требуя выделения дополнительных массивов. Это делает его быстрым и экономичным по памяти.

Рассмотрим Quick Sort на примере

Для наглядности буду использовать код задачи sort colors, который я решил на NeetCode. Добавил комментарии для лучшего понимания.

func sortColors(nums []int) {
       fmt.Println("До сортировки:", nums)
       quickSort(nums, 0, len(nums)-1)
       fmt.Println("После сортировки:", nums)
}

func quickSort(nums []int, left, right int) {
       // Базовый случай: если границы сошлись или пересеклись — сортировать нечего
       if left >= right {
             return
       }

       // Выбираем опорный элемент (pivot) — берем середину среза
       pivot := nums[(left+right)/2]

       // Устанавливаем указатели
       i, j := left, right

       // Основной цикл разделения
       for i <= j {
             // Двигаем левый указатель вправо, пока элемент меньше опорного
             for pivot > nums[i] {
                    i++
             }
             // Двигаем правый указатель влево, пока элемент больше опорного
             for pivot < nums[j] {
                    j--
             }

             // Если указатели не пересеклись — меняем элементы местами
             if i <= j {
                    nums[i], nums[j] = nums[j], nums[i]
                    i++ // сдвигаем левый указатель
                    j-- // сдвигаем правый указатель
             }
       }

       // Рекурсивно сортируем левую часть (от left до j)
       quickSort(nums, left, j)
       // Рекурсивно сортируем правую часть (от i до right)
       quickSort(nums, i, right)
}

Что тут происходит?

1. Выбор pivot — берется опорный элемент из середины среза. Это простой и надежный способ избежать худшего случая O(n²) на почти отсортированных данных.
2. Два указателя — i движется слева направо, j — справа налево. Они ищут пару элементов, которые стоят «не на своих местах» (слева — больше опорного, справа — меньше).
3. Обмен — когда такая пара найдена, элементы меняются местами.
4. Рекурсия — после разделения массив разбит на две части. Все элементы до j меньше или равны опорному, все после i — больше или равны. Осталось отсортировать каждую часть рекурсивно.

О-большое

Почему O(n²) в худшем случае?

Если опорный элемент каждый раз оказывается минимальным или максимальным, разделение получается неравномерным. Алгоритм вырождается в пузырьковую сортировку. Это случается, если:

• массив уже отсортирован;
• массив отсортирован в обратном порядке;
• pivot выбирается неудачно (например, всегда первый элемент).

В нашей реализации pivot берется из середины, что на практике почти всегда дает хорошее разделение.

Память

Quick Sort требует O(log n) дополнительной памяти за счет рекурсивных вызовов (глубина рекурсии в лучшем и среднем случае). В худшем случае глубина рекурсии может достигать O(n), но современные реализации используют оптимизации (например, хвостовую рекурсию) или переходят на другой алгоритм при малых размерах подмассивов.

Когда использовать Quick Sort?

• Данные хранятся в памяти (массив, срез), а не в связанном списке.
• Нужна быстрая сортировка «на месте».
• Дополнительная память критична (например, при работе с большими объемами данных).

Когда лучше выбрать другой алгоритм?

• Если нужна стабильная сортировка (сохраняющая порядок равных элементов) — лучше взять Merge Sort.
• Если данные уже почти отсортированы — сортировка вставками может оказаться быстрее.
• Если данные не помещаются в память — используются внешние сортировки (например, многопутевое слияние).

Резюме

Quick Sort — это баланс между скоростью, простотой и экономией памяти. Он не идеален (худший случай O(n²) никто не отменял), но на реальных данных показывает себя одним из лучших. Именно поэтому он стал стандартом во многих языках программирования.