# 2021q1 Homework1 (quiz1)
contributed by < `mahavishnuj` >
:::danger
留意共筆書寫規範：中英文間用一個半形空白區隔
:notes: jserv
:::
## 測驗題目
### 測驗 1
考慮一個單向 linked list，其結構定義為:
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)，下方程式碼嘗試對該單向 linked list 進行 Quick sort，預期依據遞增順序。
```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)
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;
}
```
## ＱuickSort 原理
使用 `Divided and Conquer` 將原本的大問題切分成若干個子問題，並逐一解答，最終彙整成完整答案。以 `quicksort` 而言，將數列中一值定為 `pivot` 將數量從頭尾循序逼近，比 `pivot` 數值小的放置左邊，大的放置右邊，直到頭尾交會處與`pivot`如此結果出來的兩邊數列迭代執行下去。
#### list_add_node_t
```cpp
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
function吃的是一個`pointer to pointer to node`跟`pointer to node`
- 假設一開始初始狀態為下
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
list[shape=plaintext,fontcolor=blue]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
list->head->A
node_t->D
}
A->B->C->NULL1
D->NULL2
}
```
經過`node_t->next = *list`將 `node_t` 所指向的那個節點的 `next` 指到 `list` 所指的那個 `head` 所指的節點
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
list[shape=plaintext,fontcolor=blue]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
list->head->A
node_t->D->A
}
A->B->C->NULL1
}
```
最後經過`*list = node_t;`把`*list`指導新加入的node上面
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
list[shape=plaintext,fontcolor=blue]
node_t[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
list->node_t->D
}
head->A
D->A->B->C->NULL1
}
```
再來看看另一個function
### list_concat()
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
可以看的出來，function的目的是想要將`*left`所指向的`list`所指向的兩個list串起來，我們已經知道`left`是一個`Pointer to a Pointer to node_t`因此我們要做的是循序找到最後一個節點並將他與right連起來
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
E[label=4]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left->head->A
right->D
}
A->B->C->NULL1
D->E->NULL2
}
```
- 最終目標是要將`left`停在最後一個節點上端最後一個尾巴節點所指的地方，while loop才會結束，並且將位置assign給`right`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
E[label=4]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left->NULL1
right->D
}
A->B->C->NULL1
D->E->NULL2
head->A
}
```
而迭代的過程是不斷的assigh新的value給`left`前面我們提到`left`是一個`Pointer to Pointer to node_t`因此他儲存的內容應該是指向該節點指摽的address,以head來說的話內容應該是儲存`&head`,因此可以以`&(*left)`來表示,因此LLL為`left = &((*left)->next)`直到指向圖中NULL的位置
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=5]
B[label=6]
C[label=8]
D[label=1]
E[label=4]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
left->right
right->D
}
A->B->C->D->E->NULL2
head->A
}
```
再來我們可以進入到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 ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
其中的方法是將`pivot`指向第一個元素
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
pivot[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=2]
B[label=3]
C[label=1]
D[label=4]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
pivot->head->A
}
A->B->C->D->NULL1
}
```
再來把`pivot`所指向的點獨立出來
```graphviz
digraph graphname{
node[shape=box]
p[shape=plaintext,fontcolor=red]
pivot[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=2]
B[label=3]
C[label=1]
D[label=4]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->A
p->B
}
B->C->D->NULL1
A->NULL2
}
```
再來後面的迴圈，就是把`pivot`的值取出來,然後在繼續看剩下的node,把比`pivot`小的地方放在`*left`的list裡面，價值比`pivot`大的放在`*right`裡面
```c=
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);
}
```
再來看到重點的function,前面我的知道`list_add_node_t()`的這個function所傳入的必須是一個`Pointer to Pointer`因此AAA所傳入的必須是所指的點的address因此應該是&(ptr)
```c=
list_add_node_t(n->value > value ? &right : &left, n);
```
最後我們看到的部分,除了對左右的兩個數列在進行quicksort之外,還要把結果鏈結起來,首先給予一個`NULL Pointer Result`再把left加在list的最右邊，因此照順序來說應該是先加入`left`再來`pivot`最後再加入`right`因此CCC的部分應該為
```c=
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
//CCC;
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=orange]
result[shape=plaintext,fontcolor=purple]
rankdir=LR
{
rankdir = LR
A[label=1]
B[label=2]
C[label=3]
D[label=4]
E[label=5]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
NULL3[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->C
left->A
right->D
result->NULL3
}
A->B->NULL1
D->E->NULL2
}
```
依序慢慢加入後變成這個型態
```graphviz
digraph graphname{
node[shape=box]
left[shape=plaintext,fontcolor=blue]
right[shape=plaintext,fontcolor=orange]
result[shape=plaintext,fontcolor=purple]
rankdir=LR
{
rankdir = LR
A[label=1]
B[label=2]
C[label=3]
D[label=4]
E[label=5]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
left->D
right->D
result->D
}
A->B->C->D->E->NULL1
}
```
## Random Function Issiue
- 根據 [random(3)](https://man7.org/linux/man-pages/man3/random.3.html)
> The random() function uses a nonlinear additive feedback random number generator employing a default table of size 31 long integers to return successive pseudo-random numbers in the range from 0 to RAND_MAX. The period of this random number generator is very large, approximately 16 * ((2^31) - 1).
`Random()`透過一個seed來決定產生變數的sequence,由wiki上面所說 [PRNG-generated sequence](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)並不真的是完全亂數產生數字,而是透過ㄧ開始所給定Initial Value做為Seed來決定產生出來數字的順序。
比較直觀的解決方法就是將Seed設定成某個隨機的數字，看到說明是2的31次方,我的想法是如果是以記憶體的address做為一個seed,就算是一個NULL的值記憶體還是會宣告一個位址來儲存他，如果再隨機記憶體分配的狀況下可能會分配到不同的記憶體位置，這樣的方法可能就可以增加產生出來數字的複雜度
```graphviz
digraph g {
graph [
rankdir = "LR"
];
node [
fontsize = "16"
shape = "ellipse"
];
edge [
];
"node0" [
label = "<f0> SEED| <f1>"
shape = "record"
];
"node1" [
label = "<f0> 0xf7fc4380| <f1> | <f2> |"
shape = "record"
];
"node0":f0 -> "node1":f0 [
id = 0
];
}
```
因此用像是這樣的function來增加隨機數字的複雜性
```c=
srand(time(NULL))
```
### Quick Sort改寫
Sign in with Wallet
Connect another wallet