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

Quicksort выбирает pivot, переставляет элементы так, чтобы меньшие/равные оказались слева, большие — справа, затем рекурсивно сортирует части.

Lomuto partition

static void quickSort(int[] values) {
    quickSort(values, 0, values.length - 1);
}
 
private static void quickSort(int[] values, int low, int high) {
    while (low < high) {
        int pivot = partition(values, low, high);
 
        // Сначала меньшая часть: ограничиваем глубину стека.
        if (pivot - low < high - pivot) {
            quickSort(values, low, pivot - 1);
            low = pivot + 1;
        } else {
            quickSort(values, pivot + 1, high);
            high = pivot - 1;
        }
    }
}
 
private static int partition(int[] values, int low, int high) {
    int pivotValue = values[high];
    int boundary = low;
 
    for (int i = low; i < high; i++) {
        if (values[i] <= pivotValue) {
            swap(values, boundary++, i);
        }
    }
    swap(values, boundary, high);
    return boundary;
}
 
private static void swap(int[] values, int i, int j) {
    int tmp = values[i];
    values[i] = values[j];
    values[j] = tmp;
}

Инвариант partition перед шагом i:

[low, boundary) <= pivot
[boundary, i)   >  pivot
[i, high)       еще не рассмотрено

После финального swap pivot стоит на окончательной позиции.

Сложность и pivot

• сбалансированные разбиения: O(n log n);
• среднее для хорошей стратегии pivot: O(n log n);
• крайне несбалансированные: O(n²);
• partition работает in-place;
• вариант выше ограничивает глубину стека до O(log n), всегда рекурсируя в меньшую часть.

Последний элемент как pivot дает худший случай на уже отсортированном массиве. На практике используют случайный pivot, median-of-three или трехстороннее разбиение для множества дубликатов.

Quicksort в этой форме нестабилен: обмены могут изменить порядок равных объектов.

См. Быстрая сортировка против сортировки слиянием.

На собеседовании

• Что гарантирует partition? Pivot на финальном месте, слева <=, справа >.
• Когда получается O(n²)? При цепочке разбиений размеров 0 и n-1.
• Стабилен ли quicksort? Обычно нет.
• Как снизить риск плохого входа? Random pivot/median-of-three и трехстороннее разбиение.
• Зачем рекурсировать в меньшую часть? Ограничить stack depth.