[排序介紹] 快速排序 Quick Sort

快速排序法（Quick Sort）可以就字面意思來理解，很快速地排好大量需排序資料，算是實用性很高的算法。

想法

基本想法：從 \(A_1, A2, \dots, A_n\) 中，隨機挑一個 \(A_p\) 當基準點（pivot element），比 \(A_p\) 小的就放左邊，反之放右邊。

過程基本上就是 divide and conquer，也就是說把大問題分成小問題再處理。我們把資料分成兩邊，希望每邊的規模可以越來越小。以這樣的概念來看，worst case 便是其中一邊完全沒有資料（也就是資料的規模完全沒有變小）。換句話說，\(A_p\) 這個點怎麼挑、如何挑到有代表性的元素，就變得很重要。

如何避免worst case？

盡量找到一個（排序後）比較中間的元素。

ex：在 sequence 中挑三、五個元素，取他的中間數作為 pivot element。（但也有可能數字一樣的很多，像是1, 2, 3, 4, 9, 9, 9, 9, 9, 9,9 這種，結果都挑到最大的之類的）

也就是說 pivot element 不必是正中間，只要左右各佔一個比例就可以了。

比較的元素

左邊的每個元素都和 \(x\) 做過比較
右邊的每個元素都和 \(x\) 做過比較
一旦分割成左、右兩個部分，左邊和右邊之元素不會做任何的比較。

講解

一樣上圖講解一下實際操作XD

以下是我們要排序的數列，有 index i 和 j 移動，紅框是目前我們挑中的 pivot。

我們會把所有比 pivot 小的全往前丟到左手邊，i 就是是紀錄左手邊最後被丟過來的元素的 index，為的是最後我們能夠把 pivot 丟到這個 index 後面一格，而 j 是目前輪到的元素。

接下來我們一步一步看排序怎麼執行：

Step 1：9 大於 5，不用動，j 移動至下一格。

Step 2：4 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換，j 移動至下一格。

Step 3：1 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。

Step 4：6 大於 5，不用動，j 移動至下一格。

Step 5：7 大於 5，不用動，j 移動至下一格。

Step 6：3 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。

Step 7：8 大於 5，不用動，j 移動至下一格。

Step 8：2 小於 5，要丟到左手邊，i 先往前一格，i 和 j 元素互相交換。

Step 9：最後因為 j 已經抵達 pivot 的前一格了，結束整個迴圈。最後一個步驟就是 pivot 要移到中間，所以 i 一樣要 +1，移動到下一格後，再把 pivot 元素往左邊丟（pivot 和 index=1 元素互換），基本上這一輪就大功告成。

應該可以感受到我們不會太在乎 pivot 前（左手邊）或 pivot 後（右手邊）的元素排序，只在乎左邊是不是都是比 pivot 小，右手邊是不是都比 pivot 大，之後黃色和藍色此生不會再互相比較。

最後我們再把左右兩邊分開，黃色組和藍色組各自以上面的邏輯操作，組別將會越拆越小。

實際操作

Quick sort 會有兩個主要操作：

進行排序

QuickSort(A, p, r): //排序陣列A裡index從p到r的部分
  if p < r:
    q = Partition(A, p, r)
    QuickSort(A, p, q - 1)
    QuickSort(A, q + 1, r)

分割陣列

Partition(A, p, r):
  x = A[r]  //把第r個位置的值記為x
  i = p - 1
  for j = p to r - 1:
    if A[j] ≤ x: //看目前要檢查的元素是不是小於x（第r個位置的值）
      i = i + 1
      exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

Best
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n\log(n))\)

Average
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n\log(n))\)

Worst
空間複雜度：\(O(\log(n))\)
時間複雜度：\(O(n^2)\)

#include <vector>
using namespace std;

void quickSortHelper(vector<int> &array, int startIdx, int pivotIdx);
int partition(vector<int> &array, int startIdx, int pivotIdx);

vector<int> quickSort(vector<int> array) {
  quickSortHelper(array, 0, array.size() - 1);
  return array;
}

void quickSortHelper(vector<int> &array, int startIdx, int pivotIdx){
  int median;
  
  if (startIdx < pivotIdx){
    median = partition(array, startIdx, pivotIdx);
    quickSortHelper(array, startIdx, median - 1);
    quickSortHelper(array, median + 1, pivotIdx);
  }
}

int partition(vector<int> &array, int startIdx, int pivotIdx){
  int pivotValue = array[pivotIdx];
  int i = startIdx - 1;
  
  for (int j = startIdx; j <= (pivotIdx - 1); j++){
    if (array[j] <= pivotValue){
      i = i + 1;
      swap(array[i], array[j]);
    }
  }
  swap(array[i+1], array[pivotIdx]);
  
  return i + 1;
}