# 2023q1 Homework1 (quiz1)
contributed by < [zeddyuu](https://github.com/zeddyuu) >
## 測驗 1
```c
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) 內有提到，是為了要讓程式設計者透過顯式轉型避免危險的指標操作。
```c
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。
```c
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
```c
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`
```c
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
```c
if (list_empty(head) || list_is_singular(head))
return;
```
先確定 list 是否為空或只有一個節點，是的話就不用進行排序。
```c
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 中。
```c
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
宣告一個 partition 變數，用來處理等等要排序的 list。
```c
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
當 stack 內還有待排序的 list 時才執行這個 while 迴圈，迴圈一開始會將放在 stack 最上面的 list 用 `list_splice_init` 接在 partition 做處理。
```c
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 的第一個元素。
```c
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`
```c
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]`
```c
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--]`
### 延伸問題
#### 指出設計和實作的缺失
程式碼在一開始就定義了
```c
#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
Sign in with Wallet
Connect another wallet