Учебники

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

Июль 31, 2018

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

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

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

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

  • У него очень короткая внутренняя петля.

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

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

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

У него очень короткая внутренняя петля.

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

Недостатки

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

  • Это требует квадратичного (т.е. n2) времени в худшем случае.

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

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

Это требует квадратичного (т.е. 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) времени.

36
Share: