演算法
===
###### tags: `大學必修-筆記`

CH1 Union-Find 演算法
===

## 演算法的方法
* Find -> 看 p 這個點在哪裡
* Connected -> 看 p q 兩點是否相連
* Union -> 把 p q 兩點連在一起

## quick-find

> id[] 裡面存的是，如果數字一樣 -> 同 union
* Find -> 看 p 的 id 是多少
* Connected -> 看 p q 兩點的 id 是否一樣
* Union -> 把 id[p] 的值放到 id[q] 裡

public class QuickFindUF {

    private int[] id; 

    public QuickFindUF(int N) {            // 初使化矩陣

        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }

    public int find(int p) {               // find 方法
        return id[p]; 
    }
    
    public void union(int p, int q) {      // union 方法

        int pid = id[p];
        int qid = id[q];

        for (int i = 0; i < id.length; i++)  // 把每個 q 變成 p
            if (id[i] == pid) id[i] = qid; 
}

| algorithm | initialize | union | find | connected |
|------------|------------|-------|------|-----------|
| quick-find | N | N | 1 | 1 |

## quick-union

> 用 tree 的想法實作
> id[] 裡面存的是，這個點的 root(最上面的點) 是誰
* Find -> p 點的 root 是誰
* Connected -> 看 p q 的 root 是否一樣
* Union -> 把 p 的 root 指向 q 的 root

public class QuickUnionUF {

    private int[] id; 

    public QuickUnionUF(int N) {            // 初使化矩陣
        
        id = new int[N];
        for (int i = 0; i < N; i++) 
            id[i] = i;
    }
    
    public int find(int i) {                // 要一直朝root往上找
                                            // 樹有可能好幾層
        while (i != id[i]) 
            i = id[i];
        return i;
    } 

    public void union(int p, int q) {       // 把 p 的 root
                                            // 給 q 的 root
        int proot = find(p);                // 代表兩個樹接在一起
        int qroot = find(q);
        id[proot] = qroot;
    }
}

| algorithm | initialize | union | find | connected |
|-------------|------------|-------|------|-----------|
| quick-find | N | N | 1 | 1 |
| quick-union(worst case) | N | N | N | N |
* 最好的情況
* 
* 最壞的情況
* 

## weighted QU
* 在 union 的過程中有可以小樹接在大樹上
* 會把 tree height 變高
* 改量方法為永遠是 ==大樹接小樹==

| algorithm | initialize | union | find | connected |
|-------------|------------|-------|------|-----------|
| quick-find | N | N | 1 | 1 |
| quick-union(worst case) | N | N | N | N |
| weighted QU (worst case)|N|lg N|lg N|lg N

* 為什麼是 lg N 呢
* 因為每次 union 後的 size 都會至少是小數的 2 倍大
* 以 1, 2, 4, 8, 16, ...成長
* 所以 union 的次數一定會小於 lg N

CH2 演算法分析
===
* Big-$Ο$ 代表演算法時間函式的上限(Upper bound)
* 在最壞的狀況下，演算法的執行時間不會超過Big-Ο

* $Ω$ 代表演算法時間函式的下限(Lower bound)
* 在最好的狀況下，演算法的執行時間不會比Omega快

CH3 未知矩陣大小問題
===

## Link-list
* 在==最糟的情況==下，執行時間為 constant
* 需要花很多空間來存 link
## Resizing Arrays
* ==每次執行==，執行時間為 constant
* 不需要花太多空間
---
* 一次增加矩陣一格

* 沒效率
* $N + (2 + 4 + 6 + 8... + 2(N – 1)) \rightarrow N^2$
* 一次增加原本矩陣的一半

* 比較有效率
* $N + (2 + 4 + 8 + ... + N) \rightarrow 3N$
* 一次減少四分之一

* 會比一次減少二分之一還要有效率

CH4 sort
===

## Selection sort 選擇排序法

* 流程

1. 從 *未排序* 的數列中找到==最小==的元素
2. 將此元素取出並加入到 *已排序* 數列最後
3. 重複以上動作直到未排序數列全部處理完成


public static void sort(Comparable[] a) {

    int N = a.length;
    for (int i = 0; i < N; i++) {
        
        int min = i;
        
        for (int j = i+1; j < N; j++)
            if (less(a[j], a[min]))
                 min = j;
        
        exch(a, i, min);
    }
}

* 所花時間
* compares：$(N–1) + (N–2) + ... + 1 + 0 \rightarrow \frac{1}{2}N^2$
* 隨著 i 漸漸往右，要比較的數字越來越少
* exchange：$N$
* 總交換數只要 N 個就可以了

## Insertion sort 插入排序法
* 流程

1. 從 *未排序* 數列==取出一元素==
2. 由後往前和 *已排序* 數列比較
3. 遇到 *不大於自己* 的元素並插入此元素之後
4. 若都沒有則插入在最前面。
5. 重複以上動作直到未排序數列全部處理完成。


public static void sort(Comparable[] a) {
    
    int N = a.length;
    
    for (int i = 0; i < N; i++)
        for (int j = i; j > 0; j--)
            if (less(a[j], a[j-1]))
                exch(a, j, j-1);
            else break;
}

* 所花時間
* 最好情況
* ==如果數列已經是排好的==
* ex："1, 2, 3, 4, 5, 6"
* compares：$N - 1$
* exchange：$0$
* 最壞情況
* ==如果數列剛好是反過來排好的==
* ex："6, 5, 4, 3, 2, 1"
* compares：$\frac{1}{2}N^2$
* exchange：$\frac{1}{2}N^2$
* 平均情況
* compares：$\frac{1}{4}N^2$
* exchange：$\frac{1}{4}N^2$

## Shellsort
* 針對 Insertion sort 改良以下兩個方法

* Insertion Sort 在對幾乎已經排好序的資料操作時，效率高
* 但 Insertion Sort 一般來說是低效率的，因為每次只能將資料移動一位
---
* 流程
1. 將整個陣列依照預先指定的間隔長度 d
2. 交錯分割成數個小陣列
3. 以==插入排序==的方式將這些小陣列個別排序
4. 逐漸縮小間隔長度 d ，直到 d 等於 1
5. 一般用 3x + 1 的方法


CH5 Merge sort 合併排序法
===
## Top-Down Merge sort
* 使用 divide and conquer 分而治之的方法
* 使用遞迴的方法
---
* 流程

1. 將陣列分割直到只有一個元素 -> 遞迴
2. 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列
3. 重複2的動作直接全部合併完成

merge 方法

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

    for (int k = lo; k <= hi; k++)   // 先 copy 到 aux 矩陣去
        aux[k] = a[k];

    int i = lo, j = mid+1;
    
    for (int k = lo; k <= hi; k++) {
        if (i > mid)                    a[k] = aux[j++];
        else if (j > hi)                a[k] = aux[i++];
        else if (less(aux[j], aux[i]))  a[k] = aux[j++];
        else                            a[k] = aux[i++];
    }
}

sort 方法

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    
    if (hi <= lo) 
        return;
    
    int mid = lo + (hi - lo) / 2;
    
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);         // 這邊遞迴
}

* 所花時間
* compares：$N logN$
* proof：
* $D(N) \leq D(\left \lfloor N/2 \right \rfloor) + D(\left \lceil N/2 \right \rceil) + N$
`左半邊 + 右半邊 + merge`
* $D (N) = 2 D (N / 2) + N$
* 樹高為 lg N


* 特別注意
* 只要演算法看起來是下面這個形式
* 它一定會花 $N log N$


## Buttion-Up Merge sort
* 比 Top-Down Merge sort 慢了一點
* 時間複雜度 N lg N

* proof：

$D(N) = 2D(\frac{N}{2}) + N$

$\frac{D(N)}{N} = \frac{2D(\frac{N}{2})}{N} + 1$

$\frac{D(N)}{N} = \frac{D(\frac{N}{2})}{\frac{N}{2}} + 1$

$\frac{D(N)}{N} = \frac{D(\frac{N}{4})}{\frac{N}{4}} + 1 + 1$

$\frac{D(N)}{N} = \frac{D(\frac{N}{8})}{\frac{N}{8}} + 1 + 1 + 1$

$...$

$\frac{D(N)}{N} = \frac{D(\frac{N}{N})}{\frac{N}{N}} + 1 + 1 + ... + 1$

$\frac{D(N)}{N} = lgN$

sort 方法

public static void sort(Comparable[] a) {
    
    int N = a.length;
    
    Comparable[] aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

* 兩個 Merge sort 的比較


## Timsort
* 結合了 merge sort 和插入排序 insertion sort 而得出的排序算法
* 為了優化在排序時有時已經排好的問題
* 以一個區塊進行排序
---
* 流程
1. 找到各區塊 $\rightarrow$ 以一個排好的數列為一區塊
2. 以 merge sort 合併各個 區塊


## stability 穩定性

* 如果在一個待排序的序列中，存在2個==相等==的數
* 在排序後這2個數的==相對位置保持不變==
* 那麼該排序演算法是穩定的
* 否則是不穩定的

> ex：(A, A*, C, D, E)$\rightarrow$(20, 20, 10, 50, 30)
>
> stability $\rightarrow$ (C, ==A, A*==, E, D)
> unstability $\rightarrow$ (C, ==A*, A==, E, D)

* 另一種看法
* 看有沒有長距離搬移
* 有的話就有可能是 unstability

## Sleep sort

* 根據 thread 的 sleep
* 數字越小 $\rightarrow$ 睡得越早，越早起來

CH6 Quick sort 快速排序法
===
## quick sort
* 排序演算法的一種
* 使用Divide and Conquer的演算法來實作
* 可以使用 in-place 來實作，但不合成本
---
* 流程

1. 數列中選擇一元素作為基準點(pivot)
2. 小於此元素的移至基準的左邊，大於此元素的移至右邊，相等的任意放
3. 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。

* 所花時間
* 最好情況
* 當選中的 pivot 都是當下的中位數時
* compares：$N log N$
* 最壞情況
* 當數列已經是排好的了
* compares：$\frac{1}{2}N^2$
* proof：
* $(N - 1) + (N - 2) + ... + 2 + 1 \rightarrow \frac{1}{2}N^2$

* 平均情況
* $1.39N log N$
* proof：

表示本次 pivot 所需比較次數 $\left( n+1 \right)$
與每種分割結果所需比較次數的期望和

$C_{n} = (n + 1) + (\frac{C_0 + C_{n - 1}}{n}) + (\frac{C_1 + C_{n - 2}}{n}) + ... + (\frac{C_{n-1} + C_{0}}{n})$

通乘以 n 得

$nC_{n} = n(n + 1) + 2(C_0 + C_1 + C_2 + ... + C_{n-1})$ $\rightarrow$ 式1

把 n 換成 n - 1 得

$(n-1)C_{n-1} = (n - 1)(n - 1 + 1) + 2(C_0 + C_1 + C_2 + ... + C_{n-2})$ $\rightarrow$ 式2

把 式1 - 式2 得

$nC_n - (n-1)C_{n-1} = 2n + 2C_{n-1}$

移位後，同除以 $n(n+1)$ 得

$\frac{C_{n}}{n+1}$

$= \frac{C_{n-1}}{n} + \frac{2}{n+1}$

$= \frac{C_{n-2}}{n-1} + \frac{2}{n} + \frac{2}{n+1}$

$= \frac{2}{3}+\frac{2}{4}+\frac{2}{5}+...+\frac{2}{n+1}$

用積分化減得

$C_n = 2(n+1)(\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n+1})$

$C_n = 2(n+1)\int_{3}^{n+1}\frac{1}{x} dx$

$C_n = 2(n+1) ln N \cong 1.39 N lg N$

## 3 ways quick sort

* 用來解決 quick sort 遇到一樣的數字時，會再 compare 一次
* 原本 quick sort 只會分成兩等分：大於 pivot 或小於 pivot
* 3 ways 則分成三等分：大於 pivot、等於 pivot、小於 pivot
---
* 流程

1. (a[i] < v)：交換 a[lt] 和 a[i]、增加 lt 和 i
2. (a[i] > v)：交換 a[gt] 和 a[i]、減少 gt
3. (a[i] == v)：增加 i


## 總整理

| | inplace | stable | 最好情況 | 平均情況 | 最壞情況 | 優點 |
|-------------|----------|---------|----------------------|------------------|------------------|-------------------------------------------|
| selection | ✔ | | $\frac{1}{2}N^2$ | $\frac{1}{2}N^2$ | $\frac{1}{2}N^2$ | 只交換 N 次 |
| insertion | ✔ | ✔ | N | $\frac{1}{4}N^2$ | $\frac{1}{2}N^2$ | 如果 N 特別小的話 效率高，會接近 constant |
| shell | ✔ | | $N log N$ | ? | ? | |
| merge | | ✔ | $\frac{1}{2}N log N$ | $N log N$ | $N log N$ | 穩定保證 $N log N$ |
| timsort | | ✔ | N | $N log N$ | $N log N$ | 改良 mergesort 優化已經排序的數列 |
| quick | ✔ | | $N log N$ | $1.39 N log N$ | $\frac{1}{2}N^2$ | 最快的排序法 |
| 3-way quick | ✔ | | N | $N log N$ | $N log N$ | 優化 quicksort 遇到相同數字的問題 |
| heap | ✔ | | N | $2N log N$ | $2N log N$ | 保證 $N log N$ |

Heap Sort
===