Почему быстрая сортировка никогда не деградирует до O(n^2)
Быстрая сортировка может иметь сложность в худшем случае O(n2)?
На практике при определенной реализации этой сортировки этого никогда не произойдет.
Сначала вспомним, как происходит алгоритм быстрой сортировки.
- 1.поиск некоторого элемента называемого опорным.
- 2.перекидываем все элементы меньше опорного в левую часть от опорного, перекидываем все элементы большего опорного в правую часть от опорного.
- 3.рекурсивно вызываем быструю сортировку для левых и правых частей (не включай опорный), пока не дойдем до подмассивов из нуля или одного элементов (такие массивы считаются уже отсортированными).
Например, алгоритм быстрой сортировки может быть реализован так (так делать не надо, ниже будет понятно почему):
class QuickSort
{
static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
QuickSortAlgorithm(arr, 0, arr.Length - 1);
Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
}
static void QuickSortAlgorithm(int[] arr, int low, int high)
{
if (low < high)
{
// Находим правильную позицию опорного элемента
int pi = Partition(arr, low, high);
// Рекурсивно сортируем элементы до и после опорного
QuickSortAlgorithm(arr, low, pi - 1);
QuickSortAlgorithm(arr, pi + 1, high);
}
}
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++;
// Меняем местами arr[i] и arr[j]
if (i != j)
{
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
}
// Ставим опорный элемент на его законное место
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;//возвращаем новый индекс опорного элемента.
}
}
Код может быть непонятен с первого раза. Опорный элемент здесь выбирается в конце массива, но мы меняем местами i-ый и j-ый элементы. Здесь смысл в том, что есть два указателя i и j. j проходит по всем элементам массива кроме последнего, а i + 1 будет указывать на индекс куда сместиться опорный элемент после перестановок. Если все элементы больше опорного, то опорный элемент станет на первом месте. Если встретится элемент меньше опорного, то индекс опорного элемента станет правее (i++) (и arr[i] с arr[j] поменяются местами). Такой алгоритм позволяет избежать сдвигания элементов массива.
Алгоритм выше легко довести до O(n^2), если на вход дать массив уже отсортированный, при том неважно в каком порядке (по возрастанию или убыванию).
Здесь в качестве опорного элемента выбирается последний.
Допустим мы подали полностью отсортированный (по возрастанию) массив от 1 до 10 включительно.
Метод Partition поделит массив на 2 части вернет индекс 9 и поделит массив на две части: [1, 2, 3, 4, 5, 6, 7, 8, 9] и пустой массив []
Потом метод Partition для первой части вернет индекс 8 и поделит первый массив, на две части [1, 2, 3, 4, 5, 6, 7, 8] и пустой массив.
Каждый раз он алгоритм будет проходить по n, потом по n-1, потом по n - 2 элементам и т.д.
Общее количество операций:
n + (n-1) + (n-2) + ... + 2 + 1 = n(n+1)/2 ≈ n²/2 = O(n²)
Но есть несколько способов, чтобы не допустить O(n^2).
Один из них – это выбрать опорный элемент случайным образом.
static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
// ГЛАВНОЕ ОТЛИЧИЕ: случайный выбор опорного элемента
int pivotIndex = RandomPartition(arr, low, high);
// Рекурсивно сортируем левую и правую части
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
static int RandomPartition(int[] arr, int low, int high)
{
// Выбираем случайный индекс в диапазоне [low, high]
int randomIndex = rand.Next(low, high + 1);
// Меняем случайный элемент с последним
(arr[randomIndex], arr[high]) = (arr[high], arr[randomIndex]);
// Теперь используем стандартную partition с последним элементом
return Partition(arr, low, high);
}
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++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
}
а есть и другой способ – выбрать медианный элемент из первого, среднего и последнего элементов.
static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pi = MedianOfThreePartition(arr, low, high);
QuickSort(arr, low, pi - 1);
QuickSort(arr, pi + 1, high);
}
}
static int MedianOfThreePartition(int[] arr, int low, int high)
{
int mid = low + (high - low) / 2;
// Сортируем три элемента: arr[low], arr[mid], arr[high]
// чтобы arr[low] <= arr[mid] <= arr[high]
if (arr[low] > arr[mid]) (arr[low], arr[mid]) = (arr[mid], arr[low]);
if (arr[low] > arr[high]) (arr[low], arr[high]) = (arr[high], arr[low]);
if (arr[mid] > arr[high]) (arr[high], arr[mid]) = (arr[mid], arr[high]);
// Теперь arr[mid] — медиана из трёх
(arr[mid], arr[high]) = (arr[high], arr[mid]);
return Partition(arr, low, high);
}
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++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
return i;
}
На примере, почему меньше операций.
Массив из 16 элементов, pivot = медиана
Уровень 1: [16 элементов] → разделение на [8] и [8]Работа: 16 операций (проход по всем элементам)
Уровень 2: [8] [8] → разделение на [4] [4] [4] [4]Работа: 8 + 8 = 16 операций
Уровень 3: [4] [4] [4] [4] → разделение на [2] × 8Работа: 4×4 = 16 операций
Уровень 4: [2] × 8 → разделение на [1] × 16Работа: 2×8 = 16 операций
Итого: 4 уровня × 16 операций = 64 операции
Массив из 16 элементов, pivot = максимум
Уровень 1: [16 элементов] → разделение на [15] и []Работа: 16 операций
Уровень 2: [15 элементов] → разделение на [14] и []Работа: 15 операций
Уровень 3: [14 элементов] → разделение на [13] и []Работа: 14 операций
Уровень 4: [13 элементов] → разделение на [12] и []Работа: 13 операций
Итого: 16 + 15 + 14 + ... + 2 + 1 = 136 операций
Теперь давайте затестим время трех сортировок.
с сортировкой, где опорным выбирается последний элемент.
с сортировкой, где опорным выбирается случайный элемент.
с сортировкой, где опорным выбирается медианный элемент.
На моем компьютере получились такие данные:
Отсортированный массив (время в мс).
Количество элементов 1000 5000 10000 15000 Опорный элемент последний 1,3481 49,9192 126,8646 282,8915 Опорный элемент случайный 0,0633 0,4826 0,8018 1,2721 Опорный элемент медианный 0,0430 0,2728 0,5773 0,8535
Отсортированный массив в порядке убывания (время в мс).
Количество элементов 1000 5000 10000 15000 Опорный элемент последний 1,1011 30,0971 111,3659 248,0829 Опорный элемент случайный 0,0698 0,3894 0,8156 1,2952 Опорный элемент медианный 0,0705 0,4464 0,9652 1,5092
Перемешанный случайно массив (время в мс).
Количество элементов 1000 5000 10000 15000 Опорный элемент последний 0,0911 0,5372 1,2565 1,8101 Опорный элемент случайный 0,0943 0,5634 1,2180 1,8907 Опорный элемент медианный 0,0890 0,5598 1,1798 1,8461
Почти отсортированный массив (перемешено 5% массива) (время в мс).
Количество элементов 1000 5000 10000 15000 Опорный элемент последний 0,1012 0,8644 1,5544 2,8059 Опорный элемент случайный 0,0704 0,4432 0,9017 1,3402 Опорный элемент медианный 0,0707 0,4196 1,0123 1,4061