# 2021q1 Homework1 (quiz1)
contributed by < shanlee870502 >
###### tags: `linux2021`
> [第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
### QuickSort 運作原理:
使用 Divide and Conquer 的概念，每次迭帶選一個 pivot，比 pivot 大的放右邊，比 pivot 小的放左邊，而左、右各成一新數列，繼續迭帶，直到數列無法分割，即完成排序。
* code:
```c=
static inline void list_add_node_t(node_t **list, node_t *node_t){
node_t->next = *list;
*list - node_t;
}
static inline void list_concat(node_t **left, node_t *right){
while(*left){
left = &((*left)->next);
}
*left = right;
}
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;
}
```
* 圖解:
進入while迴圈前:
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
n1 [label="{ <data> 2 | <ref> }"];
n2 [label="{ <data> 5 | <ref> }"];
n3 [label="{ <data> 3 | <ref> }"];
n4 [label="{ <data> 6 | <ref> }"];
n5 [label="{ <data> 4 | <ref> }"];
n6 [label="{ <data> 1 | <ref> }"];
NULL_1[label=NULL,shape=plaintext];
NULL_2[label=NULL,shape=plaintext];
NULL_3[label=NULL,shape=plaintext];
NULL_4[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
pivot[shape="none", label = "pivot", fontcolor="blue"];
p[shape="none", label = "p", fontcolor="blue"];
}
//link operation
{
n1:ref:c -> NULL_1:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n2:ref:c -> n3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n3:ref:c -> n4:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n4:ref:c -> n5:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n5:ref:c -> n6:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n6:ref:c -> NULL_2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
pivot->n1;
p->n2;
left->NULL_3;
right->NULL_4;
// right->r1
// head->l1
// left->right
// ptr->l3
}
}
```
---
whlie迴圈(比pivot值小的放左邊，大的放右):
```
node_t *n = p
p=p->next
```
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
n1 [label="{ <data> 2 | <ref> }"];
n2 [label="{ <data> 5 | <ref> }"];
n3 [label="{ <data> 3 | <ref> }"];
n4 [label="{ <data> 6 | <ref> }"];
n5 [label="{ <data> 4 | <ref> }"];
n6 [label="{ <data> 1 | <ref> }"];
NULL_1[label=NULL,shape=plaintext];
NULL_2[label=NULL,shape=plaintext];
NULL_3[label=NULL,shape=plaintext];
NULL_4[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
pivot[shape="none", label = "pivot", fontcolor="blue"];
p[shape="none", label = "p", fontcolor="blue"];
n[shape="none", label = "n", fontcolor="blue"];
}
//link operation
{
n1:ref:c -> NULL_1:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n2:ref:c -> n3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n3:ref:c -> n4:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n4:ref:c -> n5:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n5:ref:c -> n6:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n6:ref:c -> NULL_2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
pivot->n1;
p->n3;
n->n2;
left->NULL_3;
right->NULL_4;
// right->r1
// head->l1
// left->right
// ptr->l3
}
}
```
```list_add_node_t(n->value > value ? &right: &left, n);```
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
n1 [label="{ <data> 2 | <ref> }"];
n2 [label="{ <data> 5 | <ref> }"];
n3 [label="{ <data> 3 | <ref> }"];
n4 [label="{ <data> 6 | <ref> }"];
n5 [label="{ <data> 4 | <ref> }"];
n6 [label="{ <data> 1 | <ref> }"];
NULL_1[label=NULL,shape=plaintext];
NULL_2[label=NULL,shape=plaintext];
NULL_3[label=NULL,shape=plaintext];
NULL_4[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
pivot[shape="none", label = "pivot", fontcolor="blue"];
p[shape="none", label = "p", fontcolor="blue"];
n[shape="none", label = "n", fontcolor="blue"];
}
//link operation
{
n1:ref:c -> NULL_1:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n3:ref:c -> n4:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n4:ref:c -> n5:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n5:ref:c -> n6:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
n6:ref:c -> NULL_2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
pivot->n1;
p->n3;
n->n2;
left->NULL_3;
n2->NULL_4;
right->n2;
}
{
rank="same"
}
}
```
跳出while迴圈之後，應會分割為兩 sublist : 4->6->3->5 以及 1 (分別為比 pivot value 大的以及比 pivot value 小的兩串列)，之後再遞迴兩個sublist作上述圖解的分割，最後用 ```list_concat```把 sublist 接起來。
### 函式
#### list_add_node_t
* 將一個 ```node_t``` 節點加在 ```*list``` 前方，且讓 ```*list```指向串列最前端(也就是 ```node_t``` )
```c=
static_inline void list_add_node_t(node_t **list, node_t *node_t){
node_t -> next = *list;
*list = node_t;
}
```
* 圖解：
假設傳入 ```list_add_node_t```之狀態如下(藍色:指標，紅色:指標的指標):
``` graphviz
digraph foo {
rankdir = LR;
node[shape=record];
list[shape="none", label = "list", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
node_t [label="{ <data> node_t | <ref> }"];
a [label="{ <data> 4 | <ref> }"];
b [label="{ <data> 5 | <ref> }"];
c [label="{ <data> 6 | <ref> }"];
NULL[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
c:ref:c -> NULL:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
node_t:ref:c -> NULL2:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
ptr->node_t
list-> head
head-> a
}
```
```node_t -> next = *list```
``` graphviz
digraph foo {
rankdir = LR;
node[shape=record];
list[shape="none", label = "list", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
node_t [label="{ <data> node_t | <ref> }"];
a [label="{ <data> 4 | <ref> }"];
b [label="{ <data> 5 | <ref> }"];
c [label="{ <data> 6 | <ref> }"];
NULL[label=NULL,shape=plaintext];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
c:ref:c -> NULL:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
ptr->node_t
node_t -> a
list-> head
head->a
}
```
```*list = node_t```
``` graphviz
digraph foo {
rankdir = LR;
node[shape=record];
list[shape="none", label = "list", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
node_t [label="{ <data> node_t | <ref> }"];
a [label="{ <data> 4 | <ref> }"];
b [label="{ <data> 5 | <ref> }"];
c [label="{ <data> 6 | <ref> }"];
NULL[label=NULL,shape=plaintext];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
c:ref:c -> NULL:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
ptr->node_t
node_t -> a
list-> ptr
head->a
}
```
#### list_concat
* 連接兩條 list，由 while 迴圈找到 ```left``` 串列的最尾端( NULL )，再將其指向 ```right```的開頭
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);;
*left = right;
}
```
* 圖解:
假設傳入 ```list_concat```之狀態如下:
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
r1 [label="{ <data> 1 | <ref> }"];
r2 [label="{ <data> 2 | <ref> }"];
r3 [label="{ <data> 3 | <ref> }"];
l1 [label="{ <data> 4 | <ref> }"];
l2 [label="{ <data> 5 | <ref> }"];
l3 [label="{ <data> 6 | <ref> }"];
NULL_l[label=NULL,shape=plaintext];
NULL_r[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
ptr_next[shape="none", label = "ptr->next", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
}
//link operation
{
l1:ref:c -> l2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l2:ref:c -> l3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l3:ref:c -> NULL_l:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r1:ref:c -> r2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r2:ref:c -> r3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r3:ref:c -> NULL_r:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
right->r1
head->l1
left->head
ptr->l3
ptr_next->NULL_l
}
}
```
while迴圈:
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
r1 [label="{ <data> 1 | <ref> }"];
r2 [label="{ <data> 2 | <ref> }"];
r3 [label="{ <data> 3 | <ref> }"];
l1 [label="{ <data> 4 | <ref> }"];
l2 [label="{ <data> 5 | <ref> }"];
l3 [label="{ <data> 6 | <ref> }"];
NULL_l[label=NULL,shape=plaintext];
NULL_r[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
ptr_next[shape="none", label = "ptr->next", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
}
//link operation
{
l1:ref:c -> l2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l2:ref:c -> l3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l3:ref:c -> NULL_l:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r1:ref:c -> r2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r2:ref:c -> r3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r3:ref:c -> NULL_r:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
right->r1
head->l1
left->ptr_next
ptr->l3
ptr_next->NULL_l
}
}
```
```*left = right;```
```graphviz
digraph foo {
rankdir = LR;
node[shape=record];
//node declaration
{
r1 [label="{ <data> 1 | <ref> }"];
r2 [label="{ <data> 2 | <ref> }"];
r3 [label="{ <data> 3 | <ref> }"];
l1 [label="{ <data> 4 | <ref> }"];
l2 [label="{ <data> 5 | <ref> }"];
l3 [label="{ <data> 6 | <ref> }"];
NULL_r[label=NULL,shape=plaintext];
}
//pointer declaration (including pointer to pointer)
{
left[shape="none", label = "left", fontcolor="red"];
head[shape="none", label = "head", fontcolor="blue"];
ptr[shape="none", label = "ptr", fontcolor="blue"];
right[shape="none", label = "right", fontcolor="blue"];
}
//link operation
{
l1:ref:c -> l2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l2:ref:c -> l3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
l3:ref:c -> r1:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r1:ref:c -> r2:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r2:ref:c -> r3:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
r3:ref:c -> NULL_r:data [arrowhead=vee, arrowtail=dot, dir=both , tailclip=false]
}
//pointer operation
{
right->r1
head->l1
left->right
ptr->l3
}
}
```
### random 修正
* random 函式產生亂數非亂數!(多次執行發現仍相同)。
* 使用srand()產生亂數種子
* 程式片段說明(改變第6行):
```c=
int main(int argc, char **argv) {
size_t count = 20;
node_t *list = NULL;
srand((unsigned) time(&t));
while (count--)
list = list_make_node_t(list, random() % 1024);
list_display(list);
quicksort(&list);
list_display(list);
if (!list_is_ordered(list))
return EXIT_FAILURE;
list_free(&list);
return EXIT_SUCCESS;
}
```
### 避免使用遞迴呼叫的QuickSort
> [Optimized QuickSort](https://alienryderflex.com/quicksort/)
* 概念:
* code:
//TODO
Sign in with Wallet
Connect another wallet