Быстрая сортировка (Quick Sort)

Быстрая сортировка - это широко используемый алгоритм сортировки, разработанный Тони Хоаром в 1960 году и опубликованный в 1962 году. Это эффективный алгоритм "разделяй и властвуй".

Как это работает

Алгоритм быстрой сортировки работает следующим образом:

1. Выбор опорного элемента: Выберите элемент из массива, называемый "опорным".
2. Разделение: Переупорядочьте массив так, чтобы все элементы, меньшие опорного, оказались перед ним, а все элементы, большие опорного, — после него. После разделения опорный элемент находится на своей окончательной позиции. Эта операция называется "разделением".
3. Рекурсия: Рекурсивно повторите шаги выше для подмассивов элементов, меньших и больших опорного.

Псевдокод

Вот псевдокод для алгоритма быстрой сортировки:

``` function quickSort(arr, low, high) {

   if (low < high) {
       // pi - это индекс разделения, arr[pi] теперь находится на правильном месте
       pi = partition(arr, low, high);

       quickSort(arr, low, pi - 1);  // Сортировка элементов перед разделением
       quickSort(arr, pi + 1, high); // Сортировка элементов после разделения
   }

}

function partition(arr, low, high) {

   // Выбор опорного элемента (обычно последний элемент)
   pivot = arr[high];

   // Индекс меньшего элемента и указывает правильную позицию опорного элемента
   i = (low - 1);

   for (j = low; j <= high - 1; j++) {
       // Если текущий элемент меньше или равен опорному
       if (arr[j] <= pivot) {
           i++;    // Увеличение индекса меньшего элемента
           swap arr[i] and arr[j]
       }
   }
   swap arr[i + 1] and arr[high]
   return (i + 1);

} ```

Пример

Давайте рассмотрим пример сортировки массива `[10, 7, 8, 9, 1, 5]` с использованием быстрой сортировки:

1. Выбираем опорный элемент (например, последний элемент `5`).
2. Разделяем массив: `[1, 5, 8, 9, 7, 10]` (после разделения `5` находится на своей правильной позиции).
3. Рекурсивно сортируем подмассивы `[1]` и `[8, 9, 7, 10]`.

Временная сложность

Временная сложность быстрой сортировки зависит от выбора опорного элемента.

• Лучший случай: $O(n \log n)$ (когда опорный элемент делит массив на две равные части).
• Средний случай: $O(n \log n)$
• Худший случай: $O(n^2)$ (когда опорный элемент всегда является наименьшим или наибольшим элементом).

Преимущества и недостатки

Преимущества:

• Эффективна в среднем случае.
• Сортирует на месте (обычно).
• Хорошо работает с кешем памяти.

Недостатки:

• В худшем случае имеет квадратичную сложность.
• Не стабильна (порядок равных элементов может измениться).
• Рекурсивная, что может привести к переполнению стека для больших массивов (хотя этого можно избежать с помощью итеративной реализации).

Выбор опорного элемента

Выбор опорного элемента играет важную роль в производительности быстрой сортировки. Некоторые стратегии включают:

• Выбор первого элемента.
• Выбор последнего элемента.
• Выбор случайного элемента.
• Выбор медианы из трех (первый, средний и последний элементы).

Когда использовать

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