## 📊 排序（Sorting） ###
### 為什麼要排序？（排序的用途與動機）
* 排序可以幫助資料更容易查找或理解，例如將成績由高到低排列。
## 常見排序
### 🔸 冒泡排序（Bubble Sort）
- 一次比較兩個相鄰的元素
- 若順序錯誤就交換
- 重複多次直到全部有序
```cpp
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]);
}
}
}
}
```
#### ✅ 範例輸入：
```
原始資料：5 1 4 2 8
排序後：1 2 4 5 8
```
### 🔸 插入排序（Insertion Sort）
- 每次將一個元素插入前面已排序的部分
```cpp
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; j--;
}
arr[j + 1] = key;
}
}
```
### 🔸 選擇排序（Selection Sort）
- 每次從未排序的資料中選出最小的，放到已排序尾端
```cpp
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
```
### 🔸 快速排序（Merge Sort）
在數列中任意挑選一個數，稱為pivot，然後調整數列，使得「所有在pivot左邊的數，都比pivot還小」，而「在pivot右邊的數都比pivot大」。
接著，將所有在pivot左邊的數視為「新的數列」，所有在pivot右邊的數視為「另一個新的數列」，「分別」重複上述步驟(選pivot、調整數列)，直到分不出「新的數列」為止。<br>
<details>
<summary>👉 點我展開內容</summary>
<img src="https://hackmd.io/_uploads/S19N7lYqge.png" width="275">
以上的步驟中：
pivot可以任意挑選，在此是固定挑選數列(矩陣)的最後一個元素。
在「新的數列」上只是重複相同的步驟(選pivot、調整數列)，可以利用遞迴(recursion)處理。
所以，最關鍵的就是如何「調整數列」，江湖上尊稱其為：Partition。
</details>
#### Partition
<details>
<summary>👉 點我展開內容</summary>
<img src="https://hackmd.io/_uploads/r1luobtcxe.png" width="400">
<img src="https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/QuickSort/f4.png?raw=true" width="400">
<img src="https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/QuickSort/f5.png?raw=true" width="400">
<img src="https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/QuickSort/f6.png?raw=true" width="400">
<img src="https://hackmd.io/_uploads/Sk5_pbtcxg.png" width="400">
<img src="https://hackmd.io/_uploads/B1uRpbt9xg.png
" width="400">
<img src="https://hackmd.io/_uploads/B1uRpbt9xg.png
" width="400">
最後
<img src="https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Sorting%20series/ComparisonSort_fig/QuickSort/f12.png?raw=true
" width="400">
</details>
練習程式碼:
```cpp
#include <iostream>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int Partition(int *arr, int front, int end){
int pivot_val = // TODO
int i = // TODO
for (int j = front; j < end; j++) {
// TODO
}
// 下面兩行在做甚麼?
i++;
swap(&arr[i], &arr[end]);
return // TODO
}
void QuickSort(int *arr, int front, int end){
if (front < end) {
int pivot_pos = Partition(arr, front, end);
QuickSort(// TODO );
QuickSort(// TODO );
}
}
void PrintArray(int *arr, int size){
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int n = 9;
int arr[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};
std::cout << "original:\n";
PrintArray(arr, n);
QuickSort(arr, 0, n-1);
std::cout << "sorted:\n";
PrintArray(arr, n);
return 0;
}
```
### 🔸 合併排序（Merge Sort）
- 將陣列不斷分半後排序並合併
- 屬於「分治法」（Divide and Conquer）
```cpp
void Merge(std::vector<int> &Array, int front, int mid, int end){
// 利用 std::vector 的constructor,
// 把array[front]~array[mid]放進 LeftSub[]
// 把array[mid+1]~array[end]放進 RightSub[]
std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
RightSub(Array.begin()+mid+1, Array.begin()+end+1);
LeftSub.insert(LeftSub.end(), Max); // 在LeftSub[]尾端加入值為 Max 的元素
RightSub.insert(RightSub.end(), Max); // 在RightSub[]尾端加入值為 Max 的元素
int idxLeft = 0, idxRight = 0;
for (int i = front; i <= end; i++) {
if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
Array[i] = LeftSub[idxLeft];
idxLeft++;
}
else{
Array[i] = RightSub[idxRight];
idxRight++;
}
}
}
void MergeSort(std::vector<int> &array, int front, int end){
// front與end為矩陣範圍
if (front < end) { // 表示目前的矩陣範圍是有效的
int mid = (front+end)/2; // mid即是將矩陣對半分的index
MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
Merge(array, front, mid, end); // 將兩個subarray做比較, 並合併出排序後的矩陣
}
}
void PrintArray(std::vector<int> &array){
for (int i = 0; i < array.size(); i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {5,3,8,6,2,7,1,4};
std::vector<int> array(arr, arr+sizeof(arr)/sizeof(int));
std::cout << "original:\n";
PrintArray(array);
MergeSort(array, 0, 7);
std::cout << "sorted:\n";
PrintArray(array);
return 0;
}
```
要把數列{5,3,8,6,2,7,1,4}排序成{1,2,3,4,5,6,7,8}，Merge Sort的方法為：
- Divide：把數列「對半拆解」成兩個小數列。
- 先把{5,3,8,6,2,7,1,4}分成{5,3,8,6}與{2,7,1,4}。
- 再把{5,3,8,6}分解成{5,3}與{8,6}。
- {2,7,1,4}分解成{2,7}與{1,4}。
- 依此類推，直到每個數列剩下一個元素。
- Conquer：按照「由小到大」的順序，「合併」小數列。
- 考慮數列{5}與{3}，比較大小後，合併成數列{3,5}。
- 考慮數列{8}與{6}，比較大小後，合併成數列{6,8}。
- 考慮數列{3,5}與{6,8}，比較大小後，合併成數列{3,5,6,8}。
- 依此類推，最後，考慮數列{3,5,6,8}與{1,2,4,7}，比較大小後，合併成數列{1,2,3,4,5,6,7,8}。
即完成Merge Sort。
由圖一可以看出，在排序過程，需要先把{5}與{3}「記下來」，才能用來比較、合併出{3,5}，需要先把{3,5}與{6,8}「記下來」，才能用來比較、合併出{3,5,6,8}，因此，最直覺的方式，便是利用遞迴(recursion)來「記錄先前的狀態」：
```cpp
void MergeSort(std::vector<int> &array, int front, int end){
// front與end為矩陣範圍
if (front < end) { // 表示目前的矩陣範圍是有效的
int mid = (front+end)/2; // mid即是將矩陣對半分的index
MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
Merge(array, front, mid, end); // 將兩個subarray做比較, 並合併出排序後的矩陣
}
}
```
所以，關鍵就是Merge()的方法。
#### 函式：Merge
以圖一中，合併數列{2,7}與{1,4}為例。
Merge()的大前提：若要由小數列合併出大數列，那麼各自的小數列必須「已經排好序」。
- 例如數列{2,7}，已經「由小到大」排好序(2在7前面)，數列{1,4}也已經排好序。
Merge()的詳細步驟如下
- 建立兩個新的矩陣(稱為LeftSub[]與RightSub[])，分別記錄數列{2,7}與{1,4}。
- 並在兩個新矩陣的最後一個位置，新增一個值為「無限大」的元素。
- 這個「無限大」的元素是為了「比較」用
接著便開始「比較兩個矩陣的元素」，挑選「較小的元素」放進原矩陣Array中。
- 目前要更新的是介於Array[4]~Array[7]的矩陣元素。
- 以int front代表4，以int end代表7，表示此範圍的頭尾。
首先，替LeftSub[]與RightSub[]設立個別的index，稱為int idxLeft=0與int idxRight=0
接著比較LeftSub[idxLeft=0]與RightSub[idxRight=0]，發現後者較小，便將Array[front=4]更新成RightSub[idxRight=0]的1
由於目前的RightSub[idxRight=0]已經放進Array裡，表示該元素1
已經被調整完畢，於是便把idxRight往後移，繼續調整RightSub[]的其餘元素
最後重複此過程
最後一定有一個Array會先做完，也就是跑到最後的位置。例如此時，idxRight移動到2
，而RightSub[2]為「無限大」，如此一來便表示，RightSub[]裡的元素都已經成功地排序進Array[]裡。
接下來在比較LeftSub[]與RightSub[]時，一定會選擇LeftSub[]的元素放進Array[]。
就可以將Array[4]~Array[7]排序完成。
<span style = "color:red"> 時間複雜度是多少???</span>
最後只要將排好序的Array[0~3]再跟Array[0~4]做一樣的事情就好
### 🔸 基數排序（Radix Sort）
- 對每個位數（個位、十位、百位...）依次進行「桶排序」
- 適合非負整數且資料範圍不大的情況
```cpp
void radixSort(vector<int>& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
vector<int> output(arr.size());
int count[10] = {0};
for (int num : arr) count[(num / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
for (int i = arr.size() - 1; i >= 0; i--) {
output[--count[(arr[i] / exp) % 10]] = arr[i];
}
arr = output;
}
}
```
### 📌 補充：進階排序法
🔸 堆排序（Heap Sort）
- 使用最大堆（Max Heap）來維持最大值在堆頂
- 每次將堆頂取出並調整堆
- 涉及 Heap 結構的概念
```cpp
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
```
### [功課 8/30](https://drive.google.com/drive/folders/1mVQFo1a6xLO5nxXsdL3nZ6MiEglurDmI?usp=drive_link)
利用
1. 氣泡排序
2. 插入排序
3. 選擇排序 完成vector 5 1 4 2 8 的排序並cout到螢幕上
4. [Zerojudge a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
### [功課 9/6](https://drive.google.com/drive/folders/1vNsglAZuOy6900dCFo1Ub8dK1F98M_iu?usp=drive_link)
點擊標題進入作業繳交區
1. 完成填空部分 (繳交檔名請用 名字+功課發布日期+quicksort.cpp)
e.g. 王小明0906quicksort.cpp
```cpp=
#include <iostream>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int Partition(int *arr, int front, int end){
int pivot_val = // TODO
int i = // TODO
for (int j = front; j < end; j++) {
// TODO
}
// 下面兩行在做甚麼?
i++;
swap(&arr[i], &arr[end]);
return // TODO
}
void QuickSort(int *arr, int front, int end){
if (front < end) {
int pivot_pos = Partition(arr, front, end);
QuickSort(// TODO );
QuickSort(// TODO );
}
}
void PrintArray(int *arr, int size){
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int n = 9;
int arr[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};
std::cout << "original:\n";
PrintArray(arr, n);
QuickSort(arr, 0, n-1);
std::cout << "sorted:\n";
PrintArray(arr, n);
return 0;
}
```
2. [d190. 11462 - Age Sort](https://zerojudge.tw/ShowProblem?problemid=d190) (繳交檔名請用 名字+功課發布日期+d104.cpp)
e.g. 王小明0906d104.cpp
### [功課 9/13](https://drive.google.com/drive/folders/1Lqq9Muac28MnvdJdkLw0Q1acOzbrnJR2?usp=drive_link)
1.完成填空部分 (檔名請用 名字+功課發布日期+mergesort.cpp)
e.g. 王小明0906mergesort.cpp
```cpp=
#include <iostream>
using namespace std;
// 合併 arr[front..mid] 與 arr[mid+1..end]（兩段皆已排序）
void Merge(int *arr, int front, int mid, int end){
int nL = // TODO 提示:左段長度
int nR = // TODO 提示:右段長度
int LeftSub[nL];
int RightSub[nR];
// 複製資料到左右子陣列
// TODO 提示: 兩個for迴圈 把arr左邊的值指派給LeftSub，右邊的值指派給RightSub
int idxLeft = 0; // LeftSub 指標
int idxRight = 0; // RightSub 指標
int k = front; // arr指標
// 比較小先丟到arr
while (idxLeft < nL && idxRight < nR) {
// TODO
}
// 碰到底就把另一邊剩下的全部丟回去
while (idxLeft < nL) {
// TODO
}
while (idxRight < nR) {
// TODO
}
}
void MergeSort(int *arr, int front, int end){
if (front < end) {
int mid = ; // TODO 提示: 中間就是(頭+尾)/2
MergeSort(); // TODO 提示: 先排右邊
MergeSort(); // TODO 提示: 在排左邊(雖然順序無所謂)
Merge(); // TODO 提示: 看上面的函式就知道
}
}
void PrintArray(const int *arr, int n){
for (int i = 0; i < n; ++i) {
cout << arr[i] << (i + 1 == n ? '\n' : ' ');
}
}
int main() {
int arr[] = {5, 3, 8, 6, 2, 7, 1, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "original:\n";
PrintArray(arr, n);
MergeSort(arr, 0, n - 1);
cout << "sorted:\n";
PrintArray(arr, n);
return 0;
}
```
2. [d190. 11462 - Age Sort](https://zerojudge.tw/ShowProblem?problemid=d190) (繳交檔名請用 名字+功課發布日期+d104.cpp)
e.g. 王小明0906d104.cpp
Sign in with Wallet
Connect another wallet