# [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

int cmp(const void *x, const void *y){
    int a = *(const int *)x;
    int b = *(const int *)y;
    return (a > b) ? 1 : -1;
}

- swap

// 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

void (*sort)(void *base, size_t length, size_t type_size,
                    int (*compar)(const void*, const void*)) 
{

### Bubble Sort
- 第一run後 右邊一定是最大的

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

### Insertion Sort
- 挑選右邊第i個元素 => 插入左邊set 插入時左邊的set要自己在排序

### Selection Sort
- 挑選右邊第i大的元素 => 放左邊第i個位置

## 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)】

### Merge Sort
- Divide and Conquer
- 適合用在平行運算
- 需要大量的memory

- 有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
- 平均分佈時速度極快


### 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) : 從最左邊位數開始排序(最大位數

### 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代價高