Quick Sort 快速排序法

• 人如其名，是非常快的排序演算法，BigO 為 O(nlogn)。
• 使用到一個 Partition 的演算法，也可以說 Quick Sort 使用遞迴的方式去呼叫自己，並跑裡面的 Partition，來達到排序目的。
• 當 Partition 到陣列長度都為 1 時，此時已經排序完成了，換言之尚未變成 1，就是繼續執行 Partition 的動作。

目錄

• Partiton
• Quick Sort 流程
• 介紹
• BigO
• 為什麼是 O(nlogn) ?
• 參考資料

Partition

• 並不是一個排序演算法，但它可以將陣列分成三個大區塊，並且也是一種演算法
• 先選取其中一個值為 Pivot (可以理解為中間值)，比 Pivot 小的放到左邊，比 Pivot 大的放到右邊，Pivot 放在兩個區塊的中間
• Partition 後陣列會變這樣 => [ ..... 比 Pivot 小的未排序值 ..... , Pivot , ..... 比 Pivot 大的未排序值 ..... ]

Partition pseudocode (偽代碼)：
最尾端為 Pivot
i = 最左端  - 1 
開始跑迴圈 for j in range(0, 倒數第二格)
        如果 arr[ j ] < pivot
	i += 1
	對調  arr[ i ] 與 arr[ j ]  
跑完迴圈後對調 arr[ i +1 ] 與 Pivot

 

arr = [3, 99, 7, 0, 67, 32, 20, 11, 86 ,18]

def partition(l, r, arr):
  pivot = arr[r]
  i = l - 1
  for j in range(l, r):
    if arr[j] <= pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i+1], arr[r] = arr[r], arr[i+1]
  return arr

print(partition(0, len(arr)-1, arr))
# [3, 7, 0, 11, 18, 32, 20, 99, 86, 67]
# 18 是 pivot 

Partition 並不一定要將最後一項設為 Pivot，只要結果能將陣列照著 [ 小 , Pivot , 大 ] 轉換即可
傳入值 l , r 為最左及最右的 index 值，所以 for 終止值為 r，就等同於迴圈範圍到 r - 1 ( 倒數第二格 )
上方程式碼是回傳 arr，實際上在 Quick Sort 裡，則是要回傳最後 Pivot 的 index，也就是 i+1

Quick Sort 流程

nums = [3, 99, 7, 0, 67, 32, 20, 11, 86 ,18]

def partition(l, r, arr):
  pivot = arr[r]
  i = l - 1
  for j in range(l, r):
    if arr[j] <= pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
  arr[i+1], arr[r] = arr[r], arr[i+1]
  return i+1

def quickSort(l, r, arr):
  if len(arr) == 1:
    return arr
  if l < r:
    pivotIndex = partition(l, r, arr)
    quickSort(l, pivotIndex - 1, arr)
    quickSort(pivotIndex + 1, r, arr)
  return arr

print(quickSort(0, len(nums)-1, nums))
# [0, 3, 7, 11, 18, 20, 32, 67, 86, 99]

介紹

因為 partition function 會回傳 Pivot 的 index，所以以它做斷點，前與後的陣列在分別繼續做下去，
直到每個都變成長度是 1 的陣列，一個一個回傳後就會變成排序好的陣列

BigO

Worst Case Performance: O(n^2)
Best Case Performance: O(nlogn)
Average Performance: O(nlogn)

為什麼是 O(nlogn) ?

簡易說明為什麼 Quick Sort 會是 O(nlogn)
Quick Sort 是由 Partition 分到陣列長度剩下一個，此時就已經完成排序
所以 BigO 值為 Partition 的 BigO X 總共的層數
Partition 在每一層都是 O(n)
 
每一次 Partition，陣列長度都被除以 2，最後長度要變成 1 的話，總共會有 log2 n 層
因此最終結果的 BigO 為 O(nlogn)
 

參考資料：

Day16 -- Divide and Conquer - Quick Sort - iT 邦幫忙
快速排序法(Quick Sort) - HackMD
Udemy - 資料結構與演算法 (JavaScript)