2020 競技程設教材 HackMD Book

2019 Week 6: Sorting

還記得 STL 那個方便好用的 std::sort 吧

練習：

Kick start Round A 2019 A Training
Kick start Round F 2018 A Common Anagrams
CODEFORCES 1107C Brutality
AtCoder abc117 C Streamline
CODEFORCES 1114B Yet Another Array Partitioning Task

這週會介紹一些基本的排序演算法

學習這些排序演算法，並不一定只為了解決排序問題
例如 merge sort 能應用在逆序數對問題，quick sort 的 partition 能快速找出數列中第

$k$ 大的數字，counting sort 或 radix sort 能解決更複雜的排序問題

而且這些演算法的實現想法，非常值得模仿與吸收

排序

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

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

$O(N^2)$ 排序法

如第一週所講的，演算法的優劣不僅僅只看複雜度，要看場合。

Bubble sort

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

^[1]

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

---

$O(N{\log }_{2}N)$ 排序法

下面介紹的兩個是利用分而治之 (D&C) 精神所實作的演算法

通常透過 D&C 實作的演算法，其複雜度都看得見

${\log }_2$

Merge sort

中文譯作合併排序，根據以下實作方法有不少意想不到的應用

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;
}

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

練習：

TIOJ 1080 A.逆序數對

Quick sort

中文譯作快速排序，是十分重要的演算法。

若隨機從陣列中挑一元素，然後將陣列中比此元素還大的元素們放到它的右邊，小於等於的放到左邊
此元素在這樣的操作後，是否能被擺到最適合 (排序後) 的位置？這樣的操作稱為 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;
}

^[3]

那麼對每一個數字做這樣的操作，是不是整個陣列就排序完了(i.e. 選擇的數字都被放到最適合的位置)？

基於這樣的想法，新的演算法就誕生了：

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;
}

^[4]

上面介紹的 partition 是取最右端的元素當 pivot。
若每次 partition 將當前其他元素都只到 pivot 的右邊，會使得複雜度從

$O(N{\log }_{2}N)$ 退化至

$O(N^2)$。

若改為隨機取一元素當 pivot 呢？複雜度將幾乎不可能退至

$O(N^2)$，隨著資料規模越來越大，在平均來看，不太可能每次都使得上述構造的壞測資發生，有興趣可自行證明期望的複雜度。

---

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

$O(N{\log }_{2}N)$

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

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

練習：

ZEROJUDGE a233 排序法~~~ 挑戰極限

Counting sort

counting sort，不經由比較元素大小就將元素排序好的演算法。

哦？不經由比較大小呢 Σ(ﾟдﾟ)

陣列中給定的元素將會有個明確的上界，且只適用於整數的排序

int n, count[maxn], sorted[maxn]; //maxn 為數的上界, 

for (int i = 0; i < N; i++) cin >> n, count[n]++;

for (int num = 0, i = 0; num < maxn; num++) 
  while (count[num]--) sorted[i++] = num;

複雜度是線性

$O($maxn

$)$

若每次給的

$N$ 都很小，那 maxn 定的太大就顯得慘烈
所以該演算法還是要看準場合去使用。

練習：

Sky 62 我最好的朋友^[5]
UVa OJ 11462 Age Sort^[6]

拓樸排序

有別於一般對數字或是文字做排序，這裡排序的是圖中點與邊的關係

對於排序後的數列^[7]

$v_0,v_1,...,v_n$

$\mathrm{\forall }E(v_i,v_j).i<j$ 從

$v_j$ 到

$v_i$ 沒有路徑
其中

$E(u,v)$ 代表

$u$ 到

$v$ 有一條有向邊 (

$v$ 到

$u$ 不一定有)

而圖是有向無環圖若且唯若圖有拓樸排序

根據上圖以及拓樸排序規則，有好幾種排序後的數列：
5, 7, 3, 11, 8, 2, 9, 10 (從左到右，從上到下看)
3, 5, 7, 8, 11, 2, 9, 10 (優先看小的數字)
5, 7, 3, 8, 11, 10, 9, 2 (優先看最少的邊)
7, 5, 11, 3, 10, 8, 9, 2 (優先看大的數字)
5, 7, 11, 2, 3, 8, 9, 10 (從上到下，從左到右看)
3, 7, 8, 5, 11, 10, 2, 9 (隨便選)

這邊給出其中一種排序程式碼：

bool dfs(int u) {
  stat[u] = true;

  for (int v = 0; v < n; v++) if (G[u][v]) {
    if (stat[v]) return false;

    if (!vis[v]) {
      vis[v] = true;
      if (!dfs(v)) return false;
      topo[x++] = v;
    }
  }

  stat[u] = false;
  return true;
}

其中當 stat[i] 為 true 時表示此節點的所有子孫還在拜訪中。
因此若 i 的子孫都還在拜訪中時，又拜訪到了 i，這代表此圖有環，返回 false。
要印出拓樸排序應倒著印出最終的 topo 陣列。

練習：

UVa OJ 124 Following Orders
CODEFORCES 510C Fox And Names
TIOJ 1092 A.跳格子遊戲

---

1. wikipedia/ An example of bubble sort ↩︎

2. wikipedia/ an example of merge sort ↩︎

3. wikipedia/ Animated visualization of the quickselect algorithm ↩︎

4. wikipedia/ Animated visualization of the quicksort algorithm ↩︎

5. 看得出來大家都先嘗試一波 MLE 才開始意識到此題不單純 ↩︎

6. UVa 測資頗弱, 陣列開滿用 STL sort 也能過 ↩︎

7. 數列，又或者.. 點列? ↩︎