# 基礎排序
2020竹C, jeeeerrrpop

---

## 生活中的例子

- 一堆散落的紙有頁碼，我們想把它重新排成一本書。
- 要把學生的成績由大到小排序。
- ........

---

{%youtube WaNLJf8xzC4%}

---

給你一個長度為n的序列
你要把他們由小到大排序

---

## Swap
先介紹基於比較、交換的演算法。

a, b = b, a

---

何謂演算法？
我們能自己想到排序演算法嗎？

---

## Bubble Sort
- 從序列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據將大的移到後面。
- 當我們比較過所有元素一次後，可以確保數值最大的元素在最後面。
- 接著扣掉陣列中的最後一個元素，接著重複上面的步驟進行兩兩比較。

---

## Bubble Sort

void BubbleSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
}

---

## Selection Sort
- 在序列中找到最小的元素，並將他與第一個元素交換。
- 在序列中找到第二小的元素(也就是撇除掉第一個元素後的最小的元素)，並將他與第二個交換。
- 重複以上操作，直到排序好。

---

## Selection Sort

void SelectionSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int min = i;
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        swap(arr[i], arr[min]);
    }
}

---

## Insertion Sort
- 想像序列中有一部分是已經排序好的，那每次新增一個元素就去看他要插在排序好的序列的哪裡。
- 對於陣列中第 i 個值，假設 0 ~ i - 1 都排序好了，把 i 往左比較找到第一個小於他的元素並插在他右邊。

---

## Insertion Sort

void InsertionSort(int arr[], int n) {
    for(int i = 1; i < n; i++) {
        int j = i - 1;
        while (j >= 0 && arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]);
            j--;
        }
    }
}

---

## Quick Sort
[Quick Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html)

---

## Merge Sort
[Merge Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)

---

## 複雜度分析
- Bubble Sort
- Best: $O(n^2)$, Worst $O(n^2)$
- Selection Sort
- Best: $O(n^2)$, Worst $O(n^2)$
- Insertion Sort
- Best: $O(n)$, Worst $O(n^2)$
- Quick Sort
- Worst $O(n^2)$, Average $O(nlogn)$
- Merge Sort
- $O(nlogn)$

---

Bubble Sort 若在迴圈執行時，判斷這一輪是否都沒有任何元素交換，可以把最優情況下的複雜度降低到 $O(n)$。
Insertion Sort 若把內層迴圈改成二分搜，就可以優化成 $O(nlogn)$。

---

有複雜度比 $O(nlogn)$ 更好的排序方法嗎？

---

基於比較的排序演算法最好就是 $O(nlogn)$

[優質文章](https://tmt514.github.io/algorithm-analysis/sorting/comparison-based-sorting.html#定理-18)

---

## 不基於比較的排序方法
- Counting Sort
- Bucket sort
- radix sort

---

## Counting Sort
- 假如數值介於 0 ~ 999，我們就開一個長度為1000的陣列去記每一種數字出現幾次。
- 最後由小到大輸出

---

## Counting Sort

const int size = 1000;
void CountingSort(int arr[], int n) {
    int cnt[size] = {0};
    for(int i = 0; i < n; i++) {
        cnt[arr[i]]++;
    }
    int id = 0;
    for(int i = 0; i < size; i++) {
        while(cnt[i] > 0) {
            arr[id] = i;
            id++;
            cnt[i]--;
        }
    }
}

---

## Counting Sort

時間複雜度是 $O(n)$ 嗎?

---

## Counting Sort
k 為數字範圍
時間複雜度 $O(n + k)$

---

## 上課練習
[neoj 369](https://neoj.sprout.tw/problem/369/)

---

既然都有 $O(nlogn)$ 的排序演算法了，那些$O(n^2)$的演算法根本不會被用到吧？

---

當序列長度不大的時候，Insertion Sort等等反而會比Quick Sort, Merge Sort還來得有效率。
[reference](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)

---

我不想自己寫SortQQ
[std::sort](http://www.cplusplus.com/reference/algorithm/sort/)

---

#include <algorithm>

int a[1000];
std::sort(a, a + 5);

---

酷酷的影片
{%youtube kPRA0W1kECg%}

---

Homework
[neoj 2219](https://neoj.sprout.tw/problem/2219/)