# 2023q1 Homework (quiz1) contributed by < terry23304 > ## 測驗 1 ### 運作原理 ```graphviz digraph pic1 { rankdir = LR; {4->9->2->5->8}; } ``` 取第一個 entry 當`pivot`，並把`pivot`移除串列 ```c struct item *pivot = list_first_entry(head, item, list); list_del(&pivot->list); ``` ```graphviz digraph pic1 { rankdir = LR; {rank = 1 9->2->5->8} {rank = 2 pivot->4}; } ``` 使用 `list_for_each_entry_safe` 迭代，當節點值小於 pivot 就用 `list_move_tail` 把節點移到 `list_less` 的最後，大於則移到 `list_greater` 的最後 ```c list_for_each_entry_safe (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) list_move_tail (&itm->list, &list_less); else list_move_tail (&itm->list, &list_greater); } ``` ```graphviz digraph pic1 { rankdir = LR; {rank = 1 greater->9->5->8} {rank = 2 less->2}; {rank = 3 pivot->4}; } ``` 並遞迴執行直到 `list_less` 與 `list_greater` 排序完成 ```c list_sort(&list_less); list_sort(&list_greater); ``` ```graphviz digraph pic1 { rankdir = LR; {rank = 1 greater->8} {rank = 2 less->5}; {rank = 3 pivot->9}; } ``` 再將 pivot 加回串列中，並用 `list_splice` 將 `list_less` 加到 head 後， pivot 之前再執行 `list_splice_tail` 將 `list_greater` 加回結尾完成排序。 ```c list_add(&pivot->list, head); list_splice(&list_less, head); list_splice_tail(&list_greater, head); ``` ```graphviz digraph pic1 { rankdir = LR; {rank = 1 head->2->4} } ``` ```graphviz digraph pic1 { rankdir = LR; {rank = 1 head->2->4->5->8->9} } ``` - [ ] 針對 Quick sort 提出上述程式碼的改進方案並實作 - [ ] 引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響 ## 測驗 2 ### 運作原理 用 stack 來模擬遞迴 一開始先將要排序的串列移到 stack[0]，並把 head 變成 NULL queue，用`top`紀錄 stack 位置 ```c int top = -1; list_splice_init(head, &stack[++top]); ``` 每次迴圈將 stack 最上層的 queue 移到`partition list`中。 ```c INIT_LIST_HEAD(&partition); list_splice_init(&stack[top--], &partition); ``` - `partition` 若長度大於一則表示子串列尚未完成排序，將`partition list`第一個 entry 移出當成 pivot ，迭代 partition list 小於 pivot 的點移到 `list_less` 的開頭，大於等於則移到 `list_greater` 的開頭 ```c 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; list_for_each_entry_safe (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); } ``` 最後把 pivot 放到 `list_less` 的結尾，若`list_greater`非空則 push 到 stack ，再檢查`list_less`，若非空則 push 到 stack ```c list_move_tail (&pivot->list, &list_less); if (!list_empty(&list_greater)) list_splice_tail(&list_greater, &stack[++top]); if (!list_empty(&list_less)) list_splice_tail(&list_less, &stack[++top]); ``` - 若`partition`長度小於等於一則表示子串列完成排序，把`partition` push 到 stack(感覺不需要)，並把節點移到 head 尾(stack 最小值在最上面)，合併完後就排序完成。 ```c 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(&stack[top--]); list_add_tail(&tmp->list, head); } ``` ### 設計、實作缺失 以下四行可換成 `list_splice_tail_init(&stack[top], head)` ```c struct item *tmp = list_first_entry(&stack[top], struct item, list); list_del(&tmp->list); INIT_LIST_HEAD(&stack[top--]); list_add_tail(&tmp->list, head); ``` - [ ] 比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快 - [ ] 提出效能改進方案，特別是避免依賴 MAX_DEPTH - [ ] 引入 Introsort，也就是 quick sort 和 heap sort 當 quicksort 迭代 $2∗log(n)$ 次後還排序完成，那就很可能會得到 $O(n^2)$