Какой худший случай сортировки для QuickSort?

Худший случай QuickSort: анализ и решение

Hudший случай для QuickSort возникает при несбалансированном разбиении (partitioning). Это происходит, когда элемент-разделитель (pivot) выбирается так, что все остальные элементы попадают в одну из двух групп, а другая остаётся пустой.

Когда происходит худший случай

Типичные сценарии:

• Сортировка уже отсортированного массива с выбором первого элемента как pivot
• Выбор pivot как минимального или максимального элемента
• Обратно отсортированный массив

Пример худшего случая

public class QuickSortWorstCase {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);      // T(n-1)
            quickSort(arr, pi + 1, high);     // T(0)
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // ❌ Худший выбор для отсортированного массива
        int i = low + 1;
        for (int j = low + 1; j <= high; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, low, i - 1);
        return i - 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

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

Худший случай: O(n²)

• Первый вызов разбивает массив на [0] и [n-1]
• Второй вызов разбивает на [0] и [n-2]
• И так далее...
• Рекуррентное соотношение: T(n) = T(n-1) + O(n) = O(n²)

Рекуррентный анализ:

T(n) = T(n-1) + T(0) + O(n)
     = T(n-1) + O(n)
     = O(n) + O(n-1) + ... + O(1)
     = O(n²)

Оптимизации для избежания худшего случая

1. Случайный выбор pivot

private static int partitionRandom(int[] arr, int low, int high) {
    int randomIndex = low + new Random().nextInt(high - low + 1);
    swap(arr, randomIndex, high);
    return partitionLomuto(arr, low, high);
}

Средняя сложность: O(n log n) с высокой вероятностью.

2. Median-of-Three

private static int selectPivotMedianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    return arr[mid];
}

Улучшает выбор pivot на практике.

3. Three-Way QuickSort (для дублирующихся элементов)

public static void quickSortThreeWay(int[] arr, int low, int high) {
    if (low < high) {
        int lt = low;
        int gt = high;
        int pivot = arr[low];
        int i = low + 1;
        
        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt, i);
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                swap(arr, i, gt);
                gt--;
            } else {
                i++;
            }
        }
        
        quickSortThreeWay(arr, low, lt - 1);
        quickSortThreeWay(arr, gt + 1, high);
    }
}

Интроспективный QuickSort (IntroSort)

IntroSort — гибридный алгоритм, используемый в стандартных библиотеках:

• Начинает как QuickSort
• Отслеживает глубину рекурсии
• При превышении лимита (обычно 2 * log(n)) переключается на HeapSort

public static void introSort(int[] arr) {
    int n = arr.length;
    int depthLimit = 2 * (int)(Math.log(n) / Math.log(2));
    introSortHelper(arr, 0, n - 1, depthLimit);
}

private static void introSortHelper(int[] arr, int low, int high, int depthLimit) {
    if (high - low < 16) {
        insertionSort(arr, low, high);  // базовый случай
    } else if (depthLimit == 0) {
        heapSort(arr, low, high);       // переключение на HeapSort
    } else {
        int pi = partition(arr, low, high);
        introSortHelper(arr, low, pi - 1, depthLimit - 1);
        introSortHelper(arr, pi + 1, high, depthLimit - 1);
    }
}

Практические выводы

QuickSort vs конкуренты в худшем случае:

• QuickSort: O(n²) (без оптимизаций)
• MergeSort: O(n log n) (гарантировано)
• HeapSort: O(n log n) (гарантировано)
• IntroSort: O(n log n) (гибридный подход)

Когда QuickSort хороший выбор:

• Средний случай: O(n log n)
• Отличная локальность кэша
• Низкое дополнительное пространство O(log n)
• На практике часто быстрее MergeSort

Заключение: Худший случай QuickSort редко встречается с хорошей стратегией выбора pivot. Java использует DualPivotQuickSort (в Arrays.sort), который комбинирует две пивоты для избежания худшего случая.