---
# System prepended metadata

title: 第 10 次社課講義
tags: [社課講義]

---

<style>

    .reveal .slides {
        font-size: 40px;
    }

</style>

# 南大附中資訊研究社 NFIRC 1st
## 第 10 次社課講義

2024/04/17
主講：ShiYu

---

## 課前準備

----

## 今日課程內容
# 排序演算法
## 1. 氣泡排序法
## 2. 選擇排序法
## 3. 插入排序法
## 進階：合併排序法

---

## 什麼是排序演算法？

----

## 什麼是排序演算法？
將資料以特定規則重新排列

----

### 上次已經教過了 C++ 內建的 sort 函式了
## 為什麼還要學排序演算法？

----

### 上次已經教過了 C++ 內建的 sort 函式了
## 為什麼還要學排序演算法？
<!-- 當我們用內建 sort 函式幫我們排序
我們只停留在應用而已 而沒有實際去了解其中的原理 -->
真正去學習演算法才能培養解決問題的能力

----

## 在還沒學過排序演算法之前
先請各位到前面以自己的方式嘗試排序一下撲克牌

---

## 1. 氣泡排序法 Bubble Sort
每次交換相鄰元素重複直到完成排序
動畫：https://visualgo.net/zh/sorting

----

## 實際操作

----

## 實作 Code
```cpp=
void BubbleSort()
{
    int n = v.size();
    for (int i=n; i>1; --i)
    {
        for (int j=0; j<i-1; ++j)
        {
            if (v[j] > v[j+1]) 
            {
                swap(v[j],v[j+1]);
            }
        }
    }
}
```

----

## 時間複雜度是多少？

----

## 時間複雜度是多少？
有 n 個元素要浮上來
每個元素都需要遍歷一次數列
所以為 $n^2$

---

## 2. 選擇排序法 Selection Sort

選擇最小的元素放到前面重複直到完成排序
動畫：https://visualgo.net/zh/sorting

----

## 實際操作

----

## 實作 Code

```cpp=
void SelectionSort()
{
    int n = v.size();
    for (int i=0; i<n-1;++i)
    {
        int mini = i;
        for (int j=i; j<n; ++j)
        {
            if (v[j] < v[mini])
            {
                mini = j;   
            }
        }
        swap(v[i],v[mini]);
    }
}
```

----

## 時間複雜度是多少？

----

## 時間複雜度是多少？
每次找最小的元素需要遍歷整個數列
要遍歷 n 次才能讓整個數列完成排序
所以為 $n^2$

---

## 3. 插入排序法 Insertion Sort
將未排序的元素依對應位置插入已排序好的序列
動畫：https://visualgo.net/zh/sorting

----

## 實際操作

----

```cpp=
void InsertSort()
{
    int n = v.size();
    for (int i=1; i<n;++i)
    {
        int temp = v[i], j = i-1;
        while (j >= 0 && temp < v[j])
        {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = temp;
    }
}
```

----

## 時間複雜度是多少？

----

## 時間複雜度是多少？
要遍歷 n 個元素
並往前搬動到序列中
所以為 $n^2$

---

## 進階：合併排序法 Merge Sort
一種以 分治法 為核心概念的排序演算法
不斷的將數列切分成兩個小數列
再將兩個小數列以特定方式合併成有序
透過遞迴就可完成排序
動畫：https://visualgo.net/zh/sorting

----

## 實際操作

----

```cpp=
void merge(int l, int r)
{
    int mid = (l+r)/2, tmp[r-l+1];
    for(int i=l,j=mid+1,k=0; i<=mid || j<=r; ++k)
    {
        if((v[i] <= v[j] && i <= mid) || j > r) tmp[k] = v[i++];
        else tmp[k] = v[j++];
    }
    for(int i=l,j=0; i<=r; ++i,++j) v[i] = tmp[j];
}

void MergeSort(int l, int r)
{
    if(l == r) return;
    int mid = (l+r)/2;
    MergeSort(l,mid); MergeSort(mid+1,r);
    merge(l,r);
}
```

----

## 時間複雜度是多少？

----

## 時間複雜度是多少？
每次都將數列切成兩半 $\log n$
把兩段數列合併成一段 $n$
所以是 $n \log n$

---

## 這麼多種排序演算法
## 我該選哪種？

----

## 比較各種排序演算法
| 排序演算法 | 最差時間複雜度 | 空間複雜度 |
| --- | --- | --- |
| 氣泡排序 | $O(n^2)$ | $O(1)$ |
| 選擇排序 | $O(n^2)$ | $O(1)$ |
| 插入排序 | $O(n^2)$ | $O(1)$ |
| 合併排序 | $O(n\log n)$ | $O(n)$ |

---

## 實作練習

### [ZJ a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
這題大家在之前的提單有用內建的 sort 函式寫過
可以試著用氣泡、選擇、插入排序分別來寫寫看

----

## 進階題
### [ZJ a233. 排序法 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
這題用前三種複雜度 $n^2$ 的排序演算法會 TLE
要用 Merge sort 才會過 複雜度 $n \log n$

---

## 延伸閱讀
詳細介紹 10 種不同的排序演算法
## [ShiYu Blog 文章連結](https://shiyu0318.github.io/post/Sort-Algorithm/)