# 2023q1 Homework1 (quiz1)
contributed by < [zeddyuu](https://github.com/zeddyuu) >

## 測驗 1

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

用以對節點內含值比較的函式，這裡比較特別的是參數的 `void *` 型態 ，在 [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer#void--%E4%B9%8B%E8%AC%8E) 內有提到，是為了要讓程式設計者透過顯式轉型避免危險的指標操作。

    if (list_empty(head) || list_is_singular(head))
        return;
    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

先確認 list 是否為空或是只有一個元素，接著初始化兩個 head 負責連接比 pivot 小或大的 node。

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

選出第一個元素做為 pivot ，`list_first_entry` 用來取得第一個元素，參數要求為 list head、嵌入的結構體型態以及 list head 在此結構體內的變數名稱，故答案為
`AAA` : item
`BBB` : list

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

這裡的功能為<s>歷遍</s> 逐一走訪每個節點並且和 pivot 比較值的大小，若比 pivot 小則放入 list_less，比 pivot 大或等於則放入 list_greater，排序要求要 stable，所以值如果相同要照順序放入，也就是從尾巴放入 list，故答案為
`CCC` : `list_for_each_entry_safe`
`DDD` : `list_move_tail`
`EEE` : `list_move_tail`

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

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

:::danger
留意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，不用抄題目。你應該聚焦在理解題目背後的想法。
:notes: jserv
> 好的，已改正，謝謝老師。
:::

遞迴處理兩邊比 pivot 小的 list、比 pivot 大的 list，遞迴結束後，先將 pivot 接到原來的 head ，然後將排序好比 pivot 小的 list 用 `list_splice` 接在 pivot 前，最後將比 pivot 大的 list 用 `list_splice_tail` 接到 pivot 後，完成排序，故答案
`FFF` : `list_splice_tail`
## 測驗 2

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

先確定 list 是否為空或只有一個節點，是的話就不用進行排序。

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

宣告一個 list head 這個型態的 stack，用迴圈將每個陣列元素用 `INIT_LIST_HEAD` 初始化，接著用 `list_splice_init` 將 head 所有元素移到陣列元素開頭，等同將待排序的 list 放入 stack 中。

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

宣告一個 partition 變數，用來處理等等要排序的 list。

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

當 stack 內還有待排序的 list 時才執行這個 while 迴圈，迴圈一開始會將放在 stack 最上面的 list 用 `list_splice_init` 接在 partition 做處理。

if (!list_empty(&partition) && !list_is_singular(&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);

這段 if 敘述是處理 list 內有超過兩個節點的情況，跟遞迴版本一樣會用 less 跟 greater 分別去串比 pivot 小以及大的節點，pivot 也是選擇用 list 的第一個元素。

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

之後就是走訪 list 中每一個節點，看是不是比 pivot 來得小或是大，再分別移到 less 或是 greater，為了要保持 stable 的排序，跟 pivot 相同的話要串在 list_greater 中，這樣後續再接回去 pivot 後方就能確保排序是 stable 的。
所以可以知道這邊的答案就是要有走訪的功能，同時敘述中會有 delete(move) 的情況，所以要用 safe 的版本。
`GGGG` : `list_for_each_entry_safe`

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);

走訪完成後就將 pivot 移到 less 的後方，產生出兩個未排序的 list，也就是 less 以及 greater，我們的目標就是跟遞迴處理一樣，要另外排序這兩個 list，因此再把這兩個 list 放入 stack 中成為待排序的 list，要記得先累加 top，空出新的位置之後再去存取。
`HHHH` : `list_move_tail`
`IIII` : `&stack[++top]`
`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);
            }

再來這邊是待排序的 list 只有一個節點的情況，會直接把 list 再塞回去 stack 裡面，用一個 while 迴圈將 stack 頂端只有一個節點的 list 都拿出來，並且把他們唯一一個元素放到 head 的尾巴，在上面放入 stack 是依照由大到小的順序，先放入 greater 再放入 less，所以取出來根據 stack LIFO 的性質，每次 partition 一定是先處理相較起來較小的 list，最後頂端就只會剩下較小的一個元素，再跟 head 接起來。
因為這邊使用 `list_del` 刪除掉 list 了，但卻沒有對 stack 做相對應的操作(pop 所以要 top = top - 1)。
故答案
`KKKK` : `&stack[top--]`

### 延伸問題
#### 指出設計和實作的缺失
程式碼在一開始就定義了

#define MAX_DEPTH 512

所以 stack 的最大 size 也只有512，如果要排序的 list 太長會發生 [buffer overflow](https://zh.wikipedia.org/zh-tw/%E7%BC%93%E5%86%B2%E5%8C%BA%E6%BA%A2%E5%87%BA)。

## 測驗 3