# 2024q1 Homework2 (quiz1+2)
contributed by < [`Randy-Chuang`](https://github.com/Randy-Chuang) >

## 2024q1 [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)

### 測驗 `1`

先參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) ，以下我把程式碼片段貼入解釋理解過程：

    i = 0; beg[0]=0; end[0]=elements;
    while (i>=0) {
        L=beg[i]; R=end[i]-1;
        if (L<R) {
            // 取區段 (partition) 第一個 element 做 pivot 來比較
            piv=arr[L]; if (i==MAX_LEVELS-1) return NO;
            while (L<R) {
                /// 從區段頭尾比較，根據 pivot 將區段分為小大兩邊
                while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; 
                while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; 
            }
            // 將區端分為小大兩個子區段
            arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; 
        } else {
            i--; // L < R 代表區段排序尚未結束，持續減少讓迴圈運作到結束
        }
    }

範例顯示外層迴圈第一輪結束後的結果：

外層迴圈跑完第一輪陣列 `beg[]` 和 `end[]` 內數值的變化：
| 陣列 \ index | 0 | 1 | 2 | ... |
| ------------ | ----------------- | ----------------- | --- | --- |
| `beg[]` | 0 $\rightarrow$ 0 | 0 $\rightarrow$ 4 | 0 | 0 |
| `end[]` | 8 $\rightarrow$ 3 | 0 $\rightarrow$ 8 | 0 | 0 |

配上範例能發現排序過程中 pivot 變數被用來將大小區段分開後，再改變 `beg[]` 和 `end[]` 來紀錄目前 Quick Sort 待排序的區段，以每次迴圈迭代而更改的陣列內容當作分枝來看，就能看出 Quick Sort 遞迴樹的變化，行為與 [Iterative DFS](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) 中佇列的控制相同。每跑一次迴圈，當次選用的 pivot 就會被擺到左區塊最後，因此左邊區段最後的元素剛好不用再排序 (圖中紅色標示) 。

digraph g {
    label="Quick Sort Recursion Tree";
    node [shape = record,height=.1];
    node0[label = "[0, 8)"];
    node1[label = <[0, <FONT COLOR="red">3</FONT>)>];
    node2[label = "[4, 8)"];
    node3[label = ""];
    node4[label = ""];
    node5[label = ""];
    node6[label = ""];

    "node0" -> "node1";
    "node0" -> "node2";
    "node1" -> "node3";
    "node1" -> "node4";
    "node2" -> "node5";
    "node2" -> "node6";
}

但是待排序陣列若是排列特殊會讓遞迴樹產生傾斜，極端情況會讓分配不均的小區段一直保留在 `beg[]` 和 `end[]` 陣列前端，造成長度不足以紀錄遞迴樹的分枝，因此作者改善程式碼確保迭代過程中優先處理較小的區段，遞迴樹的高度不會超過 $\lceil {Log_2(n)} \rceil$ 。

digraph g {
    label="Quick Sort Tilted Recursion Tree";
    node [shape = record,height=.1];
    node0[label = "[0, n)"];
    node1[label = "[0, 1)"];
    node2[label = "[2, n)"];
    node3[label = "..."];
    node4[label = "..."];
    node5[label = "[2, 3)"];
    node6[label = "[4, n)"];
    node7[label = "[6, n)"];
    node8[label = "[8, n)"];

    "node0" -> "node1";
    "node0" -> "node2";
    "node2" -> "node5";
    "node2" -> "node6";
    "node6" -> "node7";
    "node6" -> "node3";
    "node7" -> "node8";
    "node7" -> "node4";
}

            arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; 
+           if (end[i]-beg[i] > end[i-1]-beg[i-1]) {
+               swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap;
+               swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; 
+           }
        } else {
            i--; 
        }

#### 測驗程式碼

(*left)->next
(*left)->next
p->next
list_tail(&left)
list_tail(&right)

:::warning
延伸問題：

解釋上述程式碼的運作原理，提出改進方案並予以實作。
使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::

### 測驗 `2`

:::warning
延伸問題：

解釋上述程式碼的運作原理，提出改進方案並予以實作。
將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::

## 2024q1 [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)

### 測驗 `1`
### 測驗 `2`
### 測驗 `3`

## 表單測驗

## 參考資料

- Graphviz
- [Graphviz Doc](https://graphviz.org/documentation/) / [Layout Engines](https://graphviz.org/docs/layouts/) / [Gallery](https://www.graphviz.org/gallery/) / [Drawing graphs with dot](https://graphviz.org/pdf/dotguide.pdf)
- [Multiple graphs inside Graphviz DOT file](https://stackoverflow.com/questions/63869676/multiple-graphs-inside-graphviz-dot-file)