---
tags: 成大高階競技程式設計 2020, ys
---
:+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1:
2020 Week 5: Sorting
=
這週介紹一些基本的排序演算法
學習這些排序演算法,並**不一定**只為了解決排序問題
例如 merge sort 能應用在逆序數對問題,quick sort 的 partition 能快速找出數列中第 $k$ 大的數字,counting sort 或 radix sort 能解決**更複雜**的排序問題
> 而且這些演算法的實現想法,非常值得模仿與吸收
# 排序
將一堆元素由"*給定規則*"排成一[順序](https://en.wikipedia.org/wiki/Order_theory),稱為排序 (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
中文譯作泡泡排序
概念是陣列中每次有個泡泡(?)會從左到右將當前遇到的**最大值**帶至**最右**端
![](https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)[^bubble_sort_gif]
```cpp
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
中文譯作插入排序
其精神為每次將選到的元素插入適當的位置
> 大部分的人玩撲克牌應該都這樣排的吧
![](https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif) [^insertion_sort_gif]
```cpp
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
](https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard/00000000000079cb)
---
# $O(N\log_2N)$ 排序法
下面介紹的兩個是利用分而治之 (D&C) 精神所實作的演算法
> 通常透過 D&C 實作的演算法,其複雜度都看得見 $\log_2$
## Merge sort
中文譯作合併排序,根據以下實作方法有不少意想不到的應用
![](https://i.imgur.com/h39N4SM.png)
```cpp
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;
}
```
![](https://i.imgur.com/MxfXHyI.gif) [^1]
上圖流程跟程式碼的描述是有點出入的 ~~(要怪筆者懶得做圖)~~,不過足以幫助理解過程。
#### 練習:
[TIOJ 1080 A.逆序數對](https://tioj.ck.tp.edu.tw/problems/1080)
## 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 後,他的位置到了排序後的位置
>這挺直觀的,從小到大排序的概念就正是大數字往右邊,小數字往左邊
```cpp
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;
}
```
![](https://i.imgur.com/4MQKD9J.gif) [^2]
那麼對每一個數字做這樣的操作,是不是整個陣列就排序完了?
> 選擇的數字都被放到最適合的位置
基於這樣的想法,新的演算法就誕生了:
```cpp
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;
}
```
![](https://i.imgur.com/oW2QlrB.gif) [^3]
上面介紹的 partition 是取**最右端**的元素當 pivot。
若**每次** partition 將其他元素都放到 pivot 的右邊,會使複雜度從 $O(N\log_2N)$ 退化至 $O(N^2)$。
> 每次要搬動 $O(n)$ 個元素,共挑選 $O(n)$ 次 pivot
若改為隨機取一元素當 pivot 呢?複雜度將幾乎不可能退至 $O(N^2)$,隨著資料規模越來越大,在平均來看,不太可能每次都使得上述構造的壞測資發生,有興趣可自行證明期望的複雜度。
---
> 事實上,只要在排序中用到"*比較大小*"的概念,複雜度不可能低於 $O(N\log_2N)$
mergesort 與 quicksort 的程式碼,在每次呼叫函式時區間表示方式不同,因為:
- mergesort 用到"*區間長*"的需求大
- quicksort 中 partition 每次挑最右邊數字當 pivot,需要該 index 值。
#### 練習:
[ZEROJUDGE a233 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
# Counting sort
counting sort,**不經由比較**元素大小就將元素排序好的演算法。
>哦?不經由比較大小呢 Σ(゚д゚)
陣列中給定的元素將會有個明確的上界,且只適用於整數的排序
```cpp
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` 定的太大就顯得慘烈
>所以該演算法還是要看準場合去使用。
#### 練習:
[NCKU OJ 7 藍的競程之旅--魔法藥](https://oj.leo900807.tw/problems/7)
[Sky 62 我最好的朋友](https://pc2.tfcis.org/sky/index.php/problem/view/62)[^4]
[UVa OJ 11462 Age Sort](https://uva.onlinejudge.org/external/114/11462.pdf)[^age_sort]
# Topological sort (拓樸排序)
> 建議將同樣[第五週的 Graph Structures](/@nckuacm/BJ6l2P2UL) 讀過再讀此章,不然會違反拓樸排序規則(?)
有別於一般對數字或是文字做排序,這裡排序的是圖中點與邊的關係
對於排序後點的數列 $v_0,v_1,...,v_n$
有 $\forall (v_i, v_j) \in E. i < j$ 從 $v_j$ 到 $v_i$ **沒有[路徑](/@nckuacm/BJ6l2P2UL#Graph)**
或是說,$\forall (u, v) \in E. u$ 在排序中要在 $v$ 之前
> $(u, v) \in E$ 代表 $u$ 到 $v$ 有條有向邊,但 $v$ 到 $u$ 不一定有邊
![](https://i.imgur.com/ALZIkFx.png)
根據上圖以及拓樸排序規則,有好幾種排序後的數列:
`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` (隨便選)
而==圖是有向無環圖若且唯若圖有拓樸排序==
> 有向無環圖英文為 Directed Acyclic Graph (DAG)
也就是說想找圖中的拓樸排序,前提圖必須是個 DAG,若*發現環則違反條件*
## Kahn's algorithm
根據規則,入度為 $0$ 的點必定可放進**拓樸排序數列**中的**最前端**
> 入度 $0$ 的點不會有邊連向他,所以不會有點比他排更前面 (除其他入度 $0$ 的點)
```cpp
queue<int> q;
for(int i = 0; i < n; i++)
if(deg[v[i]] == 0) q.push(v[i]), topo.push_back(v[i]);
```
當這些點排好後,接著是被他們所連向的入度為 $1$ 的點,可依序排進拓樸排序數列
> 因為這些入度為 $1$ 的點也沒有其他點能排到他們之前了
```cpp
while(q.size()) {
int u = q.front(); q.pop();
for(int i = 0; i < n; i++) {
if(!E[u][v[i]]) continue; // u 到 v[i] 沒有向邊
if(deg[v[i]] == 1) topo.push_back(v[i]);
}
}
```
看看上述讓入度為 $1$ 的點加入拓樸排序數列的動機
所以對於還不能排進拓樸排序數列的點 $v$,有若干個點 $u$ 連向 $v$
但是一旦所有 $u$ 都已進入拓樸排序,$v$ 就可以進入拓樸排序數列中
> 怎樣知道目前有幾個 $u$ 已進入拓樸排序?
每次一個連向 $v$ 的 $u$ 進入拓樸排序,$v$ 的入度就可以減 $1$
```cpp
while(q.size()) {
int u = q.front(); q.pop();
topo.push_back(u);
for(int i = 0; i < n; i++) {
if(!E[u][v[i]]) continue;
deg[v[i]]--;
if(deg[v[i]] == 0) q.push(v[i]);
}
}
```
## Depth-first search postorder
反過來想,若是某點沒有任何**後繼點**,那麼可以直接把它加入拓樸排序數列的**最尾端**
依循此法,可以逆著把拓樸排序給造出來
也就是當某點的所有後繼點都已在拓樸排序中,那它就能加入拓樸排序數列
> 這些後繼點的其他子孫後繼點都得在拓樸排序數列中
```cpp
void dfs(int u) {
for(int i = 0; i < n; i++) {
if(!E[u][v[i]] || vis[v[i]]) continue; // 沒邊或已拜訪過
vis[v[i]] = true;
dfs(v[i]);
}
topo.push_back(u);
}
```
因為此排序是逆著造出的,所以要將順序倒過來:
```cpp
reverse(topo.begin(), topo.end());
```
<!--
```cpp
bool dfs(int u) {
stat[u] = true;
for(int i = 0; i < n; i++) {
if(!E[u][v[i]]) continue;
if(stat[v]) return false;
if(vis[v]) continue;
vis[v] = true;
if(!dfs(v)) return false;
topo.push_back(v);
}
stat[u] = false;
return true;
}
```
其中當 `stat[i]` 為 `true` 時表示此節點的所有子孫還在拜訪中。
因此若 `i` 的子孫都還在拜訪中時,又拜訪到了 `i`,這代表此圖有環,返回 `false`。
要印出拓樸排序應倒著印出最終的 `topo` 陣列。
-->
#### 練習:
:::warning
給定圖,判斷其是否有環
:::
[UVa OJ 124 Following Orders](https://uva.onlinejudge.org/external/1/124.pdf)
[CODEFORCES 510C Fox And Names](http://codeforces.com/problemset/problem/510/C)
[TIOJ 1092 A.跳格子遊戲](https://tioj.ck.tp.edu.tw/problems/1092)
[^1]: [wikipedia/ an example of merge sort](https://en.wikipedia.org/wiki/Merge_sort#/media/File:Merge-sort-example-300px.gif)
[^2]: [wikipedia/ Animated visualization of the quickselect algorithm](https://en.wikipedia.org/wiki/Quickselect#/media/File:Selecting_quickselect_frames.gif)
[^3]: [wikipedia/ Animated visualization of the quicksort algorithm](https://en.wikipedia.org/wiki/Quicksort#/media/File:Sorting_quicksort_anim.gif)
[^4]: 看得出來大家都先嘗試一波 MLE 才開始意識到此題不單純
[^bubble_sort_gif]: [wikipedia/ An example of bubble sort](https://en.wikipedia.org/wiki/Bubble_sort#/media/File:Bubble-sort-example-300px.gif)
[^insertion_sort_gif]: [wikipedia/ A graphical example of insertion sort](https://en.wikipedia.org/wiki/Insertion_sort#/media/File:Insertion-sort-example-300px.gif)
[^age_sort]: UVa 測資頗弱, 陣列開滿用 STL sort 也能過