Расскажи подробнее про любой алгоритм сортировки

Алгоритм сортировки: QuickSort (Быстрая сортировка)

QuickSort — один из самых практичных алгоритмов сортировки в производстве. Это разделяй-и-властвуй алгоритм, который в среднем работает за O(n log n), но в худшем случае может деградировать до O(n²). Благодаря хорошей локальности кэша и небольшому использованию памяти, QuickSort часто быстрее на практике, чем теоретически оптимальный MergeSort.

Основной принцип работы

QuickSort основан на идее разбиения:

1. Выбираем pivot (опорный элемент)
2. Разбиваем массив на две части: элементы < pivot и элементы > pivot
3. Рекурсивно сортируем обе части

def quicksort(arr):
    # Базовый случай
    if len(arr) <= 1:
        return arr
    
    # Выбираем pivot
    pivot = arr[len(arr) // 2]
    
    # Разбиваем на три части
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # Рекурсивная сортировка
    return quicksort(left) + middle + quicksort(right)

# Пример
arr = [64, 34, 25, 12, 22, 11, 90]
print(quicksort(arr))  # [11, 12, 22, 25, 34, 64, 90]

Оптимизированная реализация на месте (in-place)

def partition(arr, low, high):
    """Раздел массива относительно pivot"""
    pivot = arr[high]  # Берём последний элемент как pivot
    i = low - 1        # Индекс элемента меньшего pivot
    
    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

def quicksort_inplace(arr, low=0, high=None):
    """QuickSort на месте"""
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # Получаем индекс разделения
        pi = partition(arr, low, high)
        
        # Рекурсивно сортируем левую и правую части
        quicksort_inplace(arr, low, pi - 1)
        quicksort_inplace(arr, pi + 1, high)
    
    return arr

# Пример
arr = [64, 34, 25, 12, 22, 11, 90]
quicksort_inplace(arr)
print(arr)  # [11, 12, 22, 25, 34, 64, 90]

Сложность алгоритма

Анализ худшего случая

Худший случай происходит когда pivot всегда наименьший или наибольший элемент:

Первая итерация: раздел на 0 и n-1 элементы
Вторая итерация: раздел на 0 и n-2 элементы
...

Глубина рекурсии: n
Операции на каждом уровне: O(n)
Общая сложность: O(n²)

Это происходит например когда:
- Массив уже отсортирован
- Выбираем pivot = первый элемент

Стратегии выбора pivot (предотвращение худшего случая)

1. Random pivot (случайный выбор)

import random

def partition_random(arr, low, high):
    # Выбираем случайный индекс
    random_idx = random.randint(low, high)
    arr[random_idx], arr[high] = arr[high], arr[random_idx]
    return partition(arr, low, high)

# Результат: в среднем O(n log n) даже на отсортированных данных

2. Median-of-three

def median_of_three(arr, low, high):
    """Находит медиану первого, среднего и последнего элементов"""
    mid = (low + high) // 2
    
    # Выбираем медиану
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    
    # Перемещаем медиану в конец
    arr[mid], arr[high] = arr[high], arr[mid]
    return partition(arr, low, high)

3. Три пути (3-way partition)

Для массивов с дублирующимися элементами:

def partition_3way(arr, low, high):
    """Разбиение на три части: <pivot, ==pivot, >pivot"""
    pivot = arr[high]
    i = low
    k = high - 1
    j = low
    
    while j <= k:
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j += 1
        elif arr[j] > pivot:
            arr[j], arr[k] = arr[k], arr[j]
            k -= 1
        else:
            j += 1
    
    return i, k + 1  # Возвращаем диапазон равных элементов

Сравнение с другими алгоритмами

import time
import numpy as np
from scipy.stats import randint

arr = np.random.randint(0, 10000, 100000)

# QuickSort
start = time.time()
quicksort_inplace(arr.copy())
print(f"QuickSort: {time.time() - start:.4f}s")

# MergeSort
from merge_sort import merge_sort
start = time.time()
merge_sort(arr.copy())
print(f"MergeSort: {time.time() - start:.4f}s")

# Встроенный (Timsort)
start = time.time()
arr.copy().sort()  # или sorted(arr)
print(f"Timsort: {time.time() - start:.4f}s")

Результаты на практике: QuickSort обычно быстрее благодаря лучшей локальности кэша, хотя асимптотическая сложность одинакова с MergeSort.

Применение QuickSort в Data Science

1. Поиск k-ых наименьших элементов

def quickselect(arr, low, high, k):
    """Находит k-ый наименьший элемент за O(n) в среднем"""
    if low == high:
        return arr[low]
    
    pi = partition(arr, low, high)
    
    if k == pi:
        return arr[k]
    elif k < pi:
        return quickselect(arr, low, pi - 1, k)
    else:
        return quickselect(arr, pi + 1, high, k)

# Использование
arr = [64, 34, 25, 12, 22, 11, 90]
third_smallest = quickselect(arr, 0, len(arr) - 1, 2)  # 22
print(f"3-й наименьший: {third_smallest}")

2. Percentile вычисление

import numpy as np

def percentile_quickselect(arr, percentile):
    """Вычисляет percentile за O(n) в среднем"""
    k = int(len(arr) * percentile / 100)
    return quickselect(arr, 0, len(arr) - 1, k)

# Намного быстрее чем np.percentile для разовых вычислений
arr = np.random.rand(1000000)
p95 = percentile_quickselect(arr.copy(), 95)
print(f"95-й процентиль: {p95}")

Когда использовать QuickSort

Используй QuickSort когда:

• Нужна практическая скорость (встроенные Timsort/Introsort на его основе)
• Важна экономия памяти
• Данные не очень структурированы
• Нужны разовые операции сортировки

Избегай QuickSort когда:

• Нужны гарантии O(n log n) (используй MergeSort)
• Устойчивость к худшему случаю критична
• Данные уже отсортированы (используй адаптивные алгоритмы как Timsort)

Практический совет

# В продакшене используй встроенные функции
import numpy as np

# NumPy (использует Quicksort/Heapsort/Insertion sort)
result = np.sort(arr)

# Pandas (использует Quicksort/Mergesort/Heapsort)
df.sort_values(by='column', kind='quicksort')

# Python (использует Timsort — адаптивный гибрид)
sorted(arr)

QuickSort — это фундаментальный алгоритм, который демонстрирует важность разделяй-и-властвуй стратегии в программировании и науке о данных.