Алгоритм быстрой сортировки

Быстрая сортировка (QuickSort) – классический алгоритм упорядочивания сравнением, основанный на парадигме «разделяй и властвуй». Он широко применяется из-за высокой средней эффективности, локальности ссылок (cache-friendliness) и простоты адаптации под разные типы данных и компараторы. Для подготовки к ЕГЭ по информатике знание QuickSort помогает:

1. уверенно анализировать алгоритмическую сложность;

2. работать с рекурсией и инвариантами циклов;

3. корректно проектировать функции (контракты, предусловия, постусловия);

4. разбирать псевдокод и выявлять ошибки в реализациях сортировок.

Постановка задачи и место в ЕГЭ

Задача: для массива/последовательности A длины n упорядочить элементы по возрастанию (или по заданному отношению порядка).
Связь с ЕГЭ: в вариантах встречаются задания на чтение и анализ алгоритмов сортировки, определение количества операций, работу рекурсии, оценку сложности и нахождение ошибок. Понимание QuickSort позволяет разбирать фрагменты кода с разбиением (partition), сравнивать схемы и объяснять, откуда берутся худшие случаи.

Идея алгоритма (концепт)

1. Выбрать опорный элемент (pivot).

2. Разделить массив на три части: меньше опорного, равные опорному, больше опорного (классически – на две: меньше/больше, равные «растворяются» в одной из зон).

3. Рекурсивно отсортировать «левую» и «правую» части.

4. Конкатенировать результаты (в in-place вариантах – просто обеспечить правильный порядок внутри того же массива).

Формальный контракт функции сортировки

• Предусловия: индексные границы корректны; компаратор задаёт строгий слабый порядок; элементы допускают сравнение и обмен.

• Постусловия: результат – перестановка исходных элементов; массив упорядочен согласно компаратору; побочные эффекты отсутствуют, кроме перестановок внутри массива.

• Ошибки: недетерминированный/несогласованный компаратор, выход за границы, бесконечная рекурсия из-за неверного разбиения.

Выбор опорного элемента (pivot)

• Первый/последний элемент: просто, но даёт худший случай на отсортированных/равнослучайных неблагоприятных данных.

• Случайный элемент: с большой вероятностью даёт равномерное деление и среднюю сложность O (n log n).

• Median-of-three (медиана из первого/среднего/последнего): снижает вероятность деградации на уже отсортированных данных.

• Тонкости ЕГЭ: уметь объяснить, как выбор pivot влияет на глубину рекурсии и число сравнений.

Схемы разбиения (partition) и инварианты

1. Схема Ломуто (две зоны)
   

   Идея: поддерживать границу «< pivot» и просканировать массив, меняя местами элементы, меньшие опорного, вперёд.
   Инвариант: перед текущей позицией i все элементы A[l..m-1] < pivot, а A[m..i-1] – уже просмотрены и ≥\ge≥ pivot.

   Плюсы: простота. Минусы: много обменов; плохо для массивов с большим числом равных pivot.

2. Схема Хоара (две стрелки)
   

   Идея: две индексации с концов, двигаем левый указатель вправо, пока < pivot, правый – влево, пока > pivot; при нарушении – обмен.
   Инвариант: слева от i элементы ≤\le≤ pivot, справа от j элементы ≥\ge≥ pivot; курсоры сходятся.

   Плюсы: меньше обменов, эффективнее на практике. Особенность: возвращаемое разделение не гарантирует, что pivot окажется «на месте» – нужно аккуратно рекурсировать по диапазонам.

3. Трёхпутевое разбиение (Dutch National Flag)
   

   Идея: поддерживать три зоны «< pivot | == pivot | > pivot».
   Инвариант:

   • A[l..lt-1] < pivot,

   • A[lt..i-1] == pivot,

   • A[gt+1..r] > pivot,

   • i сканирует непереработанную часть.
     Плюс: радикально снижает глубину рекурсии и число сравнений при большом числе дубликатов.

Корректность: доказательная схема

Корректность обеспечивается:

1. Полнота разбиения: каждый элемент попадает в одну из зон согласно компаратору.

2. Согласованность рекурсий: рекурсивные вызовы получают корректные подмассивы, которые строго меньше по длине, что гарантирует завершение.

3. Инварианты: на каждом шаге partition поддерживаются условия «зоны упорядоченно разделены по отношению к pivot».

4. Собираемость результата: после сортировки подзадач конкатенация зон даёт глобально упорядоченный массив.

Сложность и ресурсы

• Средний случай: O (n log n) сравнений/перестановок (с рандомизацией или удачным pivot).

• Лучший случай: O (n log n) при почти равных размерах подзадач.

• Худший случай: O(n²) – последовательное «разделение» на пустую и n−1 элементную часть (например, уже отсортированный массив при неудачном pivot).

• Память: O (log n) дополнительного стека рекурсии (в среднем) за счёт хвостовой рекурсии и сортировки меньшей части первой; худший случай – O(n) глубина стека (без защитных мер).

Практические правила написания корректной и быстрой реализации

1. Рандомизируйте выбор pivot или используйте median-of-three.

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

3. Включайте порог для вставок: на малых подмассивах (скажем, ≤16) переключайтесь на сортировку вставками – это ускоряет практическую работу.

4. Используйте трёхпутевое разбиение при большом числе дубликатов.

5. Не забывайте о компараторе: он должен задавать транзитивный, антисимметричный, связный порядок; некорректный компаратор делает результат неопределённым.

6. Следите за границами и условиями циклов в partition – частая причина ошибок (бесконечные циклы, выход за массив).

7. Избегайте лишних обменов (особенно в Ломуто) там, где достаточно перестановки указателей.

8. Тестируйте граничные случаи: пустой массив, все элементы равны, уже отсортирован/отсортирован в обратном порядке, большой массив с повторениями.

Псевдокод (трёхпутевое разбиение + гибридизация)

Partition (трёхпутевое)

partition3(A, l, r):

    pivot := A[l]

    lt := l        // граница зоны < pivot

    gt := r        // граница зоны > pivot

    i  := l + 1    // текущий сканер

    while i <= gt:

        if A[i] < pivot:

            swap A[lt], A[i]; lt += 1; i += 1

        else if A[i] > pivot:

            swap A[i], A[gt]; gt -= 1

        else:

            i += 1

    return (lt, gt) // зона равных pivot: [lt..gt]

Быстрая сортировка с порогом и хвостовой рекурсией

quickSort(A, l, r):

    while r - l + 1 > THRESHOLD:

        choosePivotAndPlaceAtA[l]  // рандомизация/median-of-three

        (lt, gt) := partition3(A, l, r)

        // сначала сортируем меньшую часть (ограничиваем стек):

        if (lt - l) < (r - gt):

            quickSort(A, l, lt-1)

            l := gt + 1

        else:

            quickSort(A, gt+1, r)

            r := lt - 1

    insertionSort(A, l, r) // малые диапазоны – вставками

Стабильность и вторичные ключи

QuickSort не является стабильным по умолчанию (относительный порядок равных элементов не гарантируется). Если стабильность критична:

• используйте стабильные алгоритмы (MergeSort);

• или применяйте «украшение-снятие украшений» (decorate-sort-undecorate): сортируйте пары (ключ, исходный_индекс).

Типичные ошибки и диагностика

• Неверные условия в циклах partition ⇒ «зацикливание».

• Рекурсивные вызовы перекрывающихся диапазонов ⇒ пропуски/дублирование.

• Выбор pivot без защиты ⇒ квадратичное время на «почти отсортированных» данных.

• Нет хвостовой рекурсии ⇒ избыточная глубина стека.

• Компаратор нарушает транзитивность ⇒ «неполный» порядок, нестабильный результат.

Мини-чек-лист для самопроверки (ЕГЭ-стиль)

• Корректно ли определены зоны после partition?

• Гарантирует ли ваш выбор pivot среднюю сложность O (n log n)?

• Ограничена ли глубина стека (сортировка меньшей части + хвостовая рекурсия)?

• Есть ли переключение на вставки для малых подмассивов?

• Протестированы ли крайние случаи и массивы с множеством дубликатов?

Пять упражнений (с ориентацией на экзаменационные навыки)

Упражнение 1. Инвариант трёхпутевого разбиения.

Сформулируйте и строго докажите (в 6–8 предложениях) инвариант partition3. Объясните, почему после завершения цикла зона [lt..gt] именно равна pivot, а соседние зоны строго меньше/строго больше.

Упражнение 2. Анализ худшего случая.

Рассмотрите QuickSort с pivot = последний элемент и схемой Ломуто на уже отсортированном по возрастанию массиве.
а) Опишите рекуррентное соотношение для числа сравнений.
б) Объясните, почему сложность становится квадратичной и как рандомизация pivot предотвращает деградацию.

Упражнение 3. Хвостовая рекурсия.

Преобразуйте рекурсивную реализацию QuickSort в «полурекурсивную» версию с одним рекурсивным вызовом (для меньшей части) и циклом для второй. Обоснуйте, почему это ограничивает глубину стека до O (log n) в среднем.

Упражнение 4. Дубликаты и производительность.

Смоделируйте мысленно работу двух вариантов:
– Ломуто (двухзонный),
– трёхпутевое разбиение,
на массиве из nnn элементов, где половина элементов равна одному и тому же значению. Сравните число обменов и глубину рекурсии качественно (без точных формул) и сделайте вывод.

Упражнение 5. Гибридизация со вставками.

Предложите критерий выбора порога THRESHOLD для переключения на сортировку вставками и аргументируйте его с учётом: накладных расходов функций, асимптотики вставок на малых массивах, локальности кэша. Сформулируйте правила тестирования корректности гибридной реализации.

Заключение

Быстрая сортировка – фундаментальный инструмент, сочетающий математическую строгость (инварианты, рекуррентные оценки) и инженерную эффективность (выбор pivot, трёхпутевое разбиение, хвостовая рекурсия, гибридизация). Для ЕГЭ её освоение развивает умение анализировать алгоритмы, обосновывать корректность и сложность, работать с границами, циклами и рекурсией. Практикуйтесь на граничных случаях, проверяйте инварианты и осваивайте несколько схем partition – это сформирует устойчивые навыки, необходимые на экзамене и в реальной разработке.