# 2021q1 Homework1 (quiz1)
contributed by < `chiehen` >
###### tags: `linux2021`
## 作業要求
- [x] 解釋上述程式運作原理，搭配 Graphviz
- [x] 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
- [x] 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
- [ ] 請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- [ ] 研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
## 解釋程式
程式為單向 linked-list 的 quicksort 實做
主要跟 quick sort 有關的函式有以下:
* `list_add_node_t`: 將一個 node 加入 list 開頭
* `list_concat`: 將兩個 list 以頭尾相接的方式連接
* `quicksor`: 執行 quicksort 演算法
#### list_concat
```cpp=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
```graphviz
digraph structs {
node[shape=record];
struct0 [label="<ele>1|<next>next"]
struct1 [label="<ele>5|<next>next"]
struct2 [label="<ele>6|<next>next"]
node[shape=box];
struct3 [label= "left"];
struct4 [label= "right"];
struct5 [label= "&result"];
rankdir=LR;
struct5 -> struct0[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0:next -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct4 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct5[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
第一次迴圈完:
```graphviz
digraph structs {
node[shape=record];
struct0 [label="<ele>1|<next>next"]
struct1 [label="<ele>5|<next>next"]
struct2 [label="<ele>6|<next>next"]
node[shape=box];
struct3 [label= "left"];
struct4 [label= "right"];
struct5 [label= "&result"];
struct6 [label = "&next1"]
rankdir=LR;
struct5 -> struct0[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0:next -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct4 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct6[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct6 -> struct0:next[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
第二次(全部)迴圈完:
```graphviz
digraph structs {
node[shape=record];
struct0 [label="<ele>1|<next>next"]
struct1 [label="<ele>5|<next>next"]
struct2 [label="<ele>6|<next>next"]
node[shape=box];
struct3 [label= "left"];
struct4 [label= "right"];
struct5 [label= "&result"];
struct6 [label = "&next2"]
rankdir=LR;
struct5 -> struct0[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0:next -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct4 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct6[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct6 -> struct1:next[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
此時 left 中為指向元素(value=5)的next的指標, 透過此指標將 next 中的值改為指向 right 所指向的元素:
```c=4
*left = right;
```
```graphviz
digraph structs {
node[shape=record];
struct0 [label="<ele>1|<next>next"]
struct1 [label="<ele>5|<next>next"]
struct2 [label="<ele>6|<next>next"]
node[shape=box];
struct3 [label= "left"];
struct4 [label= "right"];
struct5 [label= "&result"];
struct6 [label = "&next2"]
rankdir=LR;
struct5 -> struct0[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0:next -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct4 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct6[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct6 -> struct1:next[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1:next -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
`result` 即為指向連接後 list 開頭的指標
#### quicksort
```cpp=
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:
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct4 [label= "NULL"];
{
rank="same";
struct0 -> struct1
}
struct1 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct2 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct4[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
到第 10 行結束時將如下:
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
struct8 [label="<value>value|<data>5"]
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct4 [label= "NULL"];
struct5 [label= "pivot"];
struct6 [label= "p"];
struct7 [label = "NULL"];
{
rank="same";
struct6 -> struct2
}
struct0 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct5 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1 -> struct7[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct2 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct4[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
迴圈中將大於 value 的 node 分到 right, 小於的分到 left,
經過第一次迴圈(line 11 - 15):
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct4 [label= "NULL"];
struct5 [label= "pivot"];
struct6 [label= "p"];
struct7 [label = "NULL"];
struct9 [label = "n"];
struct10 [label = "left"];
struct11 [label = "NULL"];
{
rank="same";
struct9 -> struct2
}
{
rank="same";
struct6 -> struct3
}
struct2 -> struct11[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct10 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct5 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1 -> struct7[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct4[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
結束迴圈:
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct4 [label= "NULL"];
struct5 [label= "pivot"];
struct6 [label= "p"];
struct7 [label = "NULL"];
struct9 [label = "n"];
struct10 [label = "left"];
struct11 [label = "NULL"];
struct12 [label = "right"]
{
rank="same";
struct9 -> struct3
}
{
rank="same";
struct6 -> struct4
}
struct12 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct2 -> struct11[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct10 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct0 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct5 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1 -> struct7[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct3 -> struct4[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
接著分別排序 right, left
第 23 行前:
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct4 [label= "right"]
struct5 [label= "result"]
{
rank="same";
struct0 -> struct1
}
{
rank="same";
struct5 -> struct2
}
struct2 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct4 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
第 23 行後:
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct5 [label= "result"]
{
rank="same";
struct0 -> struct1
}
{
rank="same";
struct5 -> struct2
}
struct2 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
第 24 行後:
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
struct0 [label= "*list"];
struct1 [label= "5"];
struct2 [label= "1"];
struct3 [label= "6"];
struct5 [label= "result"]
{
rank="same";
struct5 -> struct2
}
struct0 -> struct2[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct2 -> struct1[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
struct1 -> struct3[arrowhead=vee, dir=LR, tailclip=true, arrowsize=1];
}
```
`list` 變為指向排序完 list 的 pointer to pointer
### 補完程式
* list_make_node_t: 建立一個 value 為 `val` 的 node , 並加在 list 前端
* list_free: 釋放 list 所配置的記憶體
```c
static node_t *list_make_node_t(node_t *list, int val) {
node_t *new = malloc(sizeof(node_t));
if (!new)
return list;
new->value = val;
new->next = list;
return new;
}
static void list_free(node_t **p) {
while (*p) {
node_t *curr = *p;
*p = curr->next;
free(curr);
}
}
```
### Random
原先 random() 將 回傳 一個介於 0 to RAND_MAX 的整數, 而根據 [維基百科](https://en.wikipedia.org/wiki/Pseudorandom_number_generator):
>The Pseudorandom number generator(PRNG)-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)
數列將被初始值(initial value)決定, 根據 Linux Programmer's Manual:
> The srandom() function sets its argument as the seed for a new sequence
of pseudo-random integers to be returned by random(). These sequences
are repeatable by calling srandom() with the same seed value. If no
seed value is provided, the random() function is automatically seeded
with a value of 1.
因此呼叫 srandom 時設定初始值, 而為了保證初始值不同, 則將現今時間作為初始值:
```cpp
srandom(time(NULL));
```
## 修改 quick sort 程式碼 避免遞迴
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 實做 non-resursive quick sort。
因為在文章中的資料是以 array 的方式儲存, 如果是 linked-list 在實做上需要 doubly linked list 才有辦法實現, 因此參考[課程討論區](https://www.facebook.com/groups/system.software2021/permalink/857571485085909/)以 stack 的方式實做 non-resursive quick sort。
定義 stack 結構:
```c
typedef struct __snode {
node_t *value; // 儲存 sorted linked-list
struct __snode *next; // 指向下一個 stack 元素
} snode_t;
```
兩個輔助函式對 stack 操作
* stack_push: 將元素推入 stack
* stack_pop: 將元素彈出 stack, 並回傳儲存的 list 指標
```c
static void stack_push(snode_t **top, node_t *list) {
snode_t *new = malloc(sizeof(snode_t));
if (!new)
return;
new->value = list;
new->next = *top;
*top = new;
}
static node_t *stack_pop(snode_t **top) {
snode_t *curr = *top;
if (curr) {
node_t *list = curr->value;
*top = curr->next;
free(curr);
return list;
}
return NULL;
}
```
依 pivot 調整數列的部份, 沿用原先程式的方法, 分為 `right`, `left` 兩個 list。 但在調整完後, 將 `right`, `pivot`, `left`依序推入 stack:
```c
if(left) stack_push(&stack, left);
stack_push(&stack, pivot);
if(right) stack_push(&stack, right);
```
持續將 stack 最頂端的 list 進行 Quick Sort, 如果最頂端的 list 只有一個元素, 則將此元素加到 `result` 前端, 當 stack 為空時, 代表 sorting 完成:
```c
while (stack) {
node_t *pivot = stack_pop(&stack);
int value = pivot->value;
node_t *p = pivot->next;
if (!p) {
list_add_node_t(&result, pivot);
} else {
// 進行 quick sort
.....
}
}
*list = result;
```
完整 non-recursive quick sort:
```cpp
void optquicksort(node_t **list) {
snode_t *stack = NULL;
node_t *result = NULL;
stack_push(&stack, *list);
while (stack) {
node_t *pivot = stack_pop(&stack);
int value = pivot->value;
node_t *p = pivot->next;
if (!p) {
list_add_node_t(&result, pivot);
} else {
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);
}
if(left) stack_push(&stack, left);
stack_push(&stack, pivot);
if(right) stack_push(&stack, right);
}
}
*list = result;
}
```
:::warning
如何改進上述程式碼？
:notes: jserv
:::
## 改寫 linux-list 的 quick sort 範例
## 研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms
Sign in with Wallet
Connect another wallet