Быстрая сортировка: divide and conquer в действии

🎯 Зачем это нужно?

Представь, что ты работаешь в TikTok и нужно отсортировать миллиарды видео по количеству лайков 📱. Или в Google - ранжировать результаты поиска. Или даже проще - в школьном чате упорядочить одноклассников по алфавиту для удобного поиска.

💼 В индустрии: Quicksort используется внутри стандартных библиотек C++, Java, Python 📈 Реальные кейсы: Netflix сортирует фильмы для персональных рекомендаций 🧠 ML задачи: Поиск k-го элемента в несортированном массиве (quickselect) 🎮 Геймдев: Сортировка объектов по глубине для корректного рендеринга

📚 История вопроса

В 1960 году Тони Хоар (будущий лауреат премии Тьюринга) работал в МГУ как переводчик 🇷🇺. Ему поручили создать русско-английский словарь на компьютере. Нужно было быстро сортировать тысячи слов!

Хоар придумал гениальный алгоритм: “Выбери случайное слово, раздели словарь на две части - слова ‘до’ и ‘после’ этого слова, затем повтори для каждой части”. Так родился quicksort - один из самых элегантных алгоритмов в истории!

💡 Интуиция

Quicksort работает как игра в “Угадай число” наоборот 🎲:

1️⃣ Выбираем опорный элемент (pivot) - как “контрольную точку” 2️⃣ Делим массив: всё меньше pivot влево, всё больше вправо
3️⃣ Рекурсивно сортируем обе части 4️⃣ Объединяем результат (он уже готов!)

Это как разбор завала в комнате: сначала делим вещи на “нужные” и “ненужные”, потом разбираем каждую кучку отдельно 🧹

[МЕДИА: image_01] Описание: Анимированная схема разделения массива вокруг pivot элемента Промпт: “educational animation showing array partitioning around pivot element, colorful blocks representing numbers, arrows showing movement, divide and conquer concept visualization, modern clean style”

📐 Формальное определение

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

def quicksort(arr, low, high):
    if low < high:
        # Разделяем массив, получаем позицию pivot
        pi = partition(arr, low, high)
        
        # Рекурсивно сортируем элементы до и после pivot
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]    # Выбираем последний элемент как pivot
    i = low - 1          # Индекс меньшего элемента
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Временная сложность:

• Лучший/средний случай: O(n log n)
• Худший случай: O(n²) - когда pivot всегда минимальный/максимальный

Пространственная сложность: O(log n) для рекурсивных вызовов

🔍 Примеры с разбором

Пример 1: Сортировка чисел [8, 3, 5, 4, 7, 6, 1, 2]

Шаг 1: Выбираем pivot = 2 (последний элемент)

[МЕДИА: image_02] Описание: Пошаговая визуализация partition для массива [8,3,5,4,7,6,1,2] Промпт: “step-by-step partitioning visualization, array elements as colored blocks, pivot highlighted, pointers showing comparison process, educational diagram style”

Шаг 2: Применяем partition:

• Сравниваем 8 с 2: 8 > 2, оставляем на месте
• Сравниваем 3 с 2: 3 > 2, оставляем
• …
• Сравниваем 1 с 2: 1 ≤ 2, меняем местами с первым большим элементом

Получаем: [1, 2, 5, 4, 7, 6, 3, 8] Позиция pivot: индекс 1

Шаг 3: Рекурсивно сортируем [1] и [5, 4, 7, 6, 3, 8]

Пример 2: Почему худший случай O(n²)?

Массив [1, 2, 3, 4, 5] - уже отсортированный. Если всегда выбираем последний элемент как pivot:

• Первый вызов: pivot = 5, левая часть [1,2,3,4], правая []
• Второй вызов: pivot = 4, левая часть [1,2,3], правая []
• И так далее…

Получается n уровней рекурсии × n операций = O(n²) 😱

Решение: Случайный выбор pivot или “медиана из трёх”!

🎮 Практика

Базовый уровень 🟢

Задание 1: Примени один шаг partition к массиву [6, 2, 8, 1, 4] с pivot = 4

Задание 2: Сколько сравнений нужно для partition массива из 8 элементов?

Задание 3: Какая глубина рекурсии у quicksort в лучшем случае для массива из 16 элементов?

Продвинутый уровень 🟡

Задание 4: Реализуй функцию выбора случайного pivot:

def random_partition(arr, low, high):
    # Твой код здесь
    pass

Задание 5: Посчитай количество обменов при сортировке [5, 1, 3, 2, 4]

Задание 6: Модифицируй quicksort для подсчёта количества сравнений

Челлендж 🔴

Задание 7: Реализуй quickselect - поиск k-го наименьшего элемента за O(n) в среднем

Задание 8: Как бы ты сортировал массив, где 90% элементов одинаковые? (подсказка: 3-way partition)

⚠️ Частые ошибки

❌ Ошибка: Забыть проверить границы low < high ✅ Правильно: Всегда проверяй базовый случай рекурсии
💡 Почему: Без этого получишь бесконечную рекурсию

❌ Ошибка: Неправильно обновлять индексы в partition ✅ Правильно: Внимательно следи за переменными i и j 💡 Почему: Ошибка на единицу приведёт к неправильному разделению

❌ Ошибка: Думать, что quicksort всегда O(n log n) ✅ Правильно: В худшем случае O(n²), нужна рандомизация 💡 Почему: На отсортированных данных без рандомизации деградирует

🎓 Главное запомнить

✅ Quicksort = divide and conquer: выбери pivot, раздели, рекурсивно сортируй части ✅ Средняя сложность O(n log n), худшая O(n²), но на практике очень быстр ✅ Используется в стандартных библиотеках благодаря хорошим константам

🔗 Связь с другими темами

🔗 Назад: Сортировка слиянием (урок 266) - другой алгоритм divide and conquer 🔗 Вперёд: Анализ алгоритмов и теория сложности
🔗 ML связь: Quickselect для поиска медианы в методах машинного обучения 🔗 Практика: Сортировки в реальных системах, индексы в базах данных