Quick Sort Algorithm 快速排序法
2022-10-23 23:55:38
# 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
> ```
>  
> 
> 
> 
> ``` python
> 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 流程
``` python
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 邦幫忙](https://ithelp.ithome.com.tw/articles/10241650)
[快速排序法(Quick Sort) - HackMD](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FB1SPnfRq_)
Udemy - 資料結構與演算法 (JavaScript)
點擊複製文章連結
X