Быстрая сортировка

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

Быстрая сортировка (Quick Sort) — это один из самых эффективных алгоритмов сортировки, основанный на принципе "разделяй и властвуй". Он выбирает опорный элемент и разделяет массив на две части: элементы меньше опорного и больше опорного.

Простое решение

def quick_sort(arr: list) -> list:
    """
    Реализует алгоритм быстрой сортировки.
    
    Args:
        arr: Список для сортировки
    
    Returns:
        Отсортированный список
    
    Examples:
        >>> quick_sort([3, 6, 8, 10, 1, 2, 1])
        [1, 1, 2, 3, 6, 8, 10]
        >>> quick_sort([5, 2, 8, 1, 9])
        [1, 2, 5, 8, 9]
    """
    # Базовый случай: массив с 0 или 1 элементом уже отсортирован
    if len(arr) <= 1:
        return arr
    
    # Выбираем опорный элемент (pivot)
    pivot = arr[0]
    
    # Разделяем массив на две части
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    
    # Рекурсивно сортируем части и объединяем результат
    return quick_sort(less) + [pivot] + quick_sort(greater)

Примеры использования

# Базовый пример
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # [1, 1, 2, 3, 6, 8, 10]

# Другие примеры
print(quick_sort([5, 2, 8, 1, 9]))         # [1, 2, 5, 8, 9]
print(quick_sort([1]))                     # [1]
print(quick_sort([]))                      # []
print(quick_sort([3, 3, 3]))               # [3, 3, 3]
print(quick_sort([5, 4, 3, 2, 1]))         # [1, 2, 3, 4, 5]

In-place решение (сортировка на месте)

def quick_sort_inplace(arr: list, left: int = 0, right: int = None) -> None:
    """
    In-place реализация быстрой сортировки.
    Сортирует массив без создания новых списков.
    
    Args:
        arr: Список для сортировки (изменяется на месте)
        left: Левый индекс диапазона
        right: Правый индекс диапазона
    """
    if right is None:
        right = len(arr) - 1
    
    if left < right:
        # Разделяем массив и получаем позицию опорного элемента
        partition_index = partition(arr, left, right)
        
        # Рекурсивно сортируем левую часть
        quick_sort_inplace(arr, left, partition_index - 1)
        
        # Рекурсивно сортируем правую часть
        quick_sort_inplace(arr, partition_index + 1, right)


def partition(arr: list, left: int, right: int) -> int:
    """
    Разделяет массив относительно опорного элемента.
    
    Returns:
        Индекс опорного элемента после разделения
    """
    pivot = arr[right]  # Берём последний элемент как опорный
    i = left - 1
    
    # Проходим по элементам от left до right-1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            # Меняем элементы местами
            arr[i], arr[j] = arr[j], arr[i]
    
    # Ставим опорный элемент на правильное место
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1


# Использование
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

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

1. Первый элемент (худший случай для отсортированных данных)

def quick_sort_first_pivot(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]  # Первый элемент
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    
    return quick_sort_first_pivot(less) + [pivot] + quick_sort_first_pivot(greater)

2. Случайный элемент (хороший в среднем)

import random

def quick_sort_random_pivot(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    
    # Выбираем случайный элемент
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]
    
    # Переставляем опорный элемент в начало
    arr[0], arr[pivot_index] = arr[pivot_index], arr[0]
    
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    
    return quick_sort_random_pivot(less) + [pivot] + quick_sort_random_pivot(greater)

3. Медиана из трёх (хороший баланс)

def quick_sort_median_pivot(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    
    # Находим медиану из первого, среднего и последнего элемента
    first, middle, last = arr[0], arr[len(arr) // 2], arr[-1]
    pivot = sorted([first, middle, last])[1]  # Средний элемент
    
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    
    return quick_sort_median_pivot(less) + equal + quick_sort_median_pivot(greater)

Тестирование

def test_quick_sort():
    # Базовые примеры
    assert quick_sort([3, 6, 8, 10, 1, 2, 1]) == [1, 1, 2, 3, 6, 8, 10]
    assert quick_sort([5, 2, 8, 1, 9]) == [1, 2, 5, 8, 9]
    
    # Граничные случаи
    assert quick_sort([]) == []
    assert quick_sort([1]) == [1]
    assert quick_sort([1, 1, 1]) == [1, 1, 1]
    
    # Уже отсортировано
    assert quick_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]
    
    # В обратном порядке
    assert quick_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    
    # С отрицательными числами
    assert quick_sort([-3, 5, -1, 2]) == [-3, -1, 2, 5]
    
    # С дубликатами
    assert quick_sort([3, 1, 4, 1, 5, 9, 2, 6]) == [1, 1, 2, 3, 4, 5, 6, 9]
    
    # In-place версия
    arr = [3, 6, 8, 10, 1, 2, 1]
    quick_sort_inplace(arr)
    assert arr == [1, 1, 2, 3, 6, 8, 10]
    
    print("Все тесты пройдены!")

test_quick_sort()

Анализ сложности

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

• Лучший случай: O(n log n) — равномерное разделение
• Средний случай: O(n log n)
• Худший случай: O(n²) — если опорный элемент всегда минимум/максимум

Пространственная сложность:

• Простое решение: O(n) для новых списков
• In-place: O(log n) для стека рекурсии

Сравнение производительности

import time
import random

def benchmark():
    # Создаём большой случайный массив
    arr = [random.randint(1, 1000) for _ in range(10000)]
    
    # Простая версия
    start = time.time()
    quick_sort(arr.copy())
    simple_time = time.time() - start
    
    # In-place версия
    arr_copy = arr.copy()
    start = time.time()
    quick_sort_inplace(arr_copy)
    inplace_time = time.time() - start
    
    # Встроенная сортировка Python
    start = time.time()
    sorted(arr)
    builtin_time = time.time() - start
    
    print(f"Простая версия: {simple_time:.4f}s")
    print(f"In-place версия: {inplace_time:.4f}s")
    print(f"Встроенная sorted(): {builtin_time:.4f}s")

benchmark()

Практические замечания

1. Встроенная функция sorted() обычно быстрее (использует Timsort)
2. Quick Sort отлично работает для больших массивов с хорошим выбором pivot
3. In-place версия экономит память
4. Случайный pivot защищает от худшего случая
5. Три способа выбора pivot дают разные баланс производительности

Быстрая сортировка остаётся одним из практически важных алгоритмов, который демонстрирует мощь рекурсии и стратегии "разделяй и властвуй".