# 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` 找出串列的最後一個節點並回傳 * 舉例： > 初始資料 ```graphviz 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; ``` > 第一次迴圈 ```graphviz 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; ``` > 第二次迴圈處理右側串列 ```graphviz 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` ```graphviz 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; ``` > 第五次迴圈 ```graphviz 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` ```graphviz 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 長度保持平衡。 * 舉例： > 初始資料 ```graphviz 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; } ``` >找尋已排序子序列，並將每個子序列的首個節點串接在一起，若遇到子序列順序相反時則自動將其反轉 ```graphviz 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` 的長度總和，因此進行合併。 ```graphviz 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"] } } ``` >將最後兩個已排序好的子序列合併後即完成 ```graphviz 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)