資料結構中「搜尋與排序」的概念、Code以及Demo

筆者的話

筆者的話：
紀錄一下「搜尋與排序」，這些觀念十分重要，需要記清楚，不論在考試或者未來工作，一定可以幫上讀者的忙，一方面也是筆者需要紀錄自己看。

版本號：1.0.0
說明：Search完成，Sort僅完成初等排序，待日後更新。

另徵求志願共筆者一同修改筆記，請直接留言，謝謝。

一、Search and sorting

(一)、Search

1. linear search

介紹：
Def:由左而右一一比較，直到找到或找不到為止。

資料搜尋不需事先經過排序
資料保存可以在random access(array)或者sequential access(link list)上實施
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

介紹：
Def:

資料必須經過排序(e.g 小到大)
保存在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;
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Recursive time function:T(n)=T(n/2)+1, T(1)=1 ∴O(logn)

Time complexity分析：

	Linear Search	Binary Search
Best	O(n)	O(logn)
Avg	O(n)	O(logn)
Worst	O(n)	O(logn)

(二)、Sort

初等排序

基本名詞解釋：

Sort可分：

Internal sorting
– 資料量小，可以全部置於記憶體中，並完成排序工作。
External sorting
– 資料量過大，無法一次全部置於記憶體，Need外部儲存體幫忙進行資料保存，再進行排序，外部儲存體如磁碟。

以及Stable和unstable：

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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即可。

Demo：Give num{5,3,4,2,1}
(底線表已排序)
–>Pass1:3, 5, 4, 2, 1
–>Pass2:3, 4, 5, 2, 1
–>Pass3:2, 3, 4, 5, 1
–>Pass4:1, 2, 3, 4, 5

– 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);
        
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

補充說明：
比較次數=(n-1)+(n-2)+…+1
=比較n(n-1)/2次
∴O(n^2)

2. Selection Sort

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

Demo：Give num{4,5,3,2,1}

–>Pass1:1,5,3,2,4
–>Pass2:1,2,3,5,4
–>Pass3:1,2,3,5,4
–>Pass4:1,2,3,4,5

– 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

分為兩個版本，分述如下：
[版本一]
觀念：

每一回合，左至右，兩兩紀錄相互比較，若前者>後者則交換前後；
若某一回合無任何交換，則可以Exit(後面回合不用作)；
最多作(n-1)回合；
效果：每一回合當時子清單中最大值移動到最大位置。

– 是否為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)

Demo：Give num{3,5,4,2,1}

–>Pass1:（3,5,4,2,1）–>3,4,2,1,5
–>Pass2:（3,4,2,1,5） –>3,2,1,4,5
–>Pass3:（3,2,1,4,5）–>2,1,3,4,5
–>Pass4:（2,1,3,4,5）–>1,2,3,4,5

result:
pass1: 3,4,2,1,5
Pass2: 3,2,1,4,5
Pass3: 2,1,3,4,5
Pass4: 1,2,3,4,5

[版本二]
觀念：

由左至右相互比較；
效果：每一回合完，最小值降到「最低」位置。

Demo：Give num{3,5,4,2,1}

–>Pass1:（3,5,4,2,1）–>1,3,5,4,2
–>Pass2:（1,3,5,4,2）–>1,2,3,5,4
–>Pass3:（1,2,3,5,4）–>1,2,3,5,4
–>Pass4:（1,2,3,5,4）–>1,2,34,5

result:
Pass1:1,3,5,4,2
Pass2:1,2,3,5,4
Pass3:1,2,3,5,4
Pass4:1,2,34,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

資料結構中「搜尋與排序」的概念、Code以及Demo

筆者的話

目錄

一、Search and sorting

(一)、Search

1. linear search

2.Binary search

(二)、Sort

初等排序

1. Insertion Sort

2. Selection Sort

3. Bubble Sort

4. Shell Sort

高等排序

1. Quick sort

Read more

LAB - TLS版本會不會影響到SMB連線

攻防LAB：存取Windows C槽之嘗試

VMware虛擬化環境進行簡易的iSCSI配置-NAS以QNAP為例

DFS 命名空間權限