2023q1 Homework1 (quiz1)

contributed by < brianlin314 >

第一周測驗題

測驗一

遞迴版 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。

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

測驗二

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 為空為止。

測驗三