# Quick Sort
###### tags: `排序法`

### 概念：切!!
* 選一個 item 當 **pivot**
* 以 pivot **分左右 list**
* pivot 左邊都是比 pivot 小的 items
* pivot 右邊都是比 pivot 大的 items
* recursive 左右list

#### Recursive algorithm
* origin array = **2 6 5 3 8 7 1 0**
* find a pivot and **swap** with the rightest (or leftest) item, then would be **2 6 5 0 8 7 1 3**
* there are two indexes named itemFromLeft and itemFromRight
* **itemFromLeft** is the item **larger** than pivot
* **itemFromRight** is the item **smaller** than pivot
* two indexes starts searching the list untill
* if there is an item **larger** than pivot, then its **itemFromRight**
* if there is an item **smaller** than pivot, then its **itemFromLeft**
* 
* **swap** two items, then would be **2 1 5 0 8 7 6 3**
* **recursive** the step of find itemFromLeft and itemFromRight, then would be **2 1 0 5 8 7 6 3**
* **stop** when index of itemFromRight **>** index of itemFromRight
* 
* swap **pivot** and **itemFromLeft**, then would be **2 1 0 3 8 7 6 5**
* now all items to the left of pivot are smaller and all items to the right of pivot are larger
* recursive the left list and the right list

---

### algorithm

Quicksort(int[] arr, int left, int right){
    //判斷左指標的index小於右指標
    //在partitio是用pivot的index
    if(left<right){
        pivot_index = partitio(arr,left,right);
        Quicksort(arr,left,pivot_index);
        Quicksort(arr,pivot_index+1,right);
    }
}
partitio(int[] arr, int left, int right){
    pivot = arr[left];  //選pivot，為最小的
    leftwall = left;    //leftwall為邊界
    
    //9 7 10 3 5 8  ; 9=pivot
    for(int i=left+1; i<=right; i++){
        if(arr[i]<pivot){
            // 7<9
            swap(arr[i],arr[leftwall]);
            //7 9 10 3 5 8 
            
            
            leftwall = leftwall+1;
            //已交換過代表已排序過，所以邊界+1
            //leftwall=1
        }
        //7 3 10 9 5 8 
        //7 3 5 9 10 8
        //7 3 5 8 10 9
    }
    swap(pivot,arr[leftwall]);
    //最後把邊界與pivot換回來
    //即達到右邊比pivot大，左邊比pivot小的排序
    //7 3 5 8 9 10
    
    
    return leftwall;
    //回傳pivot index
}

---

### How to choose a pivot
* 選最左邊
* 選最右邊
* 選中間

### 複雜度
* best = average = **O(nlogn)**
* worst = **O(n*n)**，ordered list
* 額外空間 = **O(logn)**

---

參考資料：[**Michael Sambol**](https://www.youtube.com/watch?v=Hoixgm4-P4M&list=PL9xmBV_5YoZOZSbGAXAPIq1BeUf4j20pl&index=6) youtube channel