# 2024q1 Homework2 (quiz1+2)
contributed by < [yc199911](https://github.com/yc199911) >
## 第一週測驗題
### 測驗一：實作非遞迴 (non-recursive; iterative) 的快速排序法。
`假設一個序列為 4, 1, 3, 5, 2, 7`
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "4", group = g1];
n2[label = "1", group = g1];
n3[label = "3", group = g1];
n4[label = "5", group = g1];
n5[label = "2", group = g1];
n6[label = "7", group = g1];
n2->n3;
n3->n4;
n4->n5;
n5->n6;
n1->n2;
}
```
`運作原理`：首先，從給定的鏈結串列中將最左邊的點設為 pivot ，接著將 pivot->next 指向 NULL 。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "4", group = g1];
n2[label = "1", group = g1];
n3[label = "3", group = g1];
n4[label = "5", group = g1];
n5[label = "2", group = g1];
n6[label = "7", group = g1];
n2->n3;
n3->n4;
n4->n5;
n5->n6;
pivot->n1;
n1->null;
}
```
執行完這個 while 迴圈後會將鏈結串列分為 `left` 和 `right`
```c=
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "4", group = g1];
n2[label = "1", group = g1];
n3[label = "3", group = g1];
n4[label = "5", group = g1];
n5[label = "2", group = g1];
n6[label = "7", group = g1];
n2->n3->n5;
n4->n6;
pivot->n1;
n1->null;
right->n2;
left->n4;
}
```
因為每次執行完都是 `i += 2` 表示會先將整個 `right` 的鏈結串列逐一分解至只剩一個 `node` 。
```c=
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
```
而當只剩一個 `node` 時，會執行 `list_add` 接著 `i --` ，此時 `begin` 和 `end` 皆為 pivot ，再執行一次 `list_add` 即可開始排序 `left` 的部分。
### 測驗二 ： Timsort
`運作原理`：透過 `find_run` 去尋找一個遞增或遞減的 `run`
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "7", group = g1];
n8[label = "8", group = g1];
n1->n2->n3->n4->n5->n6->n7->n8->null;
}
```
進行第一次 `find_run` 後，即為下圖所示。
此時因為 `stk_size＝1` 所以不會執行 `merge_collapse`，繼續執行 `do while`。
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR" {
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "7", group = g1];
n8[label = "8", group = g1];
tp->n1->n2->n3->n4->null;
list->n5->n6->n7->n8->nul;
result_next->n5;
}
{
rank = "smae"
result_head->n1;
}
}
```
因為 3 ,2 為 descending run ，所以須將他翻轉為 ascending run。
```c=
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
```
```graphviz
digraph list
{
graph [fontsize=12 fontname="Verdana" compound=true];
node [shape="record"];
rankdir = "LR"
n1[label = "1", group = g1];
n2[label = "2", group = g1];
n3[label = "3", group = g1];
n4[label = "4", group = g1];
n5[label = "3", group = g1];
n6[label = "2", group = g1];
n7[label = "7", gtoup = g1];
n8[label = "8", gtoup = g1];
tp->n1->n2->n3->n4->null;
n2->len_4;
n6->n5;
n5->len_2;
n6->tp;
result_head->n6;
list->n7->n8->nul;
result_next->n7;
}
```
```c=
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
```
Sign in with Wallet
Connect another wallet