Какая временная сложность у быстрой сортировки в худшем случае?

Ответ на вопрос о временной сложности быстрой сортировки

В худшем случае временная сложность алгоритма быстрой сортировки (QuickSort) составляет O(n²), где n — количество элементов в сортируемом массиве.

Подробный анализ

Быстрая сортировка — это алгоритм «разделяй и властвуй», который работает следующим образом:

1. Выбирается опорный элемент (pivot).
2. Массив разбивается на две части: элементы меньше опорного и элементы больше опорного.
3. Рекурсивно сортируются обе части.

Когда возникает худший случай?

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

• Уже отсортированный или обратно отсортированный массив при выборе первого или последнего элемента в качестве опорта.
• Все элементы равны (если реализация не оптимизирована).
• Постоянный выбор минимального или максимального элемента в качестве опорта.

В этой ситуации каждый рекурсивный вызов обрабатывает подмассив, уменьшенный всего на один элемент, что приводит к глубине рекурсии O(n) и общей сложности O(n²).

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

// Пример массива, где худший случай проявляется при выборе первого элемента как опора
int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8};

// Процесс разделения будет выглядеть так:
// Первый вызов: pivot = 1, левая часть = [], правая часть = [2,3,4,5,6,7,8]
// Второй вызов: pivot = 2, левая часть = [], правая часть = [3,4,5,6,7,8]
// И так далее... Каждый раз обрабатывается подмассив размером (n-1)

Как избежать худшего случая?

На практике быстрая сортировка редко работает за O(n²) благодаря оптимизациям:

1. Случайный выбор опорного элемента:

   private static int ChoosePivotRandom(int[] arr, int low, int high)
   {
       Random rand = new Random();
       return rand.Next(low, high + 1);
   }
   

2. Медиана трёх (выбор опора среди первого, среднего и последнего элементов):

   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; // Средний элемент теперь медиана
   }
   

3. Гибридные подходы: комбинация с сортировкой вставками для малых подмассивов.

Средний и лучший случаи

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

Практическое значение

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

• Хорошей константе скрытой в O-нотации.
• Локальности ссылок (эффективное использование кэша процессора).
• Алгоритмическим оптимизациям, применяемым в реальных реализациях (например, в .NET Array.Sort() использует интроспективную сортировку — IntroSort, которая сочетает быструю сортировку, пирамидальную сортировку и сортировку вставками).

// Пример реализации быстрой сортировки на C# с выбором случайного опора
public 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 randomIndex = new Random().Next(low, high + 1);
    Swap(arr, randomIndex, 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;
}

private static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Вывод

Таким образом, формально худший случай быстрой сортировки имеет сложность O(n²), но благодаря современным оптимизациям этот случай становится статистически маловероятным в практике. Именно поэтому быстрая сортировка остается одним из самых популярных и эффективных алгоритмов сортировки общего назначения, применяемым во многих стандартных библиотеках, включая .NET Framework.