前言

一般的Quick Sort 都是做 2-way partition，不斷的把資料根據 pivot 位置，切割成兩邊，但在資料有很多相同數值時，效率會下降

因為切割成兩邊是指 >pivot 與 <=pivot 或是 >=pivot 與 <pivot 的情況，並沒有嚴格定義當 =pivot 的情況發生時應該怎麼做，所以當有很多一樣的數值出現在陣列中，就會發現做了一些不必要的交換而降低速度

3-way Quick sort 平均時間複雜度為 $O(NlogN)$，一樣屬於 unstable sorting

概念

Dijkstra 提出了新的演算法，從 2-way partition 變成 3-way partition
可以到 Toptal 的這個網頁觀看不同 case 的視覺化排序過程

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

把小於pivot的數值往左堆，大於pivot的數值往右堆，一樣的數值都擺在中間不要動到，就能避免發生不必要的交換了

做完往左堆和往右堆後，會紀錄兩個index回傳，而不是回傳 pivot 的最終位置

這兩個 index，一個是 lt (less than)，另一個是 gt (greater than)，而介於 lt 與 gt 之間的就是一樣的數值

想法上看起來是容易理解，網路上也有不少資料說明，可是真正在實作程式時卻有一點眉眉角角要注意

lt和gt之間的那一塊並不會丟進去做遞迴(就是一樣的數值)，每次做遞迴的只有 < lt 與 > gt 那兩塊陣列

大致的想法圖如下 (有點簡陋XD，修圖時不小心蓋到 i-- 和 gt-- )

3Way image

pivot 一樣都是選在陣列最左邊，只是分堆的判定少了等於，需要非常注意的是 lt 跟 gt 的位置

pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]

// 得到lt和gt的位置, 開一個2格的陣列或vector吃回傳值
pivotFinalPos(lt, gt) ← Partition3(A, left, right)

// 根據lt和gt的位置, Array最前面跟最後面的兩塊做遞迴, Array中間的部分是一樣的數值
// pivotFinalPos(0):lt, pivotFinalPos(1):gt
QuickSort(A, left, pivotFinalPos(0)-1)
QuickSort(A, pivotFinalPos(1)+1, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Partition2(A[1..n], left, right)
x ← A[left]   // x = pivot, 在array的最左方
gt ← right    // gt一開始設在array最右方
lt ← left     // lt一開始設在array最左方
for i from left to gt:
　// 比pivot小的數值堆到pivot的左邊
　if A[i] < x
　　swap A[i] and A[lt]
　　lt++
　// 比pivot大的數值先不斷放到最右邊(gt)
  else if A[i] > x 
    swap A[i] and A[gt]
    i--  // 從A[gt]換來的數值不一定比pivot小, 要在下一次迴圈檢查目前A[i]的值, i要先--
    gt--
pos(lt, gt)  // pos[0] = lt, pos[1] = gt
return pos

複雜度比較

大致上與 2-way Quick sort 一樣，差別在於情況如果只有 $O(1)$ 獨立數值，時間複雜度可達到 $O(N)$