排序

將一堆元素由"給定規則"排成一順序，稱為排序 (sort)。
例如：
5, 6, 9, 8, 2 這五個元素由小到大排為 2, 5, 6, 8, 9
a, bc, aa, ay 這四個元素由字典順序排為 a, aa, ay, bc

如果兩個一樣的元素，在排序後會發生位置互相調換，則此排序法為不穩定排序 (unstable sort)。

讀者可以只用程式語言內建的 sort 解決以下的練習

練習：

GCJ Kickstart Round F 2018 C Common Anagrams
CODEFORCES 1107C Brutality
AtCoder abc117 C Streamline
CODEFORCES 1114B Yet Another Array Partitioning Task

排序

Bubble sort

中文譯作泡泡排序
概念是陣列中每次有個泡泡(?)會從左到右將當前遇到的最大值帶至最右端

wikipedia/ An example of bubble sort

for (int i = n-1; i >= 1; i--)
  for (int j = 0; j < i; j++)
    if (a[j] > a[j+1]) swap(a[j], a[j+1]);

其中 i 為每次的最右端，
由於這次已將最大值放至最右端，下次的泡泡不需顧及這次的最右端

重覆行為至多 $n-1$ 次，就能達到排序的效果

Insertion sort

中文譯作插入排序
其精神為每次將選到的元素插入適當的位置

大部分的人玩撲克牌應該都這樣排的吧

for (int i = 1; i < n; i++)
  for (int j = i-1; j >= 0 && a[j+1] < a[j]; j--)
    swap(a[j+1], a[j]);

i 每次選一個數字，接著藉由比較的方式將其往左依序交換至適當的位置

由於在輸入規模小的時候有不錯的時間效率，插入排序也作為 STL sort 與 stdlib qsort 的擴充

練習：

GCJ Qualification Round 2018 Trouble Sort

排序

Merge sort

合併排序 (Merge sort)，是利用 D&C 之精神所完成的演算法：

每次將問題分成夠小的問題，再一一解決，是否大的問題就能被解決呢？
不是每個問題都能採用 D&C 精神解決，但對陣列排序剛好有這樣的結構；

int a[maxn], b[maxn]; // a := 欲排序陣列， b := 暫存兩子問題
int n; // 欲排序陣列長度

void mergesort(int l, int r) { // 每次陣列範圍 [l, r)
  if (r-l <= 1) return; // 當子問題足夠小，不再分割

  // 分割並求解子問題
  int m = (l+r)/2;
  mergesort(l, m);
  mergesort(m, r);

  // 合併子問題
  int p = l, q = m, i = l; // p := 左半邊的 index, q := 右半邊的 index
  copy(a+l, a+r, b+l); // 複製當前問題範圍的陣列
  
  while (i < r) {
    if (q == r  // 右邊取完了
        || (p != m && b[p] <= b[q])) // 左邊還有且左邊比較小
      a[i++] = b[p++];
    else
      a[i++] = b[q++];
  }
}

int main() {
    :
    .
  mergesort(0, n);
   
  return 0;
}

source
上圖的流程跟上面程式碼的描述是有點出入的 (要怪撰文者懶得做圖)，不過還是足以幫助理解過程。

Quick sort

快速排序 (Quick sort)，一樣是 D&C 精神的實踐：

若我們隨機從陣列中挑一數，然後將陣列中所有比此數還大的數放到他的右邊，小於等於的放到左邊，那麼此數是否在這樣的操作後，能被擺到它最適合的位置？這樣的操作稱為 partition，並且稱挑的數為 pivot：

8, 7, 2, 1, 4, 5, 5, 3, 9, 0
隨機挑一數 p = 3, index 值為 7

進行 partition：
1, 0, 2, 3, 4, 5, 5, 9, 8, 7

p 的位置被換了，那麼來驗證一下這樣的猜想：

進行 sort：
0, 1, 2, 3, 4, 5, 5, 7, 8, 9

明顯的，p 進行 partition 後，他的位置到了排序後的位置
其實這挺直觀的，從小到大排序的概念不就正是大的數字往右邊，小的數字往左邊嗎？

int a[maxn];

int partition(int l, int r) {
  int p = a[r], ls = l; // p := pivot, ls := less equal
  for (int i = l; i < r; i++)
    if (a[i] <= p) swap(a[i], a[ls++]);
  swap(a[r], a[ls]);

  return ls;
}

source

那麼如果我們對每一個數字做這樣的操作，是不是整個陣列就排序完了(i.d. 選擇的數字都被放到最適合的位置)？
基於這樣的想法，一個新的演算法就誕生了：

void quicksort(int l, int r) { // 每次陣列範圍 [l, r]
  if (l >= r) return;
  int s = partition(l, r);
  quicksort(l, s-1);
  quicksort(s+1, r);
}

int main() {
    :
    .
  quicksort(0, n-1);
  
  return 0;
}

source

以上用到的 partition 都只是取最右端的數字做 pivot，應該可以想得到，這樣能夠構造一些很糟的陣列，使得複雜度從 退化至 ，就是令每次 partition 所有元素都到 pivot 的某一邊 (極傾斜的劃分)
但若改為隨機取一數呢？複雜度會幾乎不可能退至 ，隨著資料規模越來越大，在平均來看，不太可能每次都使得上述構造的壞測資發生，有興趣可自行證明期望的複雜度。

murmur：
事實上，已經有人用"比較決策樹"，證明了只要在排序演算法中有使用到"比較大小"這般的概念，其複雜度都不可能低於

mergesort 與 quicksort 的程式碼，在每次呼叫函式時區間表示方式不同，因為：

• mergesort 用到"區間長"的需求大
• quicksort 中 partition 每次挑最右邊數字當 pivot，需要該 index 值。

而且 quicksort 每次分割問題時：

quicksort(l, s-1);
quicksort(s+1, r);

剛好這樣寫起來超優雅的 (*ﾟ∀ﾟ*)

練習：

ZERO JUDGE a233 排序法~~~ 挑戰極限