# 2024q1 Homework2 (quiz1+2)
contributed by < `chishuo9810` >

## 第一週測驗題
### [測驗 1 ](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1)

#### 程式運作原理
* 目標 : 以鏈結串列實作非遞廻 `quick sort`
* `quick sort` 說明：
1. 選定串列的其中一節點為 `pivot` (此次測驗程式碼令串列最開始為 `pivot` )。
2. 將比 `pivot` 大的節點放置於其右側，比 `pivot` 小的節點放置於其左側。
3. 對 `pivot` 左、右兩側的節點們重複進行前兩點操作，最後即可得到由小到大的排序。
* 重要函式說明 :
* `list_length` 回傳串列長度
* `list_add` 將節點插入串列之首
* `list_tail` 找出串列的最後一個節點並回傳
* 舉例：
> 初始資料

digraph graphname{

        node[shape=box]
        b2 [label = "2"];
        b4 [label = "4"];
        b3 [label = "3"];
        b5 [label = "5"];
        b1 [label = "1"];
        
        node[shape=plaintext]
        pivot;
        L [fontcolor="blue"]
        R [fontcolor="blue"]
        {
            rank="same";
            b2->b4->b3->b5->b1->NULL;
        }
        pivot->b2;
        L->b2;
        R->b1;
	}

begin[0] = 2; end[0] = 1;

> 第一次迴圈

digraph graphname{

        node[shape=box]
        b2 [label = "2"];
        b4 [label = "4"];
        b3 [label = "3"];
        b5 [label = "5"];
        b1 [label = "1"];
        
        node[shape=plaintext]
        pivot;
        L [fontcolor="blue"]
        R [fontcolor="blue"]
        n1 [label = "NULL"]
        n2 [label = "NULL"]
        n3 [label = "NULL"]
        rankdir=LR;
        L->b1->n2;
        R->b5->b3->b4->n3;
        pivot->b2->n1;
	}

begin[0] = 1; end[0] = 1;
begin[1] = 2; end[1] = 2;
begin[2] = 5; end[2] = 4;

> 第二次迴圈處理右側串列

digraph graphname{
        node[shape=box]
        b4 [label = "4"];
        b3 [label = "3"];
        b5 [label = "5"];
        
        node[shape=plaintext]
        pivot;
        L [fontcolor="blue"]
        R [fontcolor="blue"]
        n1 [label = "NULL"]
        n2 [label = "NULL"]
        n3 [label = "NULL"]
        rankdir=LR;
        R->n3;
        L->b4->b3->n2
        pivot->b5->n1;
	}

begin[0] = 1; end[0] = 1;
begin[1] = 2; end[1] = 2;
begin[2] = 4; end[2] = 3;
begin[3] = 5; end[3] = 5;
begin[4] = NULL; end[4] = NULL;

> 第三次迴圈

右側串列沒有節點，直接進入下一次迴圈
>第四次迴圈

將節點 5 放入節點 `result`

digraph graphname{
        node[shape=box]
        b5 [label = "5"];        
        node[shape=plaintext]
        result [fontcolor="red"]
        rankdir=LR;
        result->b5->NULL
	}

begin[0] = 1; end[0] = 1;
begin[1] = 2; end[1] = 2;
begin[2] = 4; end[2] = 3;

> 第五次迴圈

digraph graphname{
        node[shape=box]
        b4 [label = "4"];
        b3 [label = "3"];
        
        node[shape=plaintext]
        pivot;
        L [fontcolor="blue"]
        R [fontcolor="blue"]
        n1 [label = "NULL"]
        n2 [label = "NULL"]
        n3 [label = "NULL"]
        rankdir=LR;
        R->n3;
        L->b3->n1
        pivot->b4->n2;
	}

begin[0] = 1; end[0] = 1;
begin[1] = 2; end[1] = 2;
begin[2] = 3; end[2] = 3;
begin[3] = 4; end[3] = 4;
begin[4] = NULL; end[4] = NULL;

> 第六次迴圈

右側串列沒有節點，直接進入下一次迴圈
> 第七、八、九、十次迴圈

分別將節點 4、3、2、1 放入節點 `result`

digraph graphname{
        node[shape=box]
        b5 [label = "5"]; 
        b4 [label = "4"];        
        b3 [label = "3"];        
        b2 [label = "2"];        
        b1 [label = "1"];        
        node[shape=plaintext]
        result [fontcolor="red"]
        rankdir=LR;
        result->b1->b2->b3->b4->b5->NULL
	}

### [測驗 2 ](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)
#### 程式運作原理
* 目標 : 改進合併排序法
* `Timsort` 說明：
在現實世界中，許多資料其實已經部份排序了，`Timsort` 減少了原本合併排序的合併次數
1. 識別出資料中已排序的子序列 `run`
2. 不斷合併這些子序列來達成全部資料的排序
* 重要函式說明 :
* `find_run`
從參數傳的節點開始，往後找出最長已排序子串列並回傳。
* `merge_collapse` 檢查是否滿足 ：

1. `tp->prev->prev` 的長度要大於 `tp->prev` 和 `tp` 的長度總和。
2. `tp->prev` 的長度要大於 `tp` 的長度。
若不符合條件則進行合併已確保堆疊上的 run 長度保持平衡。
* 舉例：
> 初始資料

digraph graphname{
        node[shape=box]
        b1 [label = "1"];
        b2 [label = "2"];
        b3 [label = "3"];
        b4 [label = "4"];
        b5 [label = "3"];
        b6 [label = "2"];
        b7 [label = "4"];
        b8 [label = "7"];
        b9 [label = "8"];
        rankdir=LR;
        b1->b2->b3->b4->b5->b6->b7->b8->b9->NULL;
	}

>找尋已排序子序列，並將每個子序列的首個節點串接在一起，若遇到子序列順序相反時則自動將其反轉

digraph graphname{
        node[shape=box]
        b1 [label = "1"];
        b2 [label = "2"];
        b3 [label = "3"];
        b4 [label = "4"];
        b5 [label = "3"];
        b6 [label = "2"];
        b7 [label = "4"];
        b8 [label = "7"];
        b9 [label = "8"];
        node[shape=plaintext]
        n1 [label = "NULL"]
        n2 [label = "NULL"]
        n3 [label = "NULL"]
        rankdir=LR;

        b7->b8->b9->n3;
        b6->b5->n2;
        b1->b2->b3->b4->n1;
        {
            rank="same"
            tp[fontcolor="red"]
            tp->b7
            b7->b6 [label="prev"]
            b6->b1 [label="prev"]
        }
	}

>`tp->prev->prev` 的長度並未大於 `tp->prev` 和 `tp` 的長度總和，因此進行合併。

digraph graphname{
        node[shape=box]
        b1 [label = "1"];
        b2 [label = "2"];
        b3 [label = "3"];
        b4 [label = "4"];
        b5 [label = "3"];
        b6 [label = "2"];
        b7 [label = "4"];
        b8 [label = "7"];
        b9 [label = "8"];
        node[shape=plaintext]
        n1 [label = "NULL"]
        n3 [label = "NULL"]
        rankdir=LR;

        b6->b5->b7->b8->b9->n3;
        b1->b2->b3->b4->n1;
        {
            rank="same"
            tp[fontcolor="red"]
            tp->b6
            b6->b1 [label="prev"]
        }
	}

>將最後兩個已排序好的子序列合併後即完成

digraph graphname{
        node[shape=box]
        b1 [label = "1"];
        b2 [label = "2"];
        b3 [label = "3"];
        b4 [label = "4"];
        b5 [label = "3"];
        b6 [label = "2"];
        b7 [label = "4"];
        b8 [label = "7"];
        b9 [label = "8"];
        node[shape=plaintext]
        n3 [label = "NULL"]
        rankdir=LR;

        b1->b2->b6->b3->b5->b4->b7->b8->b9->n3;
	}

>相較合併排序法原本需要進行 8 次的合併，這筆資料由於有部份排序過，透過 `Timsort` 僅僅進行了 2 次合併
## 第二週測驗題
### [測驗 1 ](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-1)
#### 程式運作原理
* 目標 : 透過遞迴呼叫的方式，利用深度搜尋法重建二元樹。
* 說明：
1. 由前序得知根節點。
2. 在中序中尋得根節點，左側即為左子樹，右側即為右子數。
3. 左子樹和右子樹接著進行 1、2。
4. 反覆操作 1～3 即可重建二元樹
* 重要函式說明 :
* `dfs`回傳已建成之子樹的根節點
* `find`回傳根節點在中序的位置
### [測驗 2 ](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-2)
### [測驗 3 ](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)