---
# System prepended metadata

title: 資料結構中「搜尋與排序」的概念、Code以及Demo
tags: [Data Structure]

---

# 資料結構中「搜尋與排序」的概念、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：

![image](https://hackmd.io/_uploads/S1MIhw5AA.png)


Demo

![image](https://hackmd.io/_uploads/BJjFgO5AA.png)
