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(n2). Однако, используя этот метод, в средних случаях обычно мы получаем результат вO(n log n) время.