# 資料結構中「搜尋與排序」的概念、Code以及Demo
## 筆者的話
:::info
筆者的話：
紀錄一下「搜尋與排序」，這些觀念十分重要，需要記清楚，不論在考試或者未來工作，一定可以幫上讀者的忙，一方面也是筆者需要紀錄自己看。
版本號：1.0.0
說明：`Search`完成，`Sort`僅完成`初等排序`，待日後更新。
另徵求志願共筆者一同修改筆記，請直接留言，謝謝。
:::
## 目錄
一、Search and sorting
* (一)、Search
* linear search
* binary search
* (二)、Sort
* 初等排序
* inserting sort
* selection sort
* bubble sort
* shell sort
* 高等排序
---
# 一、Search and sorting
## (一)、Search
### 1. linear search
:::info
介紹：
Def:由左而右一一比較，直到找到或找不到為止。
1. 資料搜尋不需事先經過排序
2. 資料保存可以在random access(array)或者sequential access(link list)上實施
3. Time complexity:`O(n)`
:::
// linear search algorithm
// n is input data size, X is the searching key
int search(int arr[], int n, int x){
int i;
for(i=0;i<n;i++) //搜尋範圍結束與否，沒結束就繼續走
if(arr[i]==x) //找到資料
return i; //回傳值
return -1; //沒找到資料
}
### 2.Binary search
:::info
介紹：
Def:
1. 資料必須經過排序(e.g 小到大)
2. 保存在Random Access(array)上(機制)
每一次和中間位置紀錄比較
使用了`Divide and conquer`, `Prun and search`之觀念。
Time complexity:
Avg case：`O(logn)`
Best case：`O(logn)`
worst case：`O(n)`
`左半邊:x>A[m]`
`左半邊:x<A[m]`
`m=(l+u)/2`
:::
// interative
int binarysearch(int arr[], int l, int u, int x){
while(l<=u){
int m = (l+u)/2;
if(arr[m]==x)
return m;
if(arr[m]<x) //右半
1=m+1;
else //左半
r=m-1;
}
return -1; //找不到
}
// Rcursive
int BS(int arr[], int l, int u, int x){
if(l<=u){
int m=(l+u)/2;
if(arr[m]==x)
return m;
else if(arr[m]>x)
return BS(arr,l,m-1,x);
else return BS(arr,m+1,u,x)
}
return -1;
}
:::spoiler
:notebook: Recursive time function:T(n)=T(n/2)+1, T(1)=1 ∴O(logn)
:::
:::info
Time complexity分析：
| | Linear Search | Binary Search |
| -------- | -------- | -------- |
| Best | O(n) | O(logn) |
| Avg | O(n)| O(logn)|
| Worst | O(n) | O(logn)
:::
## (二)、Sort
### 初等排序
基本名詞解釋：
Sort可分：
:::warning
* Internal sorting
-- 資料量小，可以全部置於記憶體中，並完成排序工作。
* External sorting
-- 資料量過大，無法一次全部置於記憶體，Need外部儲存體幫忙進行資料保存，再進行排序，外部儲存體如磁碟。
:::
以及Stable和unstable：
:::warning
Input data有時會出現相同之鍵值的資料，e.g 5、5* or k、k+...等等，經過排序比較後，若此方法保證結果仍為5、5*或k、k+，稱此排序法為Stable, 否則是為Unstable(5或者k出現在5*, k+之前)
* Stable性質之sorting
-- Insertion, Bubble, Merge Sort; Radix, Bucket, Counting Sort
* Unstable性質之sorting
-- Selection, Shell, Quick, Heap Sort
雖然unstable比stable多做了一個沒有意義的交換動作，但時間不一定會比stable差。
:::
### 1. Insertion Sort
:bookmark_tabs: `A[i]`~`A[n]`做`(n-1)`個回合。
觀念：將`A[i]`插入到前面`(i-1)`筆已經排序好的串列，使其成為`i`筆已排序好之串列。
`Inserting sort`有`Binary insertion sort`以及`Linear insertion sort` (不細談)
-- 是否為`stable`：是`stable`
-- Time complexity：
| best case | worst case | Avg case |
| -------- | -------- | -------- |
| O(n) | O(n^2) | O(n^2) |
| T(n)=T(n-1)+1 | T(n)=T(n-1)+(n-1) | T(n)=T(n-1)+cn |
| input data是小到大排序 | 與best case相反，是大到小排序 | |
-- Space complexity：`O(1)`, 初等排序皆為`O(1)`
-- 適合使用之情況：資料量少的時候，無需使用到快速排序，只需使用到insertion sort即可。
:::success
Demo：Give num{5,3,4,2,1}
(底線表已排序)
-->Pass1:<u>3, 5</u>, 4, 2, 1
-->Pass2:<u>3, 4, 5</u>, 2, 1
-->Pass3:<u>2, 3, 4, 5</u>, 1
-->Pass4:<u>1, 2, 3, 4, 5</u>
:::
-- Code：
<!-- Insert -->
void insert(int arr[], int r, int i){
arr[-1]=r;
int j=i;
while(r<arr[j]){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=r;
}
==
<!-- insert sort -->
void insertsort(int arr[], int){
for(int i=1;i<n;i++)
insert(arr,arr[i],i-1);
}
:::info
:bookmark_tabs: 補充說明：
比較次數=(n-1)+(n-2)+...+1
=比較n(n-1)/2次
∴O(n^2)
:::
---
### 2. Selection Sort
:bookmark_tabs: `A[i]`~`A[n]`
觀念：i=i+O(n-1)作(n-1)回合；自`第i筆`到`第n筆`找出最小值`A[min]`, then與`A[i]`作SWAP.
-- 是否為`stable`：不是，其為`unstable`
-- Time complexity：
| best case | worst case | Avg case |
| -------- | -------- | -------- |
| O(n^2) | O(n^2) | O(n^2) |
-- Space complexity：`O(1)`, 初等排序皆為`O(1)`
-- 適合使用之情況：大型紀錄排序，因為每回合頂多做一次SWAP
:::success
Demo：Give num{4,5,3,2,1}
-->Pass1:<mark>1</mark>,5,3,2,<u>4</u>
-->Pass2:1,<mark>2</mark>,3,<u>5</u>,4
-->Pass3:1,2,<mark>3</mark>,5,4
-->Pass4:1,2,3,<mark>4</mark>,<u>5</u>
:::
-- Code：
<!-- 主程式 -->
void selectionsort(int arr[], int n){
int i, min;
for(i=0;i<n-1;i++){ //0到n-2
min=i; //min初值設在第i格
for(j=i+1;j<n;j++)
if(arr[j]<arr[min]) //找出min所在位置
min=j; //找出min所在位置
if(i!=min)
SWAP(&arr[min], &arr[i]);
}
}
==
<!-- SWAP副程式 -->
void SWAP(int *xp, int *yp){
int temp=*xp; //額外空間需求及min變數
*xp=*yp;
*yp=temp;
}
---
### 3. Bubble Sort
分為兩個版本，分述如下：
[版本一]
觀念：
1. 每一回合，左至右，兩兩紀錄相互比較，若前者>後者則交換前後；
2. 若某一回合無任何交換，則可以Exit(後面回合不用作)；
3. 最多作(n-1)回合；
4. 效果：每一回合當時子清單中最大值移動到最大位置。
-- 是否為`stable`：是`stable`
-- Time complexity：
| best case | worst case | Avg case |
| -------- | -------- | -------- |
| O(n) | O(n^2) | O(n^2) |
| T(n)=n-1 | T(n)=T(n-1)+(n-1) | T(n)=T(n-1)+cn |
| 資料由小到大 | 資料由大到小 | |
-- Space complexity：`O(1)`, 初等排序皆為`O(1)`
:::success
Demo：Give num{3,5,4,2,1}
-->Pass1:（3,5,4,2,1）-->3,4,2,1,<mark>5</mark>
-->Pass2:（3,4,2,1,<mark>5</mark>） -->3,2,1,<mark>4</mark>,5
-->Pass3:（3,2,1,<mark>4</mark>,5）-->2,1,<mark>3</mark>,4,5
-->Pass4:（2,1,<mark>3</mark>,4,5）-->1,<mark>2</mark>,3,4,5
result:
pass1: 3,4,2,1,<mark>5</mark>
Pass2: 3,2,1,<mark>4</mark>,5
Pass3: 2,1,<mark>3</mark>,4,5
Pass4: 1,<mark>2</mark>,3,4,5
:::
[版本二]
觀念：
1. 由左至右相互比較；
2. 效果：每一回合完，最小值降到「最低」位置。
:::success
Demo：Give num{3,5,4,2,1}
-->Pass1:（3,5,4,2,1）--><mark>1</mark>,3,5,4,2
-->Pass2:（<mark>1</mark>,3,5,4,2）-->1,<mark>2</mark>,3,5,4
-->Pass3:（1,<mark>2</mark>,3,5,4）-->1,2,<mark>3</mark>,5,4
-->Pass4:（1,2,<mark>3</mark>,,5,4）-->1,2,3<mark>4</mark>,5
result:
Pass1:<mark>1</mark>,3,5,4,2
Pass2:1,<mark>2</mark>,3,5,4
Pass3:1,2,<mark>3</mark>,5,4
Pass4:1,2,3<mark>4</mark>,5
:::
-- Code：
void bubblesort(int arr[], int n){
int i, j, flag;
for(i=0;i<n-1;i++){
flag=0;
for(j=0;j<n-i-1;j++)
if(arr[j]>arr[j+1]){
swap(&arr[j],&arr[j+1]);
flag=1;
}
if(flag==0) break;
}
}
---
### 4. Shell Sort
-- Time complexity：
| best case | worst case | Avg case |
| -------- | -------- | -------- |
| O(n^4/5) | O(n^2) | O(n^2) |
不太常見，不多做說明。
### 高等排序
### 1. Quick sort
- Quick Sort是平均情況之下最快的排序方式（時間），其採Divide and conquer策略。
-- Time complexity：
| best case | worst case | Avg case |
| -------- | -------- | -------- |
| O(nlogn) | O(n^2) | O(nlogn) |
| T(n)=2T(n/2)+cn| T(n)=T(n-1)+cn | |
-- Space complexity：O(logn) - O(n)
-- 是否為`stable`：是`unstable`
- 觀念如下
- 擇一Pivot key, 簡稱PK, 分為兩種版本，一個最左為PK，一個最右為PK.
- 為了決定PK正確位置，會進行一個名為Partition的動作，使得PK左半均小於等於PK, 右側均大於等於PK
- How to do Partition?
- [版本一] --> PK在最左
- [版本二] --> PK在最右
以下說明[版本一]：
Code：
Demo
Sign in with Wallet
Connect another wallet