owned this note
owned this note
Published
Linked with GitHub
# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) <br> Sorting Algo
## Search, insert and delete in a sorted array
Search: O(Log n) [Using Binary Search]
Insert: O(n) [In worst case all elements may have to be moved]
Delete: O(n) [In worst case all elements may have to be moved]
- Search conclusion
- Sequential search
小資料量 (幾十,幾百)
- Binary search
大資料量, 且已經排序好
- Hash table
大資料量, 雜亂無排序
- Database
結構化資料,資料量最好不要超過百萬
- Search engine
極大資料量 (幾千萬, 幾億)
## Basic Sorting Time Complexity
|Sort Algo |Bubble| Shell | Insertion|Selection|
|:-------- |:- |:-------- |:----|:---------|
|Best | O(n)小到大| | O(n)小到大 T(n)=T(n-1)+1| |
|AVG | T(n)=T(n-1) + n/2| |T(n)=T(n-1) + n/2| |
|Worst | O(n^2)大到小| | O(n^2)小到大| |
|status| stable| unstable | stable| unstable|
|無recursive負擔 適用於data量<br>不大的時候| ||Binary Insertion <br>Linear Insertion | 適用於欄位多 但key值較少 <br> 因為每回合最多swap 一次|
## Base Sorting
- 小到大 : )
- 大到小 : (
- 穩定排序法(stable sorting),如果鍵值相同之資料,在排序後相對位置與排序前相同時,稱穩定排序。
【例如】
排序前:3,5,19,1,3*,10
排序後:1,3,3*,5,10,19 (因為兩個3, 3*的相對位置在排序前與後皆相同。)
### Function Prototype
- compare
```C
int cmp(const void *x, const void *y){
int a = *(const int *)x;
int b = *(const int *)y;
return (a > b) ? 1 : -1;
}
```
- swap
```C
// exclusive or ?
void swap(void *a, void *b, size_t type_size) {
void *tmp = malloc(type_size);
memcpy(tmp, a, type_size);
memcpy(a, b, type_size);
memcpy(b, tmp, type_size);
free(tmp);
}
```
- sort function pointer
```C
void (*sort)(void *base, size_t length, size_t type_size,
int (*compar)(const void*, const void*))
{
```
### Bubble Sort
- 第一run後 右邊一定是最大的
```C
void bubbleSort(void *base, size_t length, size_t type_size,
int (*compar)(const void*, const void*))
{
int i, j;
for (i = 0; i < length - 1; ++i)
{
bool sorting_finish = true;
for (j = 1 ; j < length-i ; ++j)
{
char *data_i = (char*)base + type_size * (j -1 );
char *data_j = (char*)base + type_size * j;
if (compar(data_i, data_j) > 0)
{
swap(data_i, data_j, type_size);
sorting_finish = false;
}
}
if (sorting_finish)
break;
}
}
```
### Shell Sort
- `swap((i + span), i)`
- Reference :
- http://notepad.yehyeh.net/Content/Algorithm/Sort/Shell/Shell.php
![](https://i.imgur.com/5x9uJeS.png)
![](https://i.imgur.com/qx2kkH1.png)
```C
```
### Insertion Sort
- 挑選右邊第i個元素 => 插入左邊set 插入時左邊的set要自己在排序
```C
```
### Selection Sort
- 挑選右邊第i大的元素 => 放左邊第i個位置
```C
```
## Advanced Sorting
- time complexity is `o(nlogn)`
### Heap Sort
Average: O (NlgN)
Selection 不適合:
- 1. 正常情況下比基本上比 Quick sort 要慢
- 2. 需要保證 stable sorting 的狀況
Selection 適合: Priority queue
什麼是 Priority queue?
- Heap 建立好之後,取出一個 max/min 只需要 O(lgN) 的時間
- Insert 一次也只需要 O(lgN) 的時間
- 在常變動的環境下,隨時想要取得【目前最大 K 個 value(s)】
```C
```
### Merge Sort
- Divide and Conquer
- 適合用在平行運算
- 需要大量的memory
![](https://i.imgur.com/efNOKUb.png)
- 有recursive or iteration版本
### Quick Sort
- 先選出pivot,比pivot小的放左邊,比pivot大的放右邊。
- 適合用在**只需要最大/最小的k個values**
- Dived and Conquer
- 先選出衛兵
- 左半部 比衛兵大的挑出來
- 右半部 比衛兵小的挑出來
- 兩邊`swap()`後 立牌
## Linear Time Sorting
### Bucket Sort
也成為 Bin sort。將所有 Data 分到有限的桶子內,然後再分別排序
例如快遞先將貨物分成國內國外,再把國內這個桶子裡面的貨物分到各縣市的桶子,依序分下去
- 不適合
- 桶子內的元素要平均(學生分數為 Normal Distribution)不適合
- M型分佈
- 需要額外空間存桶子
- 適合
- 分類 (例如要把 e-mail 按照 domain 分开)… 這好像不算 sorting
- 平均分佈時速度極快
![](https://i.imgur.com/iNGclxn.png)
### Counting Sort
- N個元素 其範圍是(0~K-1)
- 創建array(K) 用其index存每個元素出現次數
- 不用對桶子內元素sorting的bucket sort
### Radix Sort
- 使用條件
- K不能太大(長)
- 每個位數的變化不可大(中文名子不合適)
- K: 元素最大位數 , N: 元素個數
- Time Compexity : O(K*N)
- Space Complexity : O(K+N)<--- 我覺得怪怪der 應該是每個位數的範圍ex: decimal : 0~9 => 10
- 把元素放到對應的bucket
- LSD(Least Significant Digit) : 從最右邊位數開始排序(個位數)
- MSD(Most Significant Digit) : 從最左邊位數開始排序(最大位數
![](https://i.imgur.com/Z4Udjcx.png)
### Hash Function
### Overflow Manipulation
## Comparison Sorting Time Complexity
| Comparison |Quick | merge | heap | insertion| selection |
|:-------- |:---- |:----- |:-----|:---------|:----------|
|Best Case | nlogn| nlogn| nlogn| N | N^2 |
|Average Case| nlogn| nlogn| nlogn| N^2 | N^2 |
|Worst Case | N^2 | nlogn| nlogn| N^2 | M^2 |
## Conclusion
50 email address
5000萬 email address
100萬個成績
3000地址
500000個身份證字號
swap代價高