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

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

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

  • Он на месте, поскольку использует только небольшой вспомогательный стек.

  • Для сортировки n элементов требуется только n (log n) времени.

  • У него очень короткий внутренний цикл.

  • Этот алгоритм был подвергнут тщательному математическому анализу, можно сделать очень точное заявление о проблемах производительности.

Недостатки

  • Это рекурсивно. Особенно, если рекурсия недоступна, реализация чрезвычайно сложна.

  • В худшем случае требуется квадратичное (т. Е. N2) время.

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

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

Затем два подмассива сортируются рекурсивными вызовами быстрой сортировки. Точная позиция раздела зависит от заданного массива, и индекс 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) 

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

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

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

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

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