DAA - быстрая сортировка

Он используется по принципу «разделяй и властвуй». Быстрая сортировка - это алгоритм выбора во многих ситуациях, так как его нетрудно реализовать. Это хорошая сортировка общего назначения, которая потребляет относительно меньше ресурсов во время выполнения.

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

Он на месте, поскольку использует только небольшой вспомогательный стек.
Требуется только n (log n) время сортировать n Предметы.
У него очень короткий внутренний контур.
Этот алгоритм был подвергнут тщательному математическому анализу, поэтому можно сделать очень точное заявление о проблемах с производительностью.

Недостатки

Это рекурсивно. Особенно, если рекурсия недоступна, реализация чрезвычайно сложна.
Это требует квадратичного (т.е. n2) времени в худшем случае.
Он хрупок, т.е. простая ошибка в реализации может остаться незамеченной и привести к плохой работе.

Быстрая сортировка работает путем разбиения заданного массива A[p ... r] на два непустых подмассива A[p ... q] а также A[q+1 ... r] так что каждый ключ в A[p ... q] меньше или равно каждому ключу в A[q+1 ... r].

Затем два подмассива сортируются рекурсивными вызовами Quick sort. Точная позиция раздела зависит от данного массива и индексаq вычисляется как часть процедуры разбиения.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Обратите внимание, что для сортировки всего массива начальный вызов должен быть Quick-Sort (A, 1, length[A])

В качестве первого шага Quick Sort выбирает один из элементов в массиве для сортировки как сводную. Затем массив разделяется по обе стороны от оси. Элементы, которые меньше или равны pivot, будут перемещаться влево, а элементы, которые больше или равны pivot, будут двигаться вправо.

Разбиение массива

Процедура разбиения перестраивает подмассивы на месте.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Анализ

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