# 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)$
Sign in with Wallet
Connect another wallet