# 2021q1 Homework1 (quiz1)
contributed by < `hapion` >
## :memo: 預期目標
* 檢驗學員對於 C 語言指標操作的熟悉程度
* 檢驗學員對於遞迴呼叫的認知
* 搭配 [Graphviz](https://graphviz.org/) 在 HackMD 筆記上視覺化展現
## 程式運作原理
- 將 node 添加至 list 的最前端
```c
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
```graphviz
digraph graphname{
node[shape=box]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
node_t
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
"*list"->A
}
node_t->A
A->B->C->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
"*list"[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
node_t
A[label=A]
B[label=B]
C[label=C]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
"*list"->node_t
}
node_t->A
A->B->C->NULL1
}
```
- 將兩個 list 串連起來
``` c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
``` c
static inline void list_concat(node_t **left, node_t *right)
```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structp [label="left|<p>&(*left)"]
structptr [label="<name_ptr> *left|<ptr> &A"];
structb [label="<B> B|2"];
structa [label="<A> A|1"];
structc [label="<C> C|3"];
structptr:ptr -> structa:A:nw
structp:p -> structptr:ptr:nw
}
```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structd,structe,structf}
structptr [label="<name_ptr> *right|<ptr> &D"];
structe [label="<E> E|2"];
structd [label="<D> D|1"];
structf [label="<F> F|3"];
structptr:ptr -> structd:D:nw
}
```
```c
#2 while (*left)
#3 left = &((*left)->next) ;
```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structp [label="left|<p>&(*left)"]
structptr [label="<name_ptr> *left|<ptr> &A"];
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
structptr:ptr -> structb:B:nw
structp:p -> structptr:ptr:nw
}
```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structp [label="left|<p>&(*left)"]
structptr [label="<name_ptr> *left|<ptr> &A"];
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
structptr:ptr -> structc:C:nw
structp:p -> structptr:ptr:nw
}
```
```c
#4 *left = right;
```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc,structd,structe,structf}
structp [label="left|<p>&(*left)"]
structptr [label="<name_ptr> *left|<ptr> &A"];
structrptr [label="<name_ptr> *right|<ptr> &D"];
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
structe [label="<E> E|R2"];
structd [label="<D> D|R1"];
structf [label="<F> F|R3"];
structptr:ptr -> structd:D:nw
structp:p -> structptr:ptr:nw
structrptr:ptr -> structd:D:nw
}
```
- quicksort
``` 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;
}
```
```c
#6 node_t *pivot = *list;
#7 int value = pivot->value;
```
宣告一指標變數 pivot 指向 ```*list``` 所指的 node
宣告一整數變數 value 存 pivot 所指 node 內的值
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structp [label="list|<p>&(*list)"]
structptr [label="<name_ptr> *list|<ptr> &A"];
structpivot [label="<name_pivot> *pivot|&A"];
structvalue [label="<name_value> value|L1"];
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
NULL1[label=NULL,shape=plaintext]
structpivot -> structa
structvalue -> NULL1
structptr:ptr -> structa:A:nw
structp:p -> structptr:ptr:nw
}
```
``` c
#8 node_t *p = pivot->next;
```
宣告一指標變數 p 指向 ```pivot->next```
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structl [label="list|<p>&(*list)"]
structptr [label="<name_ptr> *list|<ptr> &A"];
structpivot [label="<name_pivot> *pivot|&A"];
structvalue [label="<name_value> value|L1"];
structp [label="<name_p> *p|&B"]
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
NULL1[label=NULL,shape=plaintext]
structp -> structb
structpivot -> structa
structvalue -> NULL1
structptr:ptr -> structa:A:nw
structl:l -> structptr:ptr:nw
}
```
``` c
#9 pivot->next = NULL;
```
```A->next``` 原本指向 B，將其設為 NULL
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structvalue [label="<name_value> value|L1"];
structl [label="list|<p>&(*list)"]
structptr [label="<name_ptr> *list|<ptr> &A"];
structpivot [label="<name_pivot> *pivot|&A"];
structp [label="<name_p> *p|&B"]
structb [label="<B> B|L2"];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
structp -> structb
structpivot -> structa
structvalue -> NULL1
structptr:ptr -> structa:A:nw
structl:l -> structptr:ptr:nw
structa -> NULL2
}
```
```c
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);
}
```
>宣告 ```*left``` 、 ```*right``` 兩個 pointer 指向 NULL
``` graphviz
digraph structs {
node[shape=record]
left [label="*left|"];
right [label="*right|"];
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
left -> NULL1
right -> NULL2
}
```
>宣告 ```*n``` 指向原本 ```*p``` 所指的 node ，也就是 B
``` graphviz
digraph structs {
node[shape=record]
{rank=same; structa,structb,structc}
structvalue [label="<name_value> value|L1"];
structl [label="list|<p>&(*list)"]
structptr [label="<name_ptr> *list|<ptr> &A"];
structpivot [label="<name_pivot> *pivot|&A"];
structn [label="<name_n> *n|&B", color=red]
structp [label="<name_p> *p|&B"]
structb [label="<B> B|L2",color=red];
structa [label="<A> A|L1"];
structc [label="<C> C|L3"];
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
structn -> structb
structp -> structc
structpivot -> structa
structvalue -> NULL1
structptr:ptr -> structa:A:nw
structl:l -> structptr:ptr:nw
structa -> NULL2
}
```
>比較 ```n->value``` 與 ```value``` （ L2 && L1 ）
若大於，則將 n 添加至 right
``` graphviz
digraph structs {
node[shape=record]
structb [label="<B> B|L2",color=red];
left [label="*left|"];
right [label="*right|&B"];
NULL1[label=NULL,shape=plaintext]
left -> NULL1
right -> structb
}
```
> 若小於，則將 n 添加至 left
``` graphviz
digraph structs {
node[shape=record]
structb [label="<B> B|L2",color=red];
left [label="*left|"];
right [label="*right|&B"];
NULL1[label=NULL,shape=plaintext]
left -> structb
right -> NULL1
}
```
``` c
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
```
>分別對 left list，right list 遞迴執行 quicksort
執行完後會有兩個排序好的串列
然後宣告一個 ```*result```
將 left right pivot 透過 ```list_concat``` 串連起來
:::warning
:information_source: 要記得 ```*pivot``` 還沒被加進去
:::
## 修正 random 並引入其他 Pseudorandom number generator
- 原本測試的程式中，是直接使用 random() 來取得亂數，會發現數字一樣，所以使用 srand 來取用
``` c=
int main(int argc, char **argv) {
size_t count = 20;
srand48(time(NULL));
node_t *list = NULL;
while (count--)
list = list_make_node_t(list, lrand48() % 1024);
list_display(list);
quicksort(&list);
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
## 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
Sign in with Wallet
Connect another wallet