Урок 9.3 — Быстрая сортировка (Quick Sort)

Разделяй и властвуй (Divide and Conquer) — это стратегия, в которой задача разбивается на меньшие подзадачи того же типа, решаются они, а затем результаты объединяются.

Quick Sort работает так:

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

Магия в том, что после разделения pivot оказывается на своём окончательном месте. И левая, и правая части сортируются независимо. Объединять результаты не нужно — они уже на своих местах.

Выбор pivot критически важен для скорости Quick Sort. Удачный выбор — и алгоритм работает за O(n log n). Неудачный — деградирует до O(n²).

Стратегии выбора pivot:

В нашей реализации будем использовать последний элемент как pivot (для простоты), а потом обсудим, как улучшить до случайного выбора.

Partition — это ключевая операция в Quick Sort. Она переставляет элементы массива так, чтобы:

• Все элементы меньше pivot оказались слева
• Все элементы больше или равные pivot — справа
• Pivot оказался на своём окончательном месте

Самый популярный алгоритм partition — схема Ломуто (Lomuto) или схема Хоара (Hoare). Мы рассмотрим схему Ломуто — она проще для понимания.

static int Partition(int[] arr, int left, int right)
{
    // Выбираем последний элемент как pivot
    int pivot = arr[right];

    // i — граница, слева от которой элементы меньше pivot
    int i = left - 1;

    // Проходим по всем элементам, кроме pivot
    for (int j = left; j < right; j++)
    {
        // Если текущий элемент меньше или равен pivot
        if (arr[j] <= pivot)
        {
            i++;  // расширяем границу
            // Меняем местами arr[i] и arr[j]
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }

    // Ставим pivot на своё место — между меньшими и большими
    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);

    // Возвращаем индекс, на котором стоит pivot
    return i + 1;
}

Разберём на примере. Массив [10, 7, 8, 9, 1, 5], pivot = последний = 5:

Начало: [10, 7, 8, 9, 1, 5], pivot = 5, i = -1

j=0: arr[0]=10, 10 <= 5? Нет → ничего не делаем
j=1: arr[1]=7,  7 <= 5? Нет → ничего
j=2: arr[2]=8,  8 <= 5? Нет → ничего
j=3: arr[3]=9,  9 <= 5? Нет → ничего
j=4: arr[4]=1,  1 <= 5? Да → i=0, меняем arr[0] и arr[4]: [1, 7, 8, 9, 10, 5]

После цикла: ставим pivot на место i+1 = 1.
Меняем arr[1] и arr[5]: [1, 5, 8, 9, 10, 7]

Возвращаем i+1 = 1 (индекс pivot)
Результат: слева от 5 — только 1 (меньше), справа — всё остальное (больше или равно).

Обрати внимание: после partition pivot (5) стоит на своём окончательном месте. Дальше нам нужно рекурсивно отсортировать левую часть (индексы 0..0) и правую часть (индексы 2..5).

Рассмотрим массив [10, 80, 30, 90, 40, 50, 70]. Quick Sort с pivot = последний элемент.

Вызов QuickSort(arr, 0, 6):
  [10, 80, 30, 90, 40, 50, 70]  pivot=70
  Partition: → [10, 30, 40, 50, 80, 90, 70]
  Ставим pivot: → [10, 30, 40, 50, 70, 90, 80]  pivotIndex=4
  Рекурсия: QuickSort(arr, 0, 3) и QuickSort(arr, 5, 6)

QuickSort(arr, 0, 3):
  [10, 30, 40, 50]  pivot=50
  Partition: → [10, 30, 40, 50]  pivotIndex=3
  Рекурсия: QuickSort(arr, 0, 2) и QuickSort(arr, 4, 3) — пусто

QuickSort(arr, 0, 2):
  [10, 30, 40]  pivot=40
  Partition: → [10, 30, 40]  pivotIndex=2
  Рекурсия: QuickSort(arr, 0, 1) и пусто

QuickSort(arr, 0, 1):
  [10, 30]  pivot=30
  Partition: → [10, 30]  pivotIndex=1
  Рекурсия: QuickSort(arr, 0, 0) — 1 элемент, возврат.
             QuickSort(arr, 2, 1) — пусто, возврат.

QuickSort(arr, 5, 6):
  [90, 80]  pivot=80
  Partition: → [80, 90]  pivotIndex=5
  Рекурсия: QuickSort(arr, 5, 4) — пусто.
             QuickSort(arr, 6, 6) — 1 элемент, возврат.

Результат: [10, 30, 40, 50, 70, 80, 90]

Дерево рекурсии выглядит так:

                        [10, 80, 30, 90, 40, 50, 70]
                      /                              \
          [10, 30, 40, 50]                          [90, 80]
          /              \                          /        \
    [10, 30, 40]        [50]                    [80]         [90]
    /          \
  [10]        [30, 40]
              /      \
            [30]     [40]

Теперь соединим Partition и рекурсию в полную реализацию Quick Sort:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 10, 80, 30, 90, 40, 50, 70 };

        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));

        QuickSort(arr, 0, arr.Length - 1);

        Console.WriteLine("Отсортированный: " + string.Join(", ", arr));
    }

    static void QuickSort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            // Разделяем массив и получаем индекс pivot
            int pivotIndex = Partition(arr, left, right);

            Console.WriteLine($"  pivot={arr[pivotIndex]} на [{pivotIndex}] → " +
                              string.Join(", ", arr));

            // Рекурсивно сортируем левую часть
            QuickSort(arr, left, pivotIndex - 1);

            // Рекурсивно сортируем правую часть
            QuickSort(arr, pivotIndex + 1, right);
        }
    }

    static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];  // последний элемент — pivot
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] <= pivot)
            {
                i++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }

        // Ставим pivot на место
        (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);

        return i + 1;
    }
}

// Вывод:
// Исходный массив: 10, 80, 30, 90, 40, 50, 70
//   pivot=70 на [4] → 10, 30, 40, 50, 70, 90, 80
//   pivot=50 на [3] → 10, 30, 40, 50, 70, 90, 80
//   pivot=40 на [2] → 10, 30, 40, 50, 70, 90, 80
//   pivot=30 на [1] → 10, 30, 40, 50, 70, 90, 80
//   pivot=80 на [6] → 10, 30, 40, 50, 70, 80, 90

Улучшенная версия со случайным выбором pivot (чтобы избежать худшего случая):

static Random _rand = new Random();

static int PartitionRandom(int[] arr, int left, int right)
{
    // Выбираем случайный индекс между left и right
    int randomIndex = _rand.Next(left, right + 1);

    // Меняем случайный элемент с последним (наш pivot)
    (arr[randomIndex], arr[right]) = (arr[right], arr[randomIndex]);

    // Дальше — стандартный Partition с pivot = arr[right]
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }

    (arr[i + 1], arr[right]) = (arr[right], arr[i + 1]);
    return i + 1;
}

static void QuickSortRandom(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivotIndex = PartitionRandom(arr, left, right);
        QuickSortRandom(arr, left, pivotIndex - 1);
        QuickSortRandom(arr, pivotIndex + 1, right);
    }
}

Со случайным pivot вероятность худшего случая (O(n²)) становится практически нулевой. Это стандартная практика для production-кода.

Для реального использования Quick Sort обычно применяют несколько оптимизаций:

1. Случайный pivot — избегает худшего случая на отсортированных массивах.
2. Switch на Insertion Sort — для маленьких подмассивов (< 10-20 элементов) используем Insertion Sort. Он быстрее на малых данных.
3. Трехстороннее разделение (3-way partition) — если много повторяющихся элементов, делим на три части: < pivot, == pivot, > pivot. Это улучшает производительность на данных с множеством дубликатов.
4. Хвостовая рекурсия (tail recursion) — вместо двух рекурсивных вызовов, делаем рекурсию только для меньшей части, а большую обрабатываем итеративно. Экономит память стека.

static void QuickSortOptimized(int[] arr, int left, int right)
{
    const int INSERTION_THRESHOLD = 15;

    while (left < right)
    {
        // Оптимизация 1: для маленьких массивов — Insertion Sort
        if (right - left + 1 < INSERTION_THRESHOLD)
        {
            InsertionSort(arr, left, right);
            break;
        }

        // Оптимизация 2: случайный pivot
        int pivotIndex = PartitionRandom(arr, left, right);

        // Оптимизация 3: рекурсия только для меньшей части
        if (pivotIndex - left < right - pivotIndex)
        {
            QuickSortOptimized(arr, left, pivotIndex - 1);
            left = pivotIndex + 1;  // большая часть — итеративно
        }
        else
        {
            QuickSortOptimized(arr, pivotIndex + 1, right);
            right = pivotIndex - 1;
        }
    }
}

static void InsertionSort(int[] arr, int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Такая реализация уже близка к тому, что используется в Introsort. На практике она будет работать очень быстро и безопасно.

Проверь понимание Quick Sort.