---
tags: 成大高階競技程式設計 2021
---
# 2021 Week5 - Sorting
寫程式時，我們時常會需要排序，例如當我們想使用二分搜的時候，我們先將陣列做排序之後就可以直接套用二分搜。
這週會介紹一些基本的排序演算法。
雖然 STL 中有好用的 `std::sort()`，但是學習這些演算法的概念還是對解題是有幫助的，
例如在[第三週教材](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking#%E9%80%86%E5%BA%8F%E6%95%B8%E5%B0%8D%EF%BC%88number-of-inversions%EF%BC%89)中就有提到合併排序（Merge Sort）能應用在逆序數對問題。
> 為了方便起見，下文中的 $N$ 都一律代表被搜尋的陣列的長度，
> $a_i$ 代表陣列中的索引值為 $i$ 的元素（注意 $i$ 是從 $0$ 開始）。
## 簡介排序
因為要將一堆元素根據給定的規則排成一種[順序](https://en.wikipedia.org/wiki/Order_theory)，所以稱之為排序。
例如：
* `[5, 6, 9, 8, 2]` 這 $5$ 個元素由小到大排序完後會變成 `[2, 5, 6, 8, 9]`
* `[a, bc, aa, ay]` 這 $4$ 個元素依照[字典序](https://en.wikipedia.org/wiki/Lexicographic_order)排序完後會變成 `[a, aa, ay, bc]`
> 若是一個演算法使得兩個值相同的元素排序前和排序後的相對位置不同，我們就稱這個演算法為不穩定排序（Unstable Sort）。
---
## $O(N^2)$ 排序法
### 泡沫排序（Bubble Sort）
每次都將待排序範圍內的最大值移到範圍內的最右邊，
直到待排序範圍變成空區間。
```cpp!
void bubble_sort(vector<int>& a) {
for (int i{a.size()}; i > 1; --i) // 待排序範圍：[0, i)
for (int j{1}; j < i; ++j)
if (a[j - 1] > a[j]) swap(a[j - 1], a[j]);
}
```
[^bubble_sort]
[^bubble_sort]: [wikipedia/ An example of bubble sort](https://en.wikipedia.org/wiki/Bubble_sort#/media/File:Bubble-sort-example-300px.gif)
### 插入排序（Insertion Sort）
每次都將元素插入至已排序範圍中的適當的位置。
```cpp!
void insertion_sort(vector<int>& a) {
int N{a.size()};
for (int i{1}; i < N; ++i) // 已排序範圍：[0, i)
for (int j{i}; j > 0 && a[j - 1] > a[j]; --j)
swap(a[j - 1], a[j]);
}
```
[^insertion_sort]
[^insertion_sort]: [wikipedia/ A graphical example of insertion sort](https://en.wikipedia.org/wiki/Insertion_sort#/media/File:Insertion-sort-example-300px.gif)
---
## $O(N \log{N})$ 排序法
下面介紹的演算法都是用[分治法](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking#%E5%88%86%E6%B2%BB%EF%BC%88Divide-and-Conquer%EF%BC%89)實作出來的。
:::info
只要在排序的時候有用到「比較大小」的概念，時間複雜度就不可能會小於 $O(N \log{N})$[^sort_lower_bound]。
:::
[^sort_lower_bound]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). “Introduction to Algorithms (Third Edition)”, Theorem 8.1
### 合併排序（Merge Sort）
定義父問題為排序 $[l, r)$，然後我們將父問題切分成兩個子問題：
1. 排序 $[l, m)$
2. 排序 $[m, r)$
> $m = \frac{l + r}{2}$
若是範圍內的元素少於或等於 $1$ 個，則我們就可以直接認定這個範圍已經排序完了。
```cpp!
void merge_sort(vector<int>& a, int l, int r) {
if (r - l == 1) return;
// 利用遞迴解決子問題
int m{(l + r) / 2};
merge_sort(a, l, m);
merge_sort(a, m, r);
// 將子問題的答案合併成父問題的答案
int i{l}; // 左半邊的索引值
int j{m}; // 右半邊的索引值
vector<int> tmp{};
while (i < m || j < r) {
if (i < m && (j == r || a[i] <= a[j])) tmp.push_back(a[i++]);
else tmp.push_back(a[j++]);
}
copy(tmp.begin(), tmp.end(), a.begin() + l);
}
```
```graphviz
digraph {
node [shape = record]
l1 [label = "38|27|43|3|9|82|10"]
l2_1 [label = "38|27|43"]
l2_2 [label = "3|9|82|10"]
l3_1 [label = "38"]
l3_2 [label = "27|43"]
l3_3 [label = "3|9"]
l3_4 [label = "82|10"]
l4_1 [label = "27"]
l4_2 [label = "43"]
l4_3 [label = "3"]
l4_4 [label = "9"]
l4_5 [label = "82"]
l4_6 [label = "10"]
l5_2 [label = "27|43"]
l5_3 [label = "3|9"]
l5_4 [label = "10|82"]
l6_1 [label = "27|38|43"]
l6_2 [label = "3|9|10|82"]
l7_1 [label = "3|9|10|27|38|43|82"]
l1 -> l2_1
l1 -> l2_2
l2_1 -> l3_1
l2_1 -> l3_2
l2_2 -> l3_3
l2_2 -> l3_4
l3_1 -> l6_1
l3_2 -> l4_1
l3_2 -> l4_2
l3_3 -> l4_3
l3_3 -> l4_4
l3_4 -> l4_5
l3_4 -> l4_6
l4_1 -> l5_2
l4_2 -> l5_2
l4_3 -> l5_3
l4_4 -> l5_3
l4_5 -> l5_4
l4_6 -> l5_4
l5_2 -> l6_1
l5_3 -> l6_2
l5_4 -> l6_2
l6_1 -> l7_1
l6_2 -> l7_1
}
```
### 快速排序（Quick Sort）
快速排序跟合併排序的差別在於切割子問題的方式不一樣。
定義父問題為排序 $[l, r)$，然後我們在此範圍內找出一個元素，元素值為 $pivot$，
接著將 $[l, r)$ 依照 $pivot$ 進行分隔（partition），假設分隔完後 $pivot$ 的索引值為 $p$，
我們就將父問題切割成下列兩個子問題：
1. 排序 $[l, p)$
2. 排序 $[p + 1, r)$
> $pivot$ 現在的位置已經是排序完成後他所應該在的位置。
```cpp!
// 將 [l, r) 進行分割，並回傳 pivot 的索引值
int partition(vector<int>& a, int l, int r) {
int pivot{a[l]}; // 選擇 a[l] 當作 pivot
int j{l};
for (int i{l + 1}; i < r; ++i)
if (a[i] < pivot) swap(a[i], a[++j]);
swap(a[l], a[j]);
return j;
}
void quick_sort(vector<int>& a, int l, int r) {
if (r - l < 2) return;
int p{partition(a, l, r)};
quick_sort(a, l, p);
quick_sort(a, p + 1, r);
}
```
[^quick_sort]
[^quick_sort]: [wikipedia/ Animated visualization of the quicksort algorithm](https://en.wikipedia.org/wiki/Quicksort#/media/File:Sorting_quicksort_anim.gif)
> 注意上面 gif 中的 $pivot$ 選擇方法與程式碼中的不同
#### 關於複雜度
事實上，根據選到的 $pivot$ 的值，快速搜尋的時間複雜度可能會退化成 $O(N^2)$。
若是選擇的 $pivot$ 幾乎每次都是範圍內的最大值或最小值，則切割出來的其中一個子問題的範圍其實只會比父問題少一個元素，而另一個子問題則是範圍內沒有任何元素。
下面的圖例就是在最差情況下快速排序有可能會發生的情形。
> 灰色的節點代表 $pivot$
```graphviz
digraph {
node [shape = "record"]
l1_1 [label = "6|5|4|3|2|1"]
l2_1 [label = "1|5|4|3|2"]
l2_2 [label = "6", fillcolor = gray, style = filled]
l2_3 [label = ""]
l3_1 [label = ""]
l3_2 [label = "1", fillcolor = gray, style = filled]
l3_3 [label = "5|4|3|2"]
l4_1 [label = "2|4|3"]
l4_2 [label = "5", fillcolor = gray, style = filled]
l4_3 [label = ""]
l5_1 [label = ""]
l5_2 [label = "2", fillcolor = gray, style = filled]
l5_3 [label = "4|3"]
l6_1 [label = "3"]
l6_2 [label = "4", fillcolor = gray, style = filled]
l6_3 [label = ""]
l1_1 -> l2_1
l1_1 -> l2_2
l1_1 -> l2_3
l2_1 -> l3_1
l2_1 -> l3_2
l2_1 -> l3_3
l3_3 -> l4_1
l3_3 -> l4_2
l3_3 -> l4_3
l4_1 -> l5_1
l4_1 -> l5_2
l4_1 -> l5_3
l5_3 -> l6_1
l5_3 -> l6_2
l5_3 -> l6_3
}
```
可以看到我們總共會需要遞迴 $O(N)$ 次，然後每次遞迴都需要跑一次 `partition()`，花費 $O(N)$ 的時間，因此總時間複雜度為 $O(N^2)$。
> 有許多人為了解決這個問題而提出了不同的方法，有興趣的同學可以自己去查查看。
> 關鍵字：`median of three`, `median of medians`
---
## $O(N)$ 排序法
### Counting Sort
沒有用到「比較大小」這個概念的排序法，而這個演算法的核心概念就是我們去紀錄每個值出現了幾次，而不是去記錄原本的陣列 $a$。
而排序完成的結果就是我們由小到大看每個值 $i$ 出現了幾次，我們就輸出幾次 $i$。
```cpp!
// 假設 a[i] 的範圍侷限在 0 ~ 99
void counting_sort(vector<int>& a) {
array<int, 100> cnt{}; // cnt[i] 為 i 出現的次數
for (auto ai : a) ++cnt[ai];
for (int i{0}, j{0}; i < 100; ++i)
while (cnt[i]--) a[j++] = i;
}
```
要注意到這個演算法只會用在 $a_i$ 的範圍很小的時候。
## 練習題
| Problem | tags |
| -------------------------------------------------------------------------------------------------------------------------------- | -------------------------- |
| [Trouble Sort](https://codingcompetitions.withgoogle.com/codejam/round/00000000000000cb/00000000000079cb#problem) | `Bubble Sort` |
| [ZEROJUDGE a233 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233) | `Merge Sort`, `Quick Sort` |
| [藍的競程之旅–魔法藥](https://oj.leo900807.tw/problems/7) | `Counting Sort` |
| [11462 - Age Sort](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457) | `Counting Sort` |
| [e544: 00612 - DNA Sorting](https://zerojudge.tw/ShowProblem?problemid=e544) | `Merge Sort` |
| [c431: Sort ! Sort ! Sort !](https://zerojudge.tw/ShowProblem?problemid=c431) | `Counting Sort` |
| [Hemose Shopping](https://codeforces.com/contest/1592/problem/B) | `Sort` |
| [Buggy Sorting](https://codeforces.com/contest/246/problem/A) | `Bubble Sort` |
Sign in with Wallet
Connect another wallet