Раздел 7. Алгоритмы

Глава 3: Алгоритмы сортировки и подготовка данных

Эффективные сортировки O(n log n): парадигмы и компромиссы

Парадигма «Разделяй и властвуй»

Алгоритмическая парадигма «Разделяй и властвуй» (Divide and Conquer) основана на рекурсивном разбиении задачи на подзадачи меньшего размера, решении этих подзадач и комбинировании результатов.

Три ключевых этапа:
Разделение: Разбиение исходной задачи на меньшие независимые подзадачи
Покорение: Рекурсивное решение подзадач
Объединение: Комбинирование результатов подзадач в решение исходной задачи

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


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

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

public class QuickSort {
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Разделение массива
            int pivotIndex = partition(arr, low, high);
            
            // Рекурсивная сортировка двух частей
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        // Выбор опорного элемента (последний)
        int pivot = arr[high];
        int i = low - 1; // Индекс меньшего элемента
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
}

Критические особенности

Неустойчивость: Меняет относительный порядок равных элементов
Зависимость от выбора pivot: Качество разделения определяет эффективность
Худший случай O(n²): При неудачном выборе pivot (уже отсортированный массив + выбор крайнего элемента)
Средний случай O(n log n): При случайных данных или хорошей стратегии выбора pivot

Стратегии выбора pivot
Случайный элемент: Устраняет худший случай для предсказуемых данных
Медиана трех: Выбор из первого, среднего и последнего элементов
Introsort: Переключение на HeapSort при глубокой рекурсии

// Улучшенный выбор pivot
private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    // Упорядочиваем три элемента
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    
    return mid; // Медиана в середине
}

Практическое применение

QuickSort доминирует в стандартных библиотеках благодаря:
Отличной средней производительности
Кэш-дружественности (последовательный доступ при partition)
Возможности оптимизаций (интроспективная сортировка)

#Java #для_новичков #beginner #algorithm #sorted #QuickSort