# 2024q1 Homework2 (quiz1+2)
contributed by < `Grace258` >
- [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
- [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
---
## 測驗 `1`
實作非遞迴 `(non-recursive)` 的快速排序法，以 `swap` 為主體，利用 `L` 與 `R` 去紀錄需交換的數量，再用 `begin[]` 與 `end[]` 作為堆疊，用來紀錄比較的範圍。
### node_t *list_tail(node_t **left)
```cpp=
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &((*left)->next); //AAAA
return *left;
}
```
將 `*left` 移到鏈結串列的最後一個節點，因為使用 `indirect pointer` 所以要加上 `&` 取得指標的位址。
```graphviz
digraph nodes{
subgraph cluster_1{
style = invis
node1[label = "node1", shape = rect]
node2[label = "node2", shape = rect]
node3[label = "node3", shape = rect]
NULL[shape = plaintext]
{rank = same; node1->node2->node3->NULL}
}
left[label = "*left", shape = plaintext, fontcolor = green]
left->node3
}
```
```
#4 left = &((*left)->next);
```
---
### int list_length(node_t **left)
```cpp=
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &((*left)->next); //BBBB
}
return n;
}
```
將 `*left` 移到鏈結串列的最後端 `(NULL)` ，因為使用 `indirect pointer` 所以要加上 `&` 取得指標的位址。
```graphviz
digraph nodes{
subgraph cluster_1{
style = invis
node1[label = "node1", shape = rect]
node2[label = "node2", shape = rect]
node3[label = "node3", shape = rect]
NULL[shape = plaintext]
{rank = same; node1->node2->node3->NULL}
}
left[label = "*left", shape = plaintext, fontcolor = green]
left->NULL
}
```
```
#6 left = &((*left)->next);
```
---
### void quick_sort(node_t **list)
```cpp=
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next; //CCCC
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = list_tail(&left); //DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right); //EEEE
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
使用指標 `n` 走遍整個鏈結串列，將除了 `head/pivot` 節點的剩餘部分分成鏈結串列 `right` 和鏈結串列 `left` ，並將這三個鏈結串列的指標放入 `stack(begin 和 end)` 中。
```graphviz
digraph{
subgraph cluster_1{
style = invis
node0[label = 4, shape = rect]
node1[label = 1, shape = rect]
node5[label = 7, shape = rect]
node4[label = 2, shape = rect]
node3[label = 5, shape = rect]
node2[label = 3, shape = rect]
{rank = same; node5->node4->node3->node2}
}
head[label = "head", shape = plaintext, fontcolor = red]
pivot[label = "pivot", shape = plaintext, fontcolor = green]
left[label = "left", shape = plaintext, fontcolor = green]
right[label = "right", shape = plaintext, fontcolor = green]
head->node0
pivot->node0
left->node1
right->node5
}
```
將整個鏈結串列分成 `pivot` 、 `left` 、 `right` 三個部分( `left` 放小於 `pivot` 的節點， `right` 放大於 `pivot` 的節點)
```graphviz
digraph{
subgraph cluster_1{
style = invis
node0[label = 2, shape = rect]
node1[label = 5, shape = rect]
node2[label = 3, shape = rect]
node3[label = 7, shape = rect]
NULL[shape = plaintext]
{rank = same; node0->node1->node2}
}
pivot[label = "pivot", shape = plaintext, fontcolor = green]
left[label = "left", shape = plaintext, fontcolor = green]
right[label = "right", shape = plaintext, fontcolor = green]
pivot->node3
left->node0
right->NULL
}
```
```graphviz
digraph{
subgraph cluster_1{
style = invis
node0[label = 2, shape = rect]
node1[label = 5, shape = rect]
node2[label = 3, shape = rect]
NULL[shape = plaintext]
{rank = same; node1->node2}
}
pivot[label = "pivot", shape = plaintext, fontcolor = green]
left[label = "left", shape = plaintext, fontcolor = green]
right[label = "right", shape = plaintext, fontcolor = green]
pivot->node0
left->NULL
right->node1
}
```
```graphviz
digraph{
subgraph cluster_1{
style = invis
node0[label = 3, shape = rect]
node1[label = 5, shape = rect]
NULL[shape = plaintext]
}
pivot[label = "pivot", shape = plaintext, fontcolor = green]
left[label = "left", shape = plaintext, fontcolor = green]
right[label = "right", shape = plaintext, fontcolor = green]
pivot->node1
left->node0
right->NULL
}
```
重複執行直到 `left` 、 `right` 、`pivot` 都排序完畢。
### 改進方案
```cpp=
void quick_sort(struct list_head *head) {
if (list_empty(head) || list_is_singular(head))
return;
struct list_head *pivot = list_entry(head->prev, struct list_head, list);
struct list_head *left_list, *right_list;
INIT_LIST_HEAD(&left_list);
INIT_LIST_HEAD(&right_list);
struct list_head *pos, *q, *entry;
list_for_each_safe(pos, q, head) {
struct list_head *tmp = list_entry(pos, struct list_head, list);
if (tmp != pivot) {
list_del(pos);
INIT_LIST_HEAD(pos);
if (tmp->value < pivot->value){
list_for_each_entry(entry, left_list, list) {
if (tmp->value < entry->value) {
list_add_tail(&tmp->list, &entry->list);
return;
}
}
list_add_tail(&tmp->list, &left_list);
}
else{
list_for_each_entry(entry, right_list, list) {
if (tmp->value < entry->value) {
list_add_tail(&tmp->list, &entry->list);
return;
}
}
list_add_tail(&tmp->list, &right_list);
}
}
}
quick_sort(&left_list);
quick_sort(&right_list);
list_splice_tail(&left_list, head);
list_add_tail(&pivot->list, head);
}
```
## 測驗 `2` `Timsort`
Sign in with Wallet
Connect another wallet