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

## 測驗 `1`

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

在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 ```return```

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

接著宣告了 ```list_less``` 和 ```list_greater``` ，並對其做初始化

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

選擇第一個 entry 來做為 ```pivot``` ，並將其從原本的串列中刪除，我們可以看出 ```AAA``` 及 ```BBB``` 為 ```list_first_entry``` 所用到的兩個參數，而根據以下定義可知 ```AAA``` 為 struct 的型態， ```BBB``` 為成員的名稱。

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

因此 ```AAA``` = ```struct item``` ， ```BBB``` = ```list``` 。

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

這段可看出 ```CCC``` 功能為走訪所有的節點來做比較的動作並移動，且根據其傳入的參數可判斷 ```CCC``` = ```list_for_each_entry_safe``` ，這樣的選擇可以允許目前的節點被移走，對於比較動作完成後的移動有所幫助，也因此 ```DDD``` 跟 ```EEE``` 皆為用來移動的 ```list_move_tail``` ，將值小於 ```pivot``` 的節點移到 ```list_less``` ，反之則移動到 ```list_greater``` ，值得一提的是，考量到為了使得排序達到 stable 的目標，所以在這邊 ```DDD``` 跟 ```EEE``` 不能選擇用 ```list_move``` 。

list_sort(&list_less);
list_sort(&list_greater);

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

最後這邊，透過遞迴呼叫 ```list_sort``` 來將 ```list_less``` 和 ```list_greater``` 排序完成後，我們需要將```list_less``` 放在 ```pivot``` 之前，而```list_greater``` 放在 ```pivot``` 之後，所以 ```FFF``` 選擇使用 ```list_splice_tail``` ，這樣即完成排序。

---

## 測驗 `2`

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

在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 ```return```

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]);

宣告 stack ，並透過 ```INIT_LIST_HEAD``` 將其初始化，一開始先將 ```head``` 的節點全都移進 stack

struct list_head partition;
INIT_LIST_HEAD(&partition);

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

將 stack 中最頂端的 ```pop``` 出來放入 ```partition``` 中

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

如果 ```partition``` 非空且不只一個節點則進行以下操作

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
    list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);

這邊和測驗 1 類似，先宣告了 ```list_less``` 和 ```list_greater``` ，並對其做初始化，然後選擇 ```partition``` 中第一個 entry 來做為 ```pivot``` ，並將其從原本的串列中刪除。

struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
    list_del(&itm->list);
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_move(&itm->list, &list_less);
    else
        list_move(&itm->list, &list_greater);
}

這段可看出 ```GGGG``` 功能為走訪所有的節點，且根據其傳入的參數可判斷 ```GGGG``` = ```list_for_each_entry_safe``` ，而這樣的選擇可以允許目前的節點被移走，對於比較判斷完成後的移動有所幫助，將值小於 ```pivot``` 的節點移到 ```list_less``` ，反之則移動到 ```list_greater``` 。

HHHH (&pivot->list, &list_less);

我們會希望將```list_less``` 放在 ```pivot``` 之前，因此這邊 ```HHHH``` 選擇 ```list_move_tail``` ，將 ```pivot``` 移動到 ```list_less``` 的尾端。

if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);

這段則是針對非空的 ```list_greater``` 跟 ```list_less``` 做操作，由於尚未排序完成，我們是將其 push 進 stack 中，且為先推入大的 ```list_greater``` ，再推入小的 ```list_less``` 。
因此 ```IIII``` = ```JJJJ``` = ```&stack[++top]``` 。

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(KKKK);
        list_add_tail(&tmp->list, head);
    }
}

如果 ```partition``` 只有一個節點則先將其 ```push``` 到 stack中。
然後如果 top 大於等於 0 且 ```stack[top]``` 只有單個節點，將該節點做移除的動作並 ```INIT_LIST_HEAD``` 然後再從 stack 中 pop 掉，因此 ```KKKK``` = ```&stack[top--]``` 。
而被移除的節點則加入 ```head``` 的尾端。

由以上觀察可發現，越小的節點越會到 stack 的頂端，也因此被移除的節點會是尚未被排序的節點中最小的，而透過將被移除的節點加入 ```head``` 尾端的作法，等同於將節點由小到大加入尾端，因此全部加入完畢時也就是排序完成。

---

## 測驗 `3`