---
tags: linux2023
---

# 2023q1 Homework1 (quiz1)
contributed by < `brianlin314` >

> [第一周測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)

### 測驗一

:::danger
不用抄題目，開發紀錄著重於你的想法和過程中遭遇到的問題，紀錄和討論才是主體，程式碼僅作搭配說明的用途。
:notes: jserv
> 學生收到
:+1:
:::

遞迴版 `quick sort` ，使用 `Divide and Conquer` 的概念。

`quick sort` 實做流程：
1. 在資料列中找出一個基準值 `pivot`
2. 將小於 `pivot` 的資料放在左邊，大於 `pivot` 的資料放在右邊
3. 左右兩邊資料分別重複1~2步驟，直到剩下1筆資料
4. 合併

if (list_empty(head) || list_is_singular(head))
        return;

首先，會先判斷 `list` 是否有節點存在，抑或是只存在一個節點。

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

`list_less`, `list_greater` 分別代表兩個不同 `list` 的 `head`，前者放入比 `Pivot` 小的節點，後者，反之。

struct item *pivot = list_first_entry(head, item, list);

`pivot` 設為該 `list` 的第一個節點。
所以使用 `list_first_entry` 來取得 `list` 的第一個節點的 `entry`。
:::warning
不用提及行號，可斟酌列舉相關程式碼來解說。避免「舉燭」，你應該思考：要是我來實作這樣的程式碼，我會怎麼做。
:notes: jserv
:::

struct item *itm = NULL, *is = NULL;
    list_for_each_entry_safe (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move_tail (&itm->list, &list_less);
        else
            list_move_tail (&itm->list, &list_greater);
    }

使用 `list_for_each_entry_safe` 來走訪整個 `list`，接著使用比較函式 `cmpint` 來判斷節點數值跟 `pivot` 的大小
- 若節點的值小於 `pivot`，用 `list_move_tail` 將該節點從原 list 移動到 `list_less` 的尾端。
- 反之若大於等於 `pivot`，用 `list_move_tail` 將改節點移動到 `list_greater` 的尾端。

list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);

接著持續不斷對 `&list_less` 與 `&list_greater` 進行遞迴，直到無法切割為止。

最後，將 `&list_less` 先串接到 `head`，再將 `&list_greater` 接到該 `list` 的尾端。

#### 可改進之處
因為上述程式碼每次皆選取 `list` 的第一個節點作為 `pivot`，這會遇到一個問題，就是當該 `list` 已經是由大到小或是由小到大排序時，會導致每次選到的 `pivot` 都剛好是最大值或最小值，而沒辦法均分 `list_less` 和 `list_greater`，若遇到該極端狀況，上述程式碼的時間複雜度就是 $O(n^2)$。

因此可以透過更改選擇 `pivot` 的方法，去改進上述的程式碼，大概分為以下三種方法:
1. Middle-of-Three
(1) 令 $middle = \dfrac{left + right}{2}$
(2) 比較 list[left]、list[middle] 與 list[right] 這三筆資料，排出中間值，並將此中間值再與 list[left] 做交換
(3) 讓現在新的 list[left] 作為 pivot
2. Randomized pivot
亂數選取的方式，隨機挑 list 中的一個值作為 pivot，但 worst case 還是 $O(n^2)$
3. Median-of-Medians
詳細流程可參考 [Median of medians](https://en.wikipedia.org/wiki/Median_of_medians)
---

### 測驗二

struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
    INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);

struct list_head partition;
INIT_LIST_HEAD(&partition);

一開始即宣告一個 `stack` ，代表之後的實作皆與之有關，並且依照其定義的大小，使用 `INIT_LIST_HEAD` 初始化，接著將整條未排列的 `list` 放到 `stack` 裡。

再宣告一個 `partition` ，作用是每次迴圈中都會存放 `stack` top 中的 `list`。

需特別注意 `++top` 與 `top++` 的差別，因為自己習慣用 `i++` 了，所以常常忘記區分這兩種 case。

while (top >= 0) {
    INIT_LIST_HEAD(&partition);
    list_splice_init(&stack[top--], &partition);
    ...
    }

每次進入迴圈時，都會將 `stack` top 中的 `list` 放到 `partition` 中，並進行以下 if-else 判斷。

if (!list_empty(&partition) && !list_is_singular(&partition))

若 `partition` 有大於等於兩個節點，則通過該條件式，並且與 `測驗一` 的實作方法相同，`pivot` 選為該 `list` 的第一個節點，使用 `list_for_each_entry_safe` 走訪整個 `list` 並將比 `pivot` 小的節點放到 `list_less` 中，反之，則放到 `list_greater` 。

list_move_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, &stack[++top]);

先將 `pivot` 放到 `list_less` 的尾端，因為 `list_less` 裡面的節點值皆比 `pivot` 小。

再來要將 `list_less` 和 `list_greater` 再次放到 `stack` 中，由於是要加入到 `stack` 中，所以要先放入 `list_greater`，再放入 `list_less`，這樣才符合 FILO，等等拿出來的順序才是由小到大。

else {
    top++;
    list_splice_tail(&partition, &stack[top]);
    while (top >= 0 && list_is_singular(&stack[top])) {
        struct item *tmp =
            list_first_entry(&stack[top], struct item, list);
        list_del(&tmp->list);
        INIT_LIST_HEAD(&stack[top--]);
        list_add_tail(&tmp->list, head);
    }
}

若 `partition` 只有一個節點的話，會將 `partition` 放回 `stack` 中。

`while` 迴圈會不斷從 `stack` 中 pop `list` 出來，並且插入到 `head` 的尾端，直到該 `list` 不是只有一個節點存在或該 `stack` 為空為止。

---
### 測驗三