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

## 測驗 2

<s>

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
};

#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        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]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &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);

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

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

取 ```HHHH``` 為 ```list_splice_tail```
取 ```GGGG``` 為 ```list_for_each_entry_safe```
取 ```IIII``` 為 ```&stack[++top]```
取 ```JJJJ``` 為 ```&stack[++top]```
取 ```KKKK``` 為 ```&stack[top--]```
</s>

:::danger
不用抄題目。闡述你的認知和想法。
:notes: jserv
:::

#### 解釋程式碼原理
- 串列中的元素的排序取決於當前 while loop 的 ```partition``` 處理對象的順序，並且由 ```stack[top]``` 決定
- 在第 38 行中，依據 stack 的性質，```list_less``` 會是下一輪的 while loop 的 ```partition``` 處理對象。也就是會先處理最小值
- 最終當串列中元素數量小於等於 1 時，即表示此為當前最小值。
- 在 else case 中，將此串列的元素(僅有 1 個元素)加入至 ```head``` 末端中

<!--
用 graphviz 繪製圖片有點麻煩 :)
使用 ASCIIFlow 網站繪製 :P
https://asciiflow.com/
-->

以表格顯示過程
:::danger
使用 Graphviz 重製，並嵌入於 HackMD 頁面。
:notes: jserv
:::

最一開始 stack 內容
    +------+
    | head |
    +------+

第一次 while loop 後 -->
    +-------+ +-------+ +------+
    | empty | | great | | less |
    +-------+ +-------+ +------+
top:    0        1          2

第二次 while loop 後 -->
    +-------+ +-------+ +-------+ +-------+ +------+
    | empty | | empty | | great | | great | | less |
    +-------+ +-------+ +-------+ +-------+ +------+
top:    0         1         2         3        4

很多次 while loop 後 -->
    +----------+ +----------+ +----------+
    | singular | | singular | | singular |
    +----------+ +----------+ +----------+
top:   ...          ...         ...

#### 指出其缺失
參考上面表格的第二次 ```while loop``` 後，產生用不到的 ```empty```，```empty``` 的數量為（$n$ 為節點數量) ，此不計算 ```singular``` 數量：
$$
2^0 + 2^1 + ... + 2^{(log_2{n}) - 1} \
= 2^{(log_2{n})} - 1 = n - 1
$$
若 n = 256，```empty``` 的數量為 255 個，因此 ```MAX_DEPTH=512``` 實際能夠處理的節點數量少於 ```256``` 個

#### 比較和實驗
<!--
perf:
https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg
-->

#### 效能改進方案
- 特別是避免依賴 ```MAX_DEPTH```：可以先想到的就是將 ```MAX_DEPTH``` 替換為 ```head``` 的節點數量，並且在某些步驟時將 ```empty``` 移除，(或是 circular stack?)
- 另一種偶然想到的方式， linked list 與 Array 混合版本，例如：

struct StackArray{
    struct list_head chain;
    struct list_head stack[MAX_DEPTH];
}

<!--
改進參考步驟
https://hackmd.io/@sysprog/c-linked-list#%E9%9D%9E%E9%81%9E%E8%BF%B4%E7%9A%84%E5%AF%A6%E4%BD%9C
-->