前言

Quick Sort也是Divide and Conquer的運用之一，其概念也是用到遞迴，不斷切割問題

平均時間複雜度是 $O(nlogn)$，是 unstable sorting

概念

Quick Sort 會從 array 中挑選一個 pivot(支點)，通常每次都是挑選陣列最左邊的值當 pivot

把 <=pivot 的數值都移到pivot前，>pivot 的數值移到支點後

可想而知，pivot 最後會是它應該在的位置，前面都是比它小，後面都是比它大的

所以每次切割問題的點就是 pivot 的最終位置，分成兩邊繼續挑選 pivot，重複做上述的事情

Quick Sort 也有分不同種類，而pivot的值會影響Quick Sort的效率

一般沒有特別需求的話，每次就是根據最左邊的值做 sorting

但比較好的情況會讓 pivot 的值是隨機產生的，可以應付較多的 general case

作法也很簡單，每次都從 array 隨機挑一個放到最左邊就好

大概流程如下：

  1. 挑選 pivot
  2. 將小於 pivot 的數值往 pivot 前面放，大於 pivot 的數值往 pivot 後面放
  3. 紀錄 pivot 最終位置，切割 array 成兩個部分，重複做上述流程

pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
QuickSort(A[1..n], left, right)
  if left >= right:
    return
  // 隨機挑選pivot, 因為Partition內的流程是每次都選left的值
  // 所以只要這邊傳進去的left位置的數值, 從array裡面隨機挑選然後交換就好
  k ← rand()% (right) + left  // range left~right
  swap A[left] and A[k]

  // 得到pivot最終位置
  m ← Partition2(A, left, right)

  // 根據pivot位置, 將Array拆成兩塊做遞迴
  QuickSort(A, left, m-1)
  QuickSort(A, m+1, right)
1
2
3
4
5
6
7
8
9
10
11
12
Partition2(A[1..n], left, right)
  x ← A[left]   // x = pivot, 在array的最左方
  j ← left
  for i from left+1 to r:
    // pivot先不動, 比它小的數值先堆在它右手邊, 比它大的就不需要動
    if A[i] <= x
      j ← j+1
      swap A[j] and A[i]

  // 這時候A[j]是最後一個比pivot小的數值, 將它與待在最左邊的pivot做交換
  swap A[left] and A[j]
  return j    // return pivot的最終位置

複雜度比較

時間複雜度

Quick sort 的時間複雜度大多取決於 pivot 的位置

Pivot Position Complexity Case
Equally divided $O(NlogN)$ Beat
On minimal or maximal element $O(N^2)$ Worst
Other position $O(NlogN)$ Average

如果 pivot 的位置剛好能把數列平等的切成兩份，那麼就會是 Best case

$T(N) = 2T(N/2) + cN$
$T(N) = O(NlogN)$

notes: cN = Partition 花的時間

如果 pivot 的位置剛好在數列的最小或最大值上，就會把數列切分成 0 & (N-1)，極大的不平衡

$T(N) = T(0) + T(N-1) +cN$
$T(N) = O(N^2)$

避免 worst case

  1. Middle of Three

比較 array[left]， array[middle]，array[right] 三筆資料取出中間值
取出的中間值再跟 array[left] 做交換，這時將 array[left] 設為 pivot

其實這不一定能將資料分成相等的兩邊，還是靠運氣，但至少有效避免了取到最大值與最小值的情況

  1. Random pivot

用亂數的方式隨機挑選一個數字當 pivot
這是最簡單但也可能最無法避免還是會取到最大與最小值的方法

比較靠譜的做法是再結合 Middle of Three，亂數取出三個數值然後比大小取中間

空間複雜度

best case 下用到的空間複雜度是 $O(logN)$ (遞迴深度是 $lonN$)
worst case 下用到的空間複雜度是 $O(N)$ (遞迴深度是 &N-1$)

心得

Quick Sort 的概念相對其他排序法較難理解(還是我太笨XD)，需要配合圖解或是自己紙上稍微操作一遍才比較想的通

雖然 QuickSort 的效率很好，程式碼其實也算簡潔，但它也存在一些缺點，比如當很多數值都是一樣的時候，它的速度就會下降，這是因為 Quick Sort 只考慮 <= pivot 和 > pivot 這兩種情況，如果數列中有很多一樣的數值會發生不必要的交換

所以後來 Dijkstra 提出了新的演算法，從 2-way partition 變成 3-way partition

將範圍嚴格定義成 < pivot 、 = pivot 、 > pivot ，就能以原有的效率處理special case

沒錯，就是在書本常常看到的那個待解克斯挫XD
有興趣的話，可以到我的另一篇解釋 3-way partition 的文章看看