# 2021q1 Homework1 (quiz1)
contributed by < `AmyLin0210` >
###### tags: `2021q1 Linux`
> [2021q1 第一周測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
## 解釋程式運作原理
### 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;
}
```
將 list 接到 node_t 的後方，並將 node_t 變成新的 list head
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
node1[label= node_t];
{
head[label= "head" shape= plaintext, fontcolor=red]
list0[label= A];
list1[label= B];
list2[label= C];
}
{
rank="same";
head->list0;
}
node1->list0->list1->list2
}
```
### list_concat
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
在第二及第三行的迴圈中做的事情為，找到 left 最後方 node 的 next，並使 *left 指向那個位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
head[label= "*left" shape= plaintext, fontcolor=red];
null[label= "NULL" shape= plaintext];
l1[label= "L1"];
l2[label= "L2"];
l3[label= "L3"];
{
rank="same";
head->null;
}
l1->l2->l3->null;
}
```
在第四行的地方，將 *left 指向 right，使得 left 與 right 連接起
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
head[label= "*left" shape= plaintext, fontcolor=red];
l1[label= "L1"];
l2[label= "L2"];
l3[label= "L3"];
r1[label= "R1"];
r2[label= "R2"];
{
rank="same";
head->r1;
}
l1->l2->l3->r1->r2;
}
```
當遇到 *left 指向 NULL 的狀況時，指標的指標優勢便體現出來
- 當 *left 指向 NULL 時，會直接跳出迴圈，故指標位置示意圖如下
```graphviz
digraph structs {
rankdir=LR;
head[label= "*left" shape= plaintext, fontcolor=red];
null[label= "NULL" shape= plaintext];
{
rank="same";
head->null;
}
}
```
- 在 `*left = right` 中直接將 *left 指向 right
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
head[label= "*left" shape= plaintext, fontcolor=red];
{
rank="same";
head->R1;
}
R1->R2
}
```
### 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;
}
```
使用 quick sort 會取出一個作為比較的 pivot 值，
在這段程式碼中，將 list 的第一個 node 做為 pivot 取下，
並以他的 value 當接下來的比較基準。
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
A[label= "A"]
B[label= "B"]
C[label= "C"]
pivot[label= "pivot"];
value[label= "value" shape= plaintext fontcolor="blue"];
p[label="p" shape= plaintext fontcolor="red"];
null[label= "NULL" shape= plaintext];
{
rank="same";
value->pivot;
}
{
rank="same";
p->A;
}
pivot->null;
A->B->C
}
```
在 `list_add_node_t(n->value > value ? AAA : BBB, n)` 中，
- 如果 n 的值比較大，將它與 right 進行連接，
- 如果 n 的值比較小，將它與 left 進行連接。
```flow
right=>operation: 連接 right
left=>operation: 連接 left
cond=>condition: n->value > value
cond(yes)->right
cond(no)->left
```
反覆對 right 與 left 這兩條 linked list 做 quick sort，
全部排序完後做將左右兩條串連起來。
- `list_concat(&result, left)`
由 list_concat 的函式介紹中，可以發現若第一個參數的值指向 NULL，透過函式執行後，會直接將第一個函式的值指向第二個參數的位置。
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
result[label= "result" shape= plaintext fontcolor="red"]
{
rank="same";
result->L1;
}
L1->L2->L3;
}
```
- `list_concat(&result, pivot)`
將原先的 left 與 pivot 連起
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
result[label= "result" shape= plaintext fontcolor="red"]
{
rank="same";
result->L1;
}
L1->L2->L3->pivot;
}
```
- `list_concat(&result, right)`
最後再將 right 連上
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
result[label= "result" shape= plaintext fontcolor="red"]
{
rank="same";
result->L1;
}
L1->L2->L3->pivot->R1->R2->R3;
}
```
### 測試程式中 random 結果相仿問題
> :::warning
> 有什麼證據可說明「rand() 函式使用的是亂數表」呢？工程人員說話要精準確實。
> :notes: jserv
> :::
>> The rand function computes a sequence of pseudo-random integers in the range 0 to
RAND_MAX.
> 以上節錄自 [ISO/IEC 9899 (a.k.a C99 Standard)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 中的 7.20.2.1，由此可知 rand 函式使用了 pseudo-random integers
若按照題目給的程式碼修改編譯執行，由於 rand() 函式使用的是 pseudo-random integers，在程式執行時沒有給定不同的亂數種子，因此導致執行後結果相仿。
> NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
在這裡我的改進方式是，加入亂數種子 `srand((unsigned int)time(NULL))`。
由於 `time(NULL)` 會回傳目前時間距離 (00:00:00 UTC, January 1, 1970) 這個時間點的秒數，所以使得程式執行後的結果不同。
## 非遞迴方式
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)。
### doubly-linked list
由於此連結中使用到儲存數列的資料型態為陣列，會有從陣列最後方反過來尋找比對的狀況，所以我改變我的資料型態為 doubly-linked list。
:::danger
變更資料結構會造成不相容 (incompatibility)，你需要考慮到這部分的衝擊。
:notes: jserv
:::
```cpp
typedef struct __node {
int value;
struct __node *next;
struct __node *prev;
} node_t;
```
我的 quick sort 程式碼：
```cpp
void quicksort(node_t *head, node_t *tail, int length)
{
if (!head)
return;
node_t *beg[length], *end[length], *L, *R;
int i=0, piv;
beg[0] = head;
end[0] = tail;
while (i >= 0) {
L = beg[i];
R = end[i];
if( L != R && L && R) {
piv = beg[i]->value;
while (L != R) {
while ( R->value >= piv && L != R )
R = R->prev;
if (L != R) {
L->value = R->value;
L = L->next;
}
while ( L->value <= piv && L != R )
L = L->next;
if (L != R) {
R->value = L->value;
R->prev;
}
}
L->value = piv;
beg[i+1] = L->next;
end[i+1] = end[i];
end[i++] = L;
} else {
i--;
}
}
}
```
傳入的三個參數分別為
- **head** : 此 linked list 的最前端
- **tail** : 此 linked list 的最末端
- **length** : 此 linked list 共有多少數
運作邏輯:
1. 每一對的 `beg` 與 `end` 會分別對應到要比較的數列最前方與最後方，並取 `beg` 的值作為 `piv`。
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
piv[label= "piv" shape= plaintext fontcolor="blue"]
beg0[label= "beg[0]" shape= plaintext fontcolor="red"]
end0[label= "end[0]" shape= plaintext fontcolor="red"]
L[label= "L" shape= plaintext fontcolor="red"]
R[label= "R" shape= plaintext fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
piv->161;
}
{
rank= "same";
L->beg0->161;
}
{
rank= "same";
R->end0->933;
}
161->5->421->873->964->93->933;
}
```
2. 從 R 的地方開始向左方比較，找到第一個比 piv 值小的
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
L[label= "L" shape= plaintext fontcolor="red"]
R[label= "R" shape= plaintext fontcolor="red"]
93[label= "93" fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
L->161;
}
{
rank= "same";
R->93;
}
161->5->421->873->964->93->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
3. 將 L 的數值代換成剛剛找到的比 piv 小的數 ( R 的數值 )，並將 L 向右位移一個位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
L[label= "L" shape= plaintext fontcolor="red"]
R[label= "R" shape= plaintext fontcolor="red"]
R93[label= "93" fontcolor="red"]
L93[label= "93" fontcolor="red"]
{
rank= "same";
L->5;
}
{
rank= "same";
R->R93;
}
L93->5->421->873->964->R93->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
4. 從 L 的地方開始向右方比較，找到第一個比 piv 值大的數值
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
L[label= "L" shape= plaintext fontcolor="red"]
R[label= "R" shape= plaintext fontcolor="red"]
R93[label= "93" fontcolor="red"]
L93[label= "93" fontcolor="black"]
421[label= "421" fontcolor="red"]
{
rank= "same";
L->421;
}
{
rank= "same";
R->R93;
}
L93->5->421->873->964->R93->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
5. 將 R 的數值代換成剛剛找到的比 piv 大的數 ( L 的數值 )，並將 R 向左位移一個位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
L[label= "L" shape= plaintext fontcolor="red"]
R[label= "R" shape= plaintext fontcolor="red"]
R421[label= "421" fontcolor="red"]
L421[label= "421" fontcolor="red"]
{
rank= "same";
L->L421;
}
{
rank= "same";
R->964;
}
93->5->L421->873->964->R421->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
6. 重複步驟 2~5 直到 L 與 R 重疊
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
R[label= "R" shape= plaintext fontcolor="red"]
L[label= "L" shape= plaintext fontcolor="red"]
R421[label= "421" fontcolor="black"]
L421[label= "421" fontcolor="red"]
{
rank= "same";
L->L421;
}
{
rank= "same";
R->L421;
}
93->5->L421->873->964->R421->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
7. 將重疊處的數值換為 piv
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
R[label= "R" shape= plaintext fontcolor="red"]
L[label= "L" shape= plaintext fontcolor="red"]
161[label= "161" fontcolor= "blue"]
{
rank= "same";
L->161;
}
{
rank= "same";
R->161;
}
93->5->161->873->964->421->933;
}
```
8. 將最左邊的數丟為下次的比較起始位置，將重疊位置丟為下次比較的最終位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
beg0[label= "beg[0]" shape= plaintext fontcolor="red"]
end0[label= "end[0]" shape= plaintext fontcolor="red"]
161[label= "161" fontcolor= "blue"]
{
rank= "same";
beg0->93;
}
{
rank= "same";
end0->161;
}
93->5->161->873->964->421->933;
}
```
9. 將重疊部份右移一位的數丟為下次的比較起始位置，將最右端位置丟為下次比較的最終位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
beg0[label= "beg[0]" shape= plaintext fontcolor="red"]
end0[label= "end[0]" shape= plaintext fontcolor="red"]
beg1[label= "beg[1]" shape= plaintext fontcolor="orange"]
end1[label= "end[1]" shape= plaintext fontcolor="orange"]
161[label= "161" fontcolor= "blue"]
{
rank= "same";
beg0->93;
}
{
rank= "same";
end0->161;
}
{
rank= "same";
beg1->873;
}
{
rank= "same";
end1->933;
}
93->5->161->873->964->421->933;
}
```
10. 重複進行 1~9 直到排序完成
:::warning
TODO:
1. 加上時間和空間複雜度的分析
2. 說明 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 指出進一步的效能提升機會
3. 避免修改為 doubly-linked list，沿用原本的 singly-linked list 設定
:notes: jserv
:::
### singly-linked list (array 思維)
在最初改動時，由於整體思路仍無法突破 array 的思維，所以程式碼十分冗長，需要用多個變數來存取每個階段的資訊。
邏輯如下：
1. 每一對的 `beg` 與 `end` 會分別對應到要比較的數列最前方與最後方，並取 `beg` 的值作為 `piv`。
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
piv[label= "piv" shape= plaintext fontcolor="blue"]
tail[label= "tail" shape= plaintext fontcolor="red"]
beg0[label= "beg[0]" shape= plaintext fontcolor="red"]
end0[label= "end[0]" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
piv->161;
}
{
rank= "same";
cur->beg0->161;
}
{
rank= "same";
tail->end0->933;
}
161->5->421->873->964->93->933;
}
```
2. 從最左方的地方開始向右方比較，找到第一個比 piv 值大的
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
tail[label= "tail" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
421[label= "421" fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
cur->421;
}
{
rank= "same";
tail->933;
}
161->5->421->873->964->93->933;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
3. 將比 piovt 大的值移到 `tail` 後方，並把 `cur` 位移一格
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
tail[label= "tail" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
421[label= "421" fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
cur->873;
}
{
rank= "same";
tail->933;
}
161->5->873->964->93->933->421;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
4. 重複步驟2與步驟3，直到 `cur` 與 `tail` 重疊
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
tail[label= "tail" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
161[label= "161" fontcolor="blue"]
{
rank= "same";
cur->tail->933;
}
161->5->93->933->421->873->964;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
5. 將 piv 與 cur 指向的值做比較
- 假設 cur 指向的值比 piv 大，cur 所在的位置會是比較的起始位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
tail[label= "tail" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
beg1[label= "beg[1]" shape= plaintext fontcolor="green"]
end1[label= "end[1]" shape= plaintext fontcolor="green"]
beg0[label= "beg[0]" shape= plaintext fontcolor="navy"]
end0[label= "end[0]" shape= plaintext fontcolor="navy"]
161[label= "161" fontcolor="blue"]
{
rank = "same";
beg1->933;
}
{
rank = "same";
end1->964
}
{
rank = "same";
beg0->161;
}
{
rank = "same";
end0->93
}
{
rank= "same";
cur->tail->933;
}
161->5->93->933->421->873->964;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
- 假設 cur 指向的值比 piv 小，cur 所在的位置會是比較的結束位置
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
tail[label= "tail" shape= plaintext fontcolor="red"]
cur[label= "cur" shape= plaintext fontcolor="red"]
beg1[label= "beg[1]" shape= plaintext fontcolor="green"]
end1[label= "end[1]" shape= plaintext fontcolor="green"]
beg0[label= "beg[0]" shape= plaintext fontcolor="navy"]
end0[label= "end[0]" shape= plaintext fontcolor="navy"]
161[label= "161" fontcolor="blue"]
{
rank = "same";
beg1->933;
}
{
rank = "same";
end1->964
}
{
rank = "same";
beg0->161;
}
{
rank = "same";
end0->93
}
{
rank= "same";
cur->tail->93;
}
161->5->93->933->421->873->964;
piv[label= "piv:161" shape= plaintext fontcolor="blue"]
}
```
```cpp=
void quicksort(node_t *head, int length)
{
if (!head)
return;
node_t *beg[length], *end[length], **tmp, **cur, *tail, *temp;
node_t *cur_beg, *cur_end;
int i=0, piv;
/* find the tail of this liked list */
tail = head;
while (tail->next)
tail = tail->next;
beg[0] = head;
end[0] = tail;
while (i >= 0) {
cur_beg = beg[i];
cur_end = end[i];
cur = &cur_beg;
tail = cur_end;
beg[i+1] = *cur;
if( cur_beg != cur_end && cur_beg && cur_end) {
piv = cur_beg->value;
while (*cur != cur_end) {
/**
* if the current node value is larger than value of pivot,
* move it to the tail.
**/
while (*cur != cur_end && (*cur)->value <= piv) {
end[i] = *cur;
cur = &((*cur)->next);
}
if (*cur == cur_end)
break;
temp = tail->next;
tail->next = *cur;
*cur = (*cur)->next;
tail = tail->next;
tail->next = temp;
}
/**
* Now we have a sorted linked.
* The right side of current node is larger than the pivot,
* and the left side of current node is less than the pivot.
* However we have not processed current node yet.
* There are two condition need to be thought about:
*
* - If the value of current node is larger than the pivot,
* the linked list should be cutted as
* beg - the node before current node | current node - tail
*
* - If the value of current node is less than the pivot,
* the linked list should be cutted as
* beg - current node | the node after current node - tail
*/
if ((*cur)->value > piv) {
beg[i+1] = *cur;
beg[i]->value = end[i]->value;
end[i]->value = piv;
}
if ((*cur)->value <= piv) {
if( tail == *cur) {
beg[i+1] = *cur;
beg[i]->value = tail->value;
tail->value = piv;
}
else {
end[i] = *cur;
beg[i+1] = (*cur)->next;
beg[i]->value = end[i]->value;
end[i]->value = piv;
}
}
end[++i] = tail;
} else {
i--;
}
}
}
```
### singly-linked list
在上面使用 array 思維但使用 linked list 實做時遇到很多例外要處理，意識到即使可以用 linked list 來實做類似 array 的內容，但是每種不同的資料型態適合的實做並不相同。
在實做我曾經遇到的 bug 為，若是有相同的數字需要排序，那我的程式會陷入無窮迴圈。
後來發現原因是我將 pivot 和與他的數字相同的 node 放在同一邊，根據 quick sort 的運作邏輯，它會將 node 與 pivot 比較並逐次拆解，直到只剩下最後一個 node ，再慢慢依序連接回去，若將 pivot 和與它相同優先序的 node 放在同邊的話，會導致永遠無法拆解至只剩下一個 node。
在這裡我將它改寫為以下程式碼：
```cpp=
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *sorted = NULL;
node_t *stack[MAX_LENGTH] = {NULL};
int stack_count = 0;
stack[stack_count] = *list;
while (stack_count >= 0) {
if (!stack[stack_count]->next) {
list_add_node_t(&sorted, stack[stack_count]);
stack_count--;
continue;
}
node_t *left = NULL, *right = NULL, *tmp = stack[stack_count]->next;
list_add_node_t(&right, stack[stack_count]);
while (tmp) {
node_t *n = tmp;
tmp = tmp->next;
list_add_node_t((n->value > stack[stack_count]->value)? &right:&left, n);
}
--stack_count;
if (left)
stack[++stack_count] = left;
if (right)
stack[++stack_count] = right;
}
*list = sorted;
}
```
最近在看 [並行和多執行緒程式設計系列講座](/@sysprog/concurrency) 的教材內容，當中提到 mutex 與 semaphores 時會特別解釋在不同的意境下，就會有相對合適的實做方式，經過這幾次對 quick sort 的實做後開始強烈的意識到，不同的意境需要搭配上不同實做的重要性。
在最初的實做儲存迭代資訊時，我所儲存的都是 linked list 中的某個位置，就如同儲存陣列的 index。陣列由於連續記憶體空間的特性可以快速存取特定 index 的數值，指標卻需要一個一個的走訪，尤其是在 singly-linked list 需要存取已經走訪過得 node 時，更是顯得不便。
在最後的版本中，利用了 linked-list 可以簡單的連接 node 的特性，將需要比較的數值拆做 left 與 right 兩條 linked-list，比起使用 index 比較的思維，這個版本明顯的清晰許多。
即使相同的功能可以使用不同的實做完成，但如果能夠清晰的了解資料結構與問題本身的特性，選擇了適合的實做，在寫程式碼的過程中可以減少處理例外的狀況，易讀性也會大大提昇。
Sign in with Wallet
Connect another wallet