# 2024q1 Homework2 (quiz1+2)
contributed by <`Libright1558`>

## 第一週測驗題
### 測驗一

#### `運作原理`
此處的非遞迴 (non-recursive; iterative) 快速排序法 (QuickSort) 用以重新排列「鏈結串列」，以下為程式碼運作原理︰

透過建立 `node_t *begin[max_level], *end[max_level]` 兩個陣列作為儲存串列排序開始與結束的對應節點位置，其中 `max_level` 為整個串列長度的 2 倍，提供比串列長度更長的可堆疊數量，以避免串列長度太長，造成 stack overflow 。

首先將串列的起始與結束位置節點分別紀錄在 `begin[0]` 與 `end[0]` 裡，之後分別宣告 `node_t *L = begin[i], *R = end[i]` ， `i` 初始值為 0 ，將 `pivot` 指定為 `L` ，紀錄`value` 後，將其從串列中分離出來。

之後從串列的下一個節點開始，將其中的值與先前紀錄的 `value` 作比對，如果前者大於後者，則將該節點移至 `node_t *right` ，如否，則移至 `node_t *left`。

將 `begin[i]` 與 `end[i]` 分別賦值為 `node_t *left` 串列的起始與結束位置，`begin[i+1]` 與 `end[i+1]` 則賦值為 `pivot` ，`begin[i+2]` 與 `end[i+2]` 則賦值為 `node_t *right` 串列的起始與結束位置。 此舉為紀錄串列節點起始、 `pivot` 與結束位置至堆疊內，留待後續排序進行。

如果 `L` 與 `R` 位置重合，則把 `L` 位置的節點添加至 `node_t *result` 上，待排序完成後，將 `result` 賦值到原先 `*list` 位置上，排序結束。

#### `改進方案`

1.初步思路︰
原先的 `quickSort` 實作，選擇 `pivot` 的位置均位於串列最左側，若遇到幾乎已經排序完成的串列，則時間複雜度在最糟的情況下會達到 $O(n^2)$，解決此問題的其中一種方式，是每次在選擇 `pivot` 時，大小均接近該串列的中位數，盡量確保串列被切成大小接近的子串列。

### 測驗二

#### `運作原理`

>[程式碼](https://github.com/Libright1558/2024q1_Homework2/blob/master/timsort/timSort.c)

##### `run_size`

傳入 `list_head` 引數，回傳該串列中頭節點的位址 （以 `size_t` 為單位），若頭節點不存在，回傳 0 ，若只有頭節點存在，回傳 1 。

一開始我的疑惑為，為何在回傳頭節點位址時，需要用 ` （size_of）head->next->prev` ，而不是直接回傳 `(size_of) head`，之後我決定撰寫一個測試用程式來驗證。

printf("head size: %ld\n", (size_t) h);
printf("head size (view at next node): %ld\n", (size_t) h->next->prev);

h->next->prev = (struct list_head *) 5;
printf("head size (view at next node): %ld\n", (size_t) h->next->prev);

上述部份程式碼輸出的結果如下︰

head size: 94529421296288
head size (view at next node): 94529421296288
head size (view at next node): 5

可以發現到，透過指派 `(struct list_head *) 5` 到 `h->next->prev`，使原先 `h` 的位址變成 5 ，但如果直接指派給 `h` ︰

test.c:23:9: warning: ‘free’ called on a pointer to an unallocated object ‘10’ [-Wfree-nonheap-object]
   23 |         free(h);
      |         ^~~~~~⇚
test.c:20:7: note: assigned here
   20 |     h = (struct list_head *) 10;
      |     ~~^~~~~~~~~~~~~~~~~~~~~~~~~

編譯器在編譯的過程中出現了“試圖釋放未分配的記憶體”警告，因為在程式結束前，我會先使用 `free` 釋放先前使用 `malloc` 分配位置的節點，然而在將 10 指派給 `h` 後出現此警告，而實際執行結果為︰

head size: 94084053238432
head size: 10
Segmentation fault (core dumped)

`h` 的位址被成功變更為 10 ，然而也存取了未經分配的記憶體位址，導致 Segmentation falut 發生，這裡我推測，如果直接使用分配空間後，被指派該空間位址的指標，會導致該指標直接被位移而產生錯誤。如果使用 `h->next->prev` 這類位址參照到頭節點的指標，則位移的會是 `h->next->prev` 而非 `h`，因此在 `run_size` 函式最後回傳`（size_of）head->next->prev` ，而不是直接回傳 `(size_of) head` 。

##### `merge`

分別宣告 `struct list_head *head` 與 `struct list_head *tail = &head` ，之後使用 `cmp` 函式比對 `struct list_head *a` 與 `struct list_head *b` 節點內部的值，若結果小於或等於 0 ，則將 `a` 上對應的節點接到 `head` 後面；若結果大於 0 ，則將 `b` 上對應的節點接到 `head` 後面。直到 `a` 或 `b` 串列結束，並將剩餘串列接上後，回傳 `head` 。

##### `build_prev_link`

重新建立串列間，`prev` 連結的部份，最後將串列接成環狀。

##### `merge_final`

將最後已排序完成的串列接在一起，形成 double linked-list ，最後再將串列首尾相接，完成最後的合併。

##### `find_run`

回傳每個 `run` 的頭尾位置。首先宣告 `struct list_head *next = list->next, *head = list` ，再宣告 `struct pair result` ，`next` 指向 `list` 開頭的下一個節點， `head` 指向 `list` 開頭節點， `result` 則是最後會回傳的值，另外宣告 `size_t len` 並將值設為 1 。

如果 `next` 節點不存在，則直接回傳 `list` 頭節點與 `next` 的位置。

`list` 與 `next` 節點會經過 `cmp` 函式進行比對，若結果大於 0 ， 先將 `len` 值加 1 ，並將 `list` 上的節點反向加入至 `prev` 節點 （`prev` 節點的 `next` 指標指向 `list`），直到 `next` 為 NULL 或 `cmp` 比對結果小於或等於 0 。

若比對結果小於或等於 0 ，先將 `len` 值加 1 ，之後 `list` 與 `next` 指標走訪 `list` 串列，直到 `next` 為 NULL 或 `cmp` 比對結果大於 0 。

最後將 `head->prev` 設為 NULL，並將 `head->next->prev` 設為 `(struct list_head *) len`，以表示該次 `run` 的長度，回傳 `list` 頭節點與 `next` 的位置。

##### `merge_at`

先計算 `at` 與 `at->prev` 的 run size 大小 `len` ，並紀錄 `at->prev->prev` 節點於 `prev` ，之後合併 `at` 與 `at->prev` 串列於 `list` ，並將 `prev` 接到 `list->prev` 上。將 `len` 值紀錄於 `list->next->prev` ，`stk_size` 減 1 (代表紀錄每個 `run` 的堆疊，合併後減少 1 個 `run`)，最後回傳 `list` 。

##### `merge_collapse`

在 `stk_size` （紀錄 `run` 的堆疊）裡的 `run` 數量大於等於 2 的情況下，進行以下迴圈︰

(1) 如果 `stk_size` 大於等於 3 ，且`list_head` 串列 `tp` 與 `tp->prev` 的 `run_size` 相加結果大於或等於 `tp->prev->prev` 的 `run_size` ，或是 `stk_size` 大於等於 4 ，且`list_head` 串列 `tp->prev` 與 `tp->prev->prev` 的 `run_size` 相加結果大於或等於 `tp->prev->prev->prev` 的 `run_size`︰

1.如果 `tp->prev->prev` 的 `run_size` 小於 `tp` 的 `run_size` ，則將 `tp->prev->prev` 與 `tp->prev` 這 2 個 run 進行合併。

2.其他情況下，則將 `tp->prev` 與 `tp` 這 2 個 run 進行合併。

(2) 如果 `tp->prev` 的 `run_size` 小於或等於 `tp` 的 `run_size` ，則將 `tp->prev` 與 `tp` 這 2 個 run 進行合併。

(3) 其他情況下，跳出迴圈。

最後回傳 `tp` 。

##### `merge_force_collapse`

在 `stk_size` （紀錄 `run` 的堆疊）裡的 `run` 數量大於等於 3 的情況下，進行以下迴圈︰

(1)如果 `tp->prev->prev` 的 `run_size` 小於 `tp` 的 `run_size` ，則將 `tp->prev->prev` 與 `tp->prev` 這 2 個 run 進行合併。

(2)其他情況下，則將 `tp->prev` 與 `tp` 這 2 個 run 進行合併。

最後回傳 `tp` 。

##### `timsort`

先初始化 `stk_size` 為 0 ，接著宣告 `struct list_head *list = head->next, *tp = NULL` ，如果只有 `head` 頭節點存在就直接 `return` 。之後將 `head` 串列轉換成 singly-linked list ，在 `list` 不為 NULL 的情況下進行以下迴圈︰

使用 `find_run` 找到對應該 `list` 的 `run` 範圍，並將結果的頭節點接在 `tp` 後面，將 `tp` 指向該結果的頭節點， `list` 則指向該結果的 `next` 節點，將 `stk_size` 加 1 ，之後用 merge_collapse 嘗試合併 `tp` 與 `tp->prev` 。

用 merge_force_collapse 合併剩下的 `run` 。

在 `tp->prev` 與 `tp->prev->prev` 不為 NULL 的情況下進行以下迴圈︰

將 `tp->prev` 值指派給 `tp` ，將 `tp->prev->prev` 值指派給 `tp->prev` 。

結束迴圈後，如果 `stk_size` 小於等於 1 ，使用 `build_prev_link` 重建雙向鏈接串列並 `return` 。

最後用 `merger_final` 合併剩餘的串列。

## 第二週測驗題

### 測驗一

#### `運作原理`

藉由 `preorder` 與 `inorder` 陣列建構二元樹，首先須分配 `inorder` 長度乘以 `struct hlist_head` 大小的空間，之後將該空間以 `INIT_HLIST_HEAD` 函式進行初始化，作為存放 hash list 開頭的陣列。之後將 `inorder` 中，`value` 所對應的 `idx`，存放進 hash list 內，之後便可根據 `value` 來尋找 `idx`，最後透過 `dfs` 函式建構二元樹。

### 測驗二

#### `運作原理`

在建立 `LRUCache` 時，除了分配 2 個 integer 空間以外，另外還會分配 1 個 `list_head` 大小的空間 (作為開頭) 與 `capacity` 個數的`list_head` 空間 (用以紀錄 `LRUNode` 的 `list_head` 節點)，`capacity` 即 `LRUCache` 所能容許的 `LRUNode` 數目上限。

在使用 `lRUCacheGet` 並根據 `key` 找尋特定位置的節點時，`key` 會被轉換為 `hash` 值，對應到 `LRUCache` 上的 `hhead` 陣列某一位置，並沿著 `hlist` 串列尋找 `LRUNode` 是否有對應的 `key` ，如否，則返回 -1，如果找到對應的 `key`，則將該 `LRUNode` 上的 `list_head` 節點搬移至 `dhead` 開頭位置，並返回 `LRUNode` 對應的 `value`。

使用 `lRUCachePut` 新增 `key/value` 時，先將 `key` 轉換為 `hash` 值，對應到 `LRUCache` 上的 `hhead` 陣列某一位置，並沿著 `hlist` 串列尋找 `LRUNode` 是否有對應的 `key` ，如否，先確認 `count` 值是否已達到 `capacity` 上限，如已達到上限，則將位於 `LRUCache` 之 `list_head` 串列的最後一個節點搬移至 `dhead` 開頭，並且也將 `hlist` 中對應的節點搬移至 `hhead` 開頭，以新的 `key/value` 值覆蓋舊值。反之，則分配 1 個 `LRUNode` 大小的空間，並額外新增此一節點至 `hlist` 與 `list_head`，新增 `key/value` 值，並將 `count` 數加 1 。

### 測驗三

#### `運作原理`