# 2021q1 Homework1 (quiz1)
contributed by < `WayneLin1992` >
###### tags: `linux2021`
:::danger
作業規範要求中英文間用一個半形空白字元區隔，請留意。
征服 Linux 核心這樣的龐然巨物前，我們需要掌握各項細節。
:notes: jserv
:::
## 延伸問題
- [x] 使用 HackMD 筆記，並使用 Graphviz 達到視覺化
- [x] 考慮到 PNRG 修改 random()
- [x] 改寫 quick sort 避免遞迴呼叫
- [ ] 改寫 Linux quick sort 避免遞迴呼叫
- [ ] 思考高效 Linked List sort 並實作其中
## 測驗1
考慮一個單向 linked list ，其結構定義為:
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)，下方程式碼嘗試對該單向 linked list 進行 Quick sort，預期依據遞增順序。
```cpp
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)
LLL;
*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 ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
## 思考過程
### **理解題目**
* 由題目及結構可以知道,這是一個單向的 linked list，並且不是環狀結構，下面為 quick sort，輸出的結果必須由小到大排列。
### **理解 quicksort 函式**
```cpp
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` 名稱可以知道此函式為增加 node，輸入的參數為目前`list`和想要新增的 node `node_t`由`node_t->next = *list;`可以知道新增 node 的位置為`list`的頭部，`*list = node_t;`將 `list` 的指標重新指向首位。
```cpp
node_t->next = *list;
```
:::warning
需要說明 `list_add_node_t` 所新增的節點對應的方向，例如 Linux 核心的 `<linux/list.h>` 就有 `list_add` 和 `list_add_tail`，可見 https://github.com/sysprog21/linux-list/blob/master/include/list.h
工程人員說話應當精準，從而降低日後釐清問題的成本，避免說「增加 node」這樣含糊的話。
:notes: jserv
:::
```graphviz
digraph list_add_node_t {
rankdir=LR;
nodespe = 1.0
node[shape = box]
list[color = blue]
edge[color = blue]
list -> node1
edge[color = black]
node_t-> node1;
node1->node2;
}
```
```
*list = node_t;
```
```graphviz
digraph list_add_node_t {
rankdir=LR;
nodespe = 1.0
node[shape = box]
list[color = blue]
edge[color = blue]
list -> node_t;
edge[color = black]
node_t-> node1;
node1->node2;
}
```
```cpp
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
* 由`list_concat`名稱可以知道此函式為連接兩個`node_t`參數為兩個`node_t`分別為 left 和 right 。
* `while(*left)`代表只要`*left`不是`NULL`就會不斷執行`while`因此可以推測出`LLL`應該是要不斷接續`next`直到尾部。
* `LLL=>left = &((*left)->next);`
會以`(*left)`表示是因為->的percedence比*及&大所以需要加括號，同理要`(*left)->next`的address一樣需要括號來表示`&((*left)->next)`，最後將`left`接上`right`。
```cpp
while (*left)
left = &((*left)->next);
```
```graphviz
digraph list_concat{
rankdir=LR;
nodespe = 1.0
node[shape = box]
left[color = blue]
edge[color = blue]
left -> node1;
edge[color = black]
node1-> node2;
node2->node3;
node3->NULL
}
```
```graphviz
digraph list_concat{
rankdir=LR;
nodespe = 1.0
node[shape = box]
edge[color = black]
node1-> node2;
node2->node3;
node3->NULL
left[color = blue]
edge[color = blue]
left->NULL;
}
```
```cpp
*left = right;
```
```graphviz
digraph list_concat{
rankdir=LR;
nodespe = 1.0
node[shape = box]
edge[color = black]
node1-> node2;
node2->node3;
node3->NULL
left[color = blue]
edge[color = blue]
left->NULL;
right[color = blue]
edge[color = blue]
right -> node_1;
edge[color = black]
node_1-> node_2;
node_2->node_3;
}
```
變成
```graphviz
digraph list_concat{
rankdir=LR;
nodespe = 1.0
node[shape = box]
edge[color = black]
node1-> node2;
node2->node3;
node3->node_1;
left[color = blue]
edge[color = blue]
left->node_1;
right[color = blue]
right -> node_1;
edge[color = black]
node_1-> node_2;
node_2->node_3;
}
```
```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 ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
* 由quicksort名稱可以知道這是實做 quick sort 的函式，參數為`node_t **list`一開始先選定一個`pivot`當中間值，並將`list`中的`value`與`pivot`的`value`比較並把結果放入`left`和`right`中，因此可以知道`list_add_node_t(n->value > value ? AAA : BBB, n);`當`n->value > vale`時就應該放入`right`當中，反之經應該放入`left`當中。
* `AAA => &right`
* `BBB => &left`
之後就使用遞迴的方式處理`quicksort(&left)`和`quicksort(&right)`直到`list`為`NULL`每一次遞迴都會將其`right`和`right`與`result`連接，並注意`pivot`必須在中間所以只以知道`CCC`
* `CCC=>list_concat(&result, pivot);list_concat(&result, right);`
執行環境介紹
```shell
* Distributor ID: Ubuntu
* Description: Ubuntu 20.04.1 LTS
* Release: 20.04
* Codename: focal
```
LinkedList_quicksort.h
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
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;
}
```
由`main`部分可以知道，缺少了`list_make_node_t` `list_free` 我將其增加後
LinkedList_quicksort.c
```cpp
#include "LinkedList_quicksort.h"
static bool list_is_ordered(node_t *list) {
bool first = true;
int value;
while (list) {
if (first) {
value = list->value;
first = false;
} else {
if (list->value < value)
return false;
value = list->value;
}
list = list->next;
}
return true;
}
static void list_display(node_t *list) {
printf("%s IN ORDER : ", list_is_ordered(list) ? " " : "NOT");
while (list) {
printf("%d ", list->value);
list = list->next;
}
printf("\n");
}
/*
int random(void){
int a;
a = rand();
return a;
}
*/
static void list_free(node_t **list){
node_t *ptr = *list;
while(*list){
ptr = (*list)->next;
free(*list);
*list = ptr;
}
}
static inline node_t* list_make_node_t(node_t *list, int num){
node_t *p = malloc(sizeof(node_t));
if(p==NULL){
return list;
}else{
p->value = num;
p->next = NULL;
list_add_node_t(&list,p);
}
return list;
}
int main(int argc, char **argv) {
size_t count = 20;
node_t *list = NULL;
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;
}
```
得到的結果:
```
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
```
使用 valgrind memcheck 確定記憶體空間是否有成功釋放出來，結果如下
```
==7547== Memcheck, a memory error detector
==7547== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7547== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==7547== Command: ./LinkedList_quicksort
==7547==
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
==7547==
==7547== HEAP SUMMARY:
==7547== in use at exit: 0 bytes in 0 blocks
==7547== total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated
==7547==
==7547== All heap blocks were freed -- no leaks are possible
==7547==
==7547== For lists of detected and suppressed errors, rerun with: -s
==7547== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
有成功釋放記憶體空間。
## 實作`random()`
我們將程式重複執行後發現 ramdom 數都相同。
```shell
$ ./LinkedList_quicksort
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
$./LinkedList_quicksort
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
$ ./LinkedList_quicksort
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
```
我們可以透過 `include <time.h>` 使用 `time()` 來影響 PRNG's seed 用`srandom(time(NULL))`再使`ramdom()`可以產生出隨機數，其結果如下
```
$ ./LinkedList_quicksort
NOT IN ORDER : 987 432 910 798 474 571 643 396 105 287 715 680 843 689 941 292 417 464 81 965
IN ORDER : 81 105 287 292 396 417 432 464 474 571 643 680 689 715 798 843 910 941 965 987
$ ./LinkedList_quicksort
NOT IN ORDER : 480 613 592 736 1 837 870 43 176 271 897 762 19 875 320 577 996 27 305 708
IN ORDER : 1 19 27 43 176 271 305 320 480 577 592 613 708 736 762 837 870 875 897 996
$ ./LinkedList_quicksort
NOT IN ORDER : 181 391 449 556 964 420 396 592 659 896 877 599 485 795 795 589 386 709 652 297
IN ORDER : 181 297 386 391 396 420 449 485 556 589 592 599 652 659 709 795 795 877 896 964
```
## 改寫 quick sort non recursive
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 後可以知道作者實作出非遞迴的 quick sort 作者主要是在 stack 資料結構上進行，我們這邊是使用 linked list 進行，所以要進行修改，所以我可以將`value`存入 stack 中，並排列後再將 stack 依序存入 linked list value 中
non_recursive_quicksort
```cpp
void quicksort_nonrecursive(node_t **list){
node_t *ptr = *list;
int arr[20] ;
int j = 0;
while(ptr){
arr[j++] = ptr->value;
ptr = ptr->next;
}
int element = 20;
int piv, beg[element], end[element], i=0, L, R ;
beg[0]=0; end[0]=element;
while (i>=0) {
L=beg[i]; R=end[i]-1;
if (L<R) {
piv=arr[L]; if (i==element-1) return ;
while (L<R) {
while (arr[R]>=piv && L<R)
R--;
if (L<R)
arr[L++]=arr[R];
while (arr[L]<=piv && L<R)
L++;
if (L<R)
arr[R--]=arr[L]; }
arr[L]=piv;
beg[i+1]=L+1;
end[i+1]=end[i];
end[i++]=L;
}
else {
i--; }
}
node_t*ptr1 = *list;
i = 0;
while(ptr1){
ptr1->value = arr[i++];
ptr1 = ptr1->next;
}
}
```
執行結果下
```
NOT IN ORDER : 223 908 855 946 379 612 456 262 707 374 225 734 68 123 279 442 666 64 928 9
IN ORDER : 9 64 68 123 223 225 262 279 374 379 442 456 612 666 707 734 855 908 928 946
```
Sign in with Wallet
Connect another wallet