# 2025q1 Homework2 (quiz1+2)
contributed by <`lum1nar`>

## quiz1

### 測驗一

#### main 函式
`main()` 中呼叫 `test_suite()` ，使用 `my_run_test(test_list)` 進行測試。一開始我疑惑 `my_run_test` 內部的 `test()` 是什麼，文件中都沒有定義，但後來發現要替換成傳入的函式 `test_list()`。

#define my_run_test(test)       \
    do {                        \
        char *message = test(); \ /* message = test_list() */
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)

#### 使用巨集來呼叫函式
我一直認爲巨集會把左方的內容全部展開成右方的內容，但其實是可以傳入參數的。

#define sqrt(x) x*x

sqrt(5) -> 5 * 5

再來，爲何要使用 `do{} while(0)` 呢？這是安全定義巨集的方法，考慮以下代碼

/* 巨集定義 */
#define my_assert(test, message) if (!(test)) return message;

/* 我們展開以下判斷式 */
if (condition)
    my_assert(some_test, "error");
else
    do_something();  // 這裡會導致語法錯誤

/* 展開後 */
if (condition)
    if (!(some_test)) return "error";  /* 這裡會因為沒有大括號導致 else 無法正確匹配 */
else
    do_something();

/* 如果加上do{}while(0) */
if (condition)
    do {
        if (!(some_test)) return "error";
    } while (0);

    do_something();  /* 這樣就不會有問題 */

#### test_list
這段程式首先做了 `list_reset` ， 將 `items[i]` 初始化爲 `i`。用意在於 `list_insert_before` 所傳入的是節點，而非整數，因此這一步先將要插入的數值放進節點中。最後，把 `l.head` 設爲 `NULL` 初始化鏈接串列。初始化完成後，使用迴圈在頭部插入節點，並透過 `my_assert` 來檢查是否有錯誤，後續的插入尾部也是相同的步驟。但不確定最後一次的插入和倒數第二次的有何區別。

#### 圖示
以插入 999 爲例
首先，我們呼叫 `list_insert_before`
當 `*p == before` 時，我們將 `*p` 設爲 `999`，即把 `head` 指向 `999`
再來把後續節點接上，就完成了插入。

### 測驗二

### 測驗三

#### 程式脈絡
陣列經過 `shuffle` 函數隨機排列過後，使用 `list_construct` 來插入節點。進行排序之後，使用 `list_is_ordered` 檢查是否結果正確，最後使用 `list_free` 來釋放所有節點。`max_level` 設爲 `2n` 有點讓我疑惑，即使每次分割後`left` 或 `right` 只有一個元素的情況下，應該也只需要 `n` 的空間就足夠了。

#### quicksort
首先，我們透過以下代碼將原本鏈接串列轉爲非環狀鏈接串列，並且傳入鏈接串列中第一個元素作爲開頭。

list->prev->next = NULL;
begin[0] = list->next;

將 `L` 和 `R` 指向當前鏈接串列的兩端，`Pivot` 設爲 `L`
將小於 `Pivot` 值的節點放入 `left` ，反之，則放入 `right`，再將 `pivot`、`left`、`right`分別放入 `begin[i]` 到 `begin[i+2]` 中，方便後續取出。
由 `begin[i+2]` 繼續進行分割，目的是用新的 `left` 覆蓋掉已經拆開的 `right`，就不會重複取到值

當分割到鏈接串列中只剩一個元素，或是 `Right` 不存在時，前者代表 `Right` 之中有最大值，我們直接取出。後者代表當前 `pivot` 擁有最大值，我們回到 `begin[i-1]` 去取出節點。


取完最大值之後，到了 `begin[2]` ，發現內部有大於一個節點，因此我們能夠用相同方法繼續分割


全部分割完後，我們可以確保，越大的節點，會放在 `begin` 中越後面的位置。因此我們只有從尾巴走訪到開頭，沿途將節點放入 `result` 中，即可完成排序。


最後再使用以下 `rebuild_list_link` 函式，將鏈接串列恢復成環狀，並且將開頭連結起來，就完成了。

    list->next = result;
    rebuild_list_link(list);


實際畫圖時會發現將節點移動到 `left`、`right` 時，鏈接串列之間的鏈接變得不好展示，時間因素影響，沒有全部畫出來，也因此對於細節的掌握度還不夠。

## quiz2

### 測驗一

#### 圖例
考慮以下鏈接串列
首先,我們將串列中第一個元素設爲 `pivot` 並且從鏈接串列中移除，再來把大於 `Pivot` 的元素移動到 `list_greater`，反之則移動到 `list_less`。
再來，分別對 `less` 和 `greater` 進行 quicksort，由於 `less` 只有一個元素，因此不必再拆分。
由於 `less` 爲空， `greater` 僅有一個元素，我們將三者依照 less，pivot，greater 的順序合併。
再次合併
做圖到最後一步時發現忘記加上 `prev` 指標。

> 探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
>
考慮以下鏈接串列
我們依照上面的方式進行拆分，但把 `list_move_tail` 改成 `list_move`
拆開 `greater`
接下來依照 less，pivot，greater 的順序合併。
相同數值的節點重新進行了排序，因此不符合 Stable Sorting。

### 測驗二

### 測驗三
* `map->bits` 的大小決定了 `bucket` 的大小。
* 雜湊函數
* 爲何在雜湊函數內部要乘以黃金比例呢？乘以黃金比例可以用來打散 `key` 的分佈,如果 key 本身的數據有某些模式會導致連續 `key` 落入相鄰的 `bucket`
* 爲何要右移 (32 - bit) 呢？前面說道，map->bits 決定了 `bucket` 大小，因此我們僅需要 `map->bits` 個 bit。而更高位的 bit 更能使得 hash 分佈更平均。