# 2021q1 Homework1 (quiz1)
contributed by < `ngokchaoho` >
> [2021q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
## 程式運作原理
### `list_add_node_t` 加新的節點到 list 開頭
```cpp
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
* 這裡使用到了 pointer to pointer 的技巧，`*list` 指向 head （e.g. A）
`list_add_node_t 前`
```graphviz
digraph graphname{
"*list"[shape=plaintext,fontcolor=red]
list[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=note_t]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
list[shape=plaintext,fontcolor=blue]
list->"*list"->A
}
A->B->C->NULL1
D->NULL2
}
```
`list_add_node_t 後`
```graphviz
digraph graphname{
"*list"[shape=plaintext,fontcolor=red]
list[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=note_t]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
list[shape=plaintext,fontcolor=blue]
list->"*list"->D
}
D->A->B->C->NULL1
}
```
### `list_concat` 合併兩個 list
```c++
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next)
*left = right;
}
```
#### before:
```graphviz
digraph graphname{
"*left"[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
E[label=E]
F[label=F]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->"*left"->A
right[shape=plaintext,fontcolor=blue]
right->D
}
A->B->C->NULL1
D->E->F->NULL2
}
```
#### in the middle:
travel through left list, `left = &((*left)->next)`
```graphviz
digraph graphname{
"*left"[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
"(*left)->next"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->"*left"->A
"(*left)->next"->B
}
A->B->C->NULL1
}
```
```graphviz
digraph graphname{
left[shape=plaintext,fontcolor=blue]
"(*left)->next"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
left->"(*left)->next"->B
}
A->B->C->NULL1
}
```
until
```graphviz
digraph graphname{
"*left"[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->"*left"->NULL1
}
A->B->C->NULL1
}
```
and now change what C is pointing (represented by `*left`) to `right` i.e. the address of D
#### after:
```graphviz
digraph graphname{
"*left"[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
E[label=E]
F[label=F]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left[shape=plaintext,fontcolor=blue]
left->"*left"->D
right[shape=plaintext,fontcolor=blue]
right->D
}
A->B->C->D->E->F->NULL2
}
```
### quick sort 主要邏輯
```c++
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot); list_concat(&result, right)
*list = result;
}
```
- 如果` *list ` 指向 NULL則結束，沒有需要排序
- 否則將鏈表的開頭 pivot 割出，初始化 p 為第二個node， 並用 p 遍歷 list
- 將每一個 p 指向的 node 與 pivot 指向的 node 的 value 比較，建立嚴格比 ` pivot->value ` 小的 left list 和嚴格比嚴格比 `pivot->value`大的 right list.
- 對 left list 同 right list 分別 quicksort 引發遞迴，結束條件為 NULL
- 返回後, left list 同 right list 都是有序 list, 不斷從左往右加上更大的sublist
- 回傳 result
#### start:
```graphviz
digraph graphname{
"p"[shape=plaintext,fontcolor=red]
"pivot"[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=3]
D[label=1]
E[label=2]
F[label=0]
NULL2[label=NULL,shape=plaintext]
NULL3[label=NULL,shape=plaintext]
}
{
rank="same";
"p"->B
"pivot"->A
}
A->NULL3
B->C->D->E->F->NULL2
}
```
#### split:
```graphviz
digraph graphname{
"pivot"[shape=plaintext,fontcolor=blue]
"left"[shape=plaintext,fontcolor=blue]
"right"[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=3]
D[label=1]
E[label=2]
F[label=0]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
NULL3[label=NULL,shape=plaintext]
}
{
rank="same";
"pivot"->A
"left"->C
"right"->B
}
C->D->E->F->NULL1
B->NULL2
A->NULL3
}
```
#### after further recursive quicksort:
```graphviz
digraph graphname{
"pivot"[shape=plaintext,fontcolor=blue]
"left"[shape=plaintext,fontcolor=blue]
"right"[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=3]
D[label=1]
E[label=2]
F[label=0]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
NULL3[label=NULL,shape=plaintext]
}
{
rank="same";
"pivot"->A
"left"->F
"right"->B
}
F->D->E->C->NULL1
B->NULL2
A->NULL3
}
```
#### concat:
```graphviz
digraph graphname{
"pivot"[shape=plaintext,fontcolor=blue]
"left"[shape=plaintext,fontcolor=blue]
"right"[shape=plaintext,fontcolor=blue]
"result"[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=3]
D[label=1]
E[label=2]
F[label=0]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
"pivot"->A
"left"->F
"result"->F
"right"->B
}
F->D->E->C->A->B->NULL1
pivot
}
```
Sign in with Wallet
Connect another wallet