---
title: 2021q1 Homework (quiz1)
---
# 2021q1 Homework1 (quiz1)
contributed by < `ParkerMactavish` >
## 測驗題目
### 測驗 1
考慮一個單向 linked list，其結構定義為:
```c
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;
}
```
### 題目解釋
`quicksort` 函式會被傳入一個指向指向 node_t 的指標的指標 `list`，
```c=14
if (!*list)
return;
```
在 14, 15 行，程式所做的是檢查 `list` 指向的指標是否指向一個被分配的記憶體空間，如果是則可以繼續往下進行遞迴，如果指向的是空指標指則離開函式。
```graphviz
digraph {
rankdir="LR"
list -> "pointer to list head";
"pointer to list head" -> struct1:f2;
struct1:f1 -> "";
"" [shape=none];
list [shape=box];
"pointer to list head" [shape=box]
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];"檢查是否為空指標" -> "pointer to list head" [color=firebrick];
"檢查是否為空指標" [color=firebrick fontcolor=firebrick]
}
```
```c=17
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
接著， `list` 所指向的指標會被複製一份給 `pivot` ，再透過 `pivot` 將他所指向的結點內存的值取出存入 `value` ， `value` 是稍後進行比較會被拿來做為準繩的數值。
此外，將 `p` 指向 `pivot` 的下個節點，並且透過將 `pivot` 所指向的元素的 `next` 設為空指標，把 `pivot` 所指向的節點孤立出來。
```graphviz
digraph {
rankdir="LR"
list -> "pointer to list head";
"pointer to list head" -> struct1:f2;
pivot -> struct1:f2;
"pointer to list head" -> pivot[label="予值" color=firebrick fontcolor=firebrick];
struct1:f0 -> value [fontcolor=firebrick color=firebrick label="予值"];
struct1:f1 -> struct2;
struct2:f1 -> "";
"" [shape=none];
list [shape=box];
"pointer to list head" [shape=box]
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
}
```
```graphviz
digraph {
rankdir="LR"
pivot -> struct1:f2;
struct1:f1 -> p[label="予值" color=firebrick fontcolor=firebrick];
struct1:f1 -> struct2:f2;
struct2:f1 -> "";
"" [shape=none];
p -> struct2:f2;
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
value;
}
```
```graphviz
digraph {
rankdir="LR"
pivot -> struct1:f2;
NULL -> struct1:f1[label="予值" color=firebrick fontcolor=firebrick];
struct1:f1 -> NULL;
p -> struct2:f2;
struct2:f1 -> "";
"" [shape=none];
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
value;
}
```
**找出 AAA 與 BBB**
```c=22
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);
}
```
接著，從將 `left` 與 `right` 兩個指向 node_t 型態的指標初始化，之後迭代過 `p` 所指向的串列，並且把所有元素根據某些條件，透過 `list_add_node_t` 將元素放在 `left` 與 `right` 串列中。而為了知道條件為何，大致經過下述推理。
透過第 26 行的 `list_add_node_t(n->value > value ? AAA : BBB, n)` 得知 `right` 與 `left` 所指向的串列其中一個是大於 `value` ，另一個則是小於等於 `value` 的。
```c=32
node_t *result = NULL;
list_concat(&result, left);
CCC;
```
```c=6
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
再根據題目第 32 行進行的操作，先將 `result` 指向的位置設為空指標，再呼叫 `list_concat` 傳入 `result` 的地址與 `left` 來看，因為 `list_concat` 函式中，有個迭代過 `left` 指向的內容並且檢查是否是空指標的動作，這個動作是在找尋 `left` 所指向的 node_t 鍊結串列的結尾，並且將結尾與 right 鍊結串列連結起來；因此題目先將 `result` 與 `left` 連結起來，根據 quick sort 演算法，可以推測 CCC 的部分是再將 `result` 與 `pivot` 連結後，又與 `right` 連結。
最後根據題目所提供的參考輸出，為由小到大遞增，因此可以推測 `left` 所存放的元素是小於等於 `pivot` ， `right` 則存放大於 `pivot` 的元素。
```c=
static inline void list_add_node_t(node_t **list, node_t *node) {
node->next = *list;
*list = node;
}
```
> 這裡 `list_add_node_t` 函式的第二個參數名稱應該是筆誤打成與型態一樣的 node_t ，因此這裡暫時以 `node` 代稱它。
而回到解答 AAA 與 BBB 上，根據 `list_add_node_t` 的宣告，第一個參數為指向一個指向 node_t 型態指標的指標，因此這裡 AAA 所必須填入的是 `&right` ， BBB 則是 `&left` 。而整個 while 迴圈的操作則如下圖
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
p->struct1:f2;
struct1:f1->struct2:f2;
right_ele1[label="list of elements\nwhose values are\ngreater than value of pivot"];
left_ele1[label="list of elements\nwhose values are\nsmaller than value of pivot"];
right->right_ele1;
left->left_ele1;
}
```
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
p->struct1:f2;
n->struct1:f2;
p->n[label="予值" color=firebrick fontcolor=firebrick];
struct1:f1->struct2:f2;
right_ele1[label="list of elements\nwhose values are\ngreater than value of pivot"];
left_ele1[label="list of elements\nwhose values are\nsmaller than value of pivot"];
right->right_ele1;
left->left_ele1;
}
```
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
p->struct2:f2;
n->struct1:f2;
struct1:f1->p[label="予值" color=firebrick fontcolor=firebrick];
struct1:f1->struct2:f2;
right_ele1[label="list of elements\nwhose values are\ngreater than value of pivot"];
left_ele1[label="list of elements\nwhose values are\nsmaller than value of pivot"];
right->right_ele1;
left->left_ele1;
}
```
如果 `n->value` 大於 `value` 則，
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
p->struct2:f2;
n->struct1:f2;
right_ele1[label="list of elements\nwhose values are\ngreater than value of pivot"];
left_ele1[label="list of elements\nwhose values are\nsmaller than value of pivot"];
right->struct1:f2;
struct1:f1->right_ele1;
n->right[label="list_add_node_t" color=firebrick fontcolor=firebrick]
left->left_ele1;
}
```
否則，
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
p->struct2:f2;
n->struct1:f2;
right_ele1[label="list of elements\nwhose values are\ngreater than value of pivot"];
left_ele1[label="list of elements\nwhose values are\nsmaller than value of pivot"];
right->right_ele1;
n->left[label="list_add_node_t" color=firebrick fontcolor=firebrick]
left->struct1:f2
struct1:f1->left_ele1;
}
```
重複循環直到 `p` 指向一個空指標。
**找出 LLL**
```c=29
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
```
29, 30 行是分別對 `left` 與 `right` 指向的 node_t 鍊結串列做 `quicksort` 函式的遞迴呼叫，讓 `left` 與 `right` 可以再各自分成小於等於各自的 pivot 以及大於各自 pivot 兩堆，待遞迴呼叫持續分堆至每堆只有一個元素的 base case 時，再將已經確定大小的兩堆進行組合，而組合的部分就是 32~CCC 所在那行在禁行的事。
```c=6
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
而 `list_concat` 這個函式在上面提到，是將 `*left` 所指向 node_t 鍊結串列與 `right` 指向的鍊結串列進行結合，需要注意的是型態部分， `left` 為指向一個指向 node_t 型態的指標的指標，因此在迭代過程中，要找尋 `*left` 串列中下一個元素，必須先透過 `*left` 得到 `left` 所指向的指標，再透過該指標得到 `*left` 所指向的 node_t 元素中的 next 值，最後透過取址的方式將該 next 所指向的元素的位址取為 `node_t**` 以符合 `left` 的型態。因此 LLL為 `left = &(*left)->next;`。其中 while 迴圈的操作與最後連接 `right` 的演示如下圖。
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
left -> head ->struct1:f2;
struct1:f1->struct2:f2;
empty[label="" shape="none"];
struct2:f1->empty;
}
```
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
head ->struct1:f2;
left->struct1:f1->struct2:f2;
empty[label="" shape="none"];
struct2:f1->empty;
}
```
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">1st element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">2nd element</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
head ->struct1:f2;
struct1:f1->struct2:f2;
empty[label="" shape="none"];
left -> struct2:f1->empty;
}
```
直到 `left` 指向一個指向空指標的指標，
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">n-1th element on left side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">nth element on left side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">first element on right side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct1:f1->struct2:f2;
left -> struct2:f1->NULL;
right -> struct3:f2;
}
```
```graphviz
digraph {
rankdir="LR";
struct1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">n-1th element on left side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">nth element on left side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" WIDTH="150" PORT="f2">
<TR><TD COLSPAN="2" WIDTH="150">first element on right side</TD></TR><TR><TD PORT="f0"> value </TD><TD PORT="f1"> next </TD></TR>
</TABLE>> shape=none];
struct1:f1->struct2:f2;
left -> struct2:f1 -> struct3:f2;
right -> struct3:f2;
right -> struct2:f1[label="予值" color=firebrick fontcolor=firebrick];
}
```
**找出 CCC**
```c=32
node_t *result = NULL;
list_concat(&result, left);
CCC;
```
最後要在找出程式第 34 行的 CCC 為何，而根據上方的推論，緊接著 `left` 後需要將 `pivot` 以及 `right` 接上 `result` 所指向的鍊結串列，再根據 `list_concat` 所需的參數資料型態，可以判斷 CCC 為 `list_concat(&result, pivot); list_concat(&result, right)`。
### 修正隨機數字產生的方式
#### 新增函式以進行題目的編譯
除了 `queue.c` 與 `queue.h` 存放 `node_t` 的型態，與 `static inline void list_add_node_t(node_t **, node_t *)`, `static inline void list_concat(node_t **, node_t *)`, `void quicksort(node_t **)` 這三個函式讓鏈結串列形式的佇列能被排序外，在 `main.c` 裡面還需要額外定義 `node_t *list_make_node_t(node_t *, int);` 與 `void list_free(node_t **)` 以滿足 main function 會使用的一些 utility function 。
其二函式定義如下， `list_make_node_t` 會將傳入的 `int` 型態的數值做成鍊結串列的節點，並且接在串列的頭部； `list_free` 則會迭代過整個串列並且把所有元素的記憶體空間都釋放掉。
```c
node_t *list_make_node_t(node_t *list, int number) {
node_t *newh = malloc(sizeof(node_t));
newh->next = list;
newh->value = number;
return newh;
}
```
```c=
void list_free(node_t **list) {
node_t *current = *list, *nextEle;
while (current) {
nextEle = current->next;
free(current);
current = nextEle;
}
}
```
而在執行 `gcc main.c queue.c -o sort_queue` 進行編譯，並且使用 `./sort_queue` 執行後，會得到以下的執行輸出:
```
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
```
然而會發現每次執行 `./sort_queue` 的時候都會是由 1016, 84 等數字開始的這個數列，這是因為在 main 函式中使用 `random` 卻沒有利用設定 `srandom` 來調整亂樹種子，因此根據 [random(3)](https://linux.die.net/man/3/random) 的說明在進行 `random` 呼叫前使用 `srandom()` 來調整亂樹種子，同時，為了讓亂樹種子隨時間變化，因此參考 [time(2)](https://man7.org/linux/man-pages/man2/time.2.html) 使用 `time(NULL)` 來得到目前時間自 1970-1-1 00:00:00 的秒數 。修改後的程式如下，
```c=53
size_t count = 20;
srandom(time(NULL));
node_t *list = NULL;
while (count--) {
list = list_make_node_t(list, random() % 1024);
}
```
編譯後執行可以發現在不同時期可以得到不同的元素數值，執行結果如下
在 2021-3-6 21:48:38 GMT+08:00 執行的結果：
```
NOT IN ORDER : 279 138 684 754 350 831 578 964 131 994 718 586 510 206 370 279 931 473 7 10
IN ORDER : 7 10 131 138 206 279 279 350 370 473 510 578 586 684 718 754 831 931 964 994
```
在 2021-3-6 21:50:14 GMT+08:00 執行的結果：
```
NOT IN ORDER : 894 922 847 272 852 828 174 642 168 661 131 347 628 744 694 811 469 879 695 946
IN ORDER : 131 168 174 272 347 469 628 642 661 694 695 744 811 828 847 852 879 894 922 946
```
## 修正以避免遞迴呼叫
參考 [Optimized QuickSort](https://alienryderflex.com/quicksort/) ，利用 `begin` 與 `end` 兩個 `int` 型態的陣列取代 call stack 紀錄目前正在進行排序的片段，每完成一次片段排序便會儲存本次的片段範圍，並算出下次的片段範圍，如果已經到迭代的 base case ，也就是排序片段只剩一個元素時，就會讀取過往的排序紀錄，流程描述如下，
```graphviz
digraph {
init_i[label="使用 i 來儲存 call stack 的深度" shape="parallelogon"];
init_begin_end[label="利用 begin, end, data 三個 int 型態的陣列\n儲存排序開頭 offset、結尾 offset 與 所有資料\n並將 begin[0] 設為 0 並將 end[0] 設為 list 的長度(eleNum)" shape="parallelogon"];
branch_i[label="如果 i 大於等於 0" shape="diamond"];
start[label="將 leftIndex 設為 begin[i] 來儲存本次排序從左側遞增的目標 offset，\n rightIndex 設為 end[i] - 1 來儲存本次排序從右側遞減的目標 offset" shape="parallelogon"];
branch_L_R[label="如果 leftIndex < rightIndex，\n也就是需要排序的區間內含兩筆以上資料的狀態" shape="diamond"];
get_pivot[label="讓 pivot 暫存為 data[leftIndex]" shape="parallelogon"];
branch_L_R_2[label="如果 leftIndex < rightIndex，\n也就是還未在迴圈內遍歷過所有需要檢查的元素時" shape="diamond"];
branch_R_dec[label="如果 data[rightIndex] 大於等於 pivot\n且 leftIndex < rightIndex" shape="diamond"];
dec_R[label="rightIndex--" shape="parallelogon"];
branch_L_R_swap[label="如果 leftIndex 小於 rightIndex" shape="diamond"];
L_R_swap[label="data[leftIndex] = data[rightIndex];\nleftIndex++;" shape="parallelogon"];
branch_L_inc[label="如果 data[leftIndex] 小於等於 pivot\n且 leftIndex < rightIndex" shape="diamond"];
inc_L[label="leftIndex++" shape="parallelogon"];
branch_L_R_swap_2[label="如果 leftIndex 小於 rightIndex" shape="diamond"];
L_R_swap_2[label="data[rightIndex] = data[leftIndex];\nrightIndex--;" shape="parallelogon"];
dec_i[label="i--\n可以理解為遞迴的 return" shape="parallelogon"];
settle_pivot[label="data[leftIndex]=pivot;\n因為這時候 leftIndex 與 rightIndex 相同，\n指向 data 陣列中的其中一個 element\n其中右側所有元素都大於等於 pivot\n同時左側所有元素都小於等於 pivot" shape="parallelogon"];
settle_begin[label="begin[i+1] = leftIndex + 1;\n因為這時候需要針對 leftIndex 所隔出的左右兩個子陣列分別進行排序，\n這裡原作者先對 leftIndex 右側的子陣列排序，\n而在 i-- 後才會排序 leftIndex 左側的子陣列" shape="parallelogon"];
settle_end_next[label="end[i+1]=end[i];\n呼應上面的步驟，\n因為要先取右半的陣列進行排序，\n因此將本次的 end 範圍留到下次使用" shape="parallelogon"];
settle_end_current[label="end[i] = leftIndex\n呼應上面的步驟，\n因為之後在 i-- 後要能進行左半陣列的排序，\n因此將 leftIndex 儲存在目前的 end 元素中，\n等之後使用" shape="parallelogon"];
settle_i[label="i++\n得到下一次需要使用的 begin 與 end\n以便再下個循環開頭設定 leftIndex 與 rightIndex" shape="parallelogon"];
end[label="結束"];
init_i -> init_begin_end -> branch_i;
branch_i -> start[label="是"];
start -> branch_L_R;
branch_L_R -> get_pivot[label="是"];
branch_L_R -> dec_i [label="否"];
get_pivot -> branch_L_R_2;
branch_L_R_2 -> branch_R_dec[label="是"];
branch_R_dec -> dec_R[label="是"];
dec_R -> branch_R_dec;
branch_R_dec -> branch_L_R_swap[label="否"];
branch_L_R_swap -> L_R_swap[label="是"];
L_R_swap -> branch_L_inc;
branch_L_R_swap -> branch_L_inc[label="否"];
branch_L_inc -> inc_L[label="是"];
inc_L -> branch_L_inc;
branch_L_inc -> branch_L_R_swap_2[label="否"];
branch_L_R_swap_2 -> L_R_swap_2[label="是"];
branch_L_R_swap_2 -> branch_L_R_2[label="否"];
branch_L_R_2 -> settle_pivot[label="否"];
settle_pivot -> settle_begin -> settle_end_next -> settle_end_current -> settle_i -> branch_L_R;
branch_i -> end[label="否"];
}
```
如果以 [3, 2, 1, 5, 4] 四個數字的鍊結串列進行舉例， 處理順序如下，
* i = 0
* 初始狀態
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 3 | 2 | 1 | 5 | 4 |
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | x | x | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| 5 | x | x | x | x |
leftIndex = 0
rightIndex = 4
pivot = 3
* rightIndex 從右側遞減，找到第一個比 pivot 小的數值 (1)
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 3 | 2 | 1 | 5 | 4 |
leftIndex = 0
rightIndex = 2
pivot = 3
* 將 rightIndex 指到的值予值給 leftIndex 指向的元素後 leftIndex++
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| **1** | 2 | 1 | 5 | 4 |
leftIndex = **1**
rightIndex = 2
pivot = 3
* leftIndex 從左側遞增，嘗試找到一個比 pivot 還要大的數值
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 1 | 5 | 4 |
leftIndex = **2**
rightIndex = 2
pivot = 3
* 因為 leftIndex 等於 rightIndex ，因此將 pivot 予值給 data[leftIndex] 後，對 begin, end 陣列進行修改，以達成類似遞迴的效果。
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | **3** | 5 | 4 |
leftIndex = 2
rightIndex = 2
pivot = 3
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | **3** | x | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| **2** | **5** | x | x | x |
**i=1**
* i = 1
* 初始狀態
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | 5 | 4 |
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | 3 | x | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| 2 | 5 | x | x | x |
leftIndex = 3
rightIndex = 4
pivot = 5
* rightIndex 從右側遞減，找到第一個比 pivot 小的數值 (4)
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | 5 | 4 |
leftIndex = 3
rightIndex = 4
pivot = 5
* 將 rightIndex 指到的值予值給 leftIndex 指向的元素後 leftIndex++
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | **4** | 4 |
leftIndex = **4**
rightIndex = 4
pivot = 5
* 因為 leftIndex 等於 rightIndex ，因此將 pivot 予值給 data[leftIndex] 後，對 begin, end 陣列進行修改，以達成類似遞迴的效果。
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | 4 | **5** |
leftIndex = 4
rightIndex = 4
pivot = 5
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | 3 | 5 | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| 2 | 5 | 5 | x | x |
**i=2**
* i = 2
* 初始狀態
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | 4 | 5 |
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | 3 | 5 | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| 2 | 4 | 5 | x | x |
leftIndex = 5
rightIndex = 4
* 因為遇到被排序片段內沒有元素 (leftIndex > rightIndex) 的狀況，因此將 i 減一，跳回上一層
**i=1**
* i = 1
* 初始狀態
| data[0] | data[1] | data[2] | data[3] | data[4] |
| ------- | ------- | ------- | ------- | ------- |
| 1 | 2 | 3 | 4 | 5 |
| begin[0] | begin[1] | begin[2] | begin[3] | begin[4] |
| -------- | -------- | -------- | -------- | -------- |
| 0 | 3 | 5 | x | x |
| end[0] | end[1] | end[2] | end[3] | end[4] |
| ------ | ------ | ------ | ------ | ------ |
| 2 | 4 | 5 | x | x |
leftIndex = 3
rightIndex = 3
* 因為遇到被排序片段內只有一個元素 (leftIndex = rightIndex) 的狀況，因此將 i 減一，跳回上一層
**i=0**
後面的排序與前面排序 data[3], data[4] 的片段相同，因此不特別贅述。
其實現如下，因為這次所使用的鍊結串列是單向非循環的版本，因此我將整個串列複製至一個在函式內分配的空間 `data` ，以便後面能進行連續記憶體的 random access 。同時，為了能紀錄該次排序的開頭與結尾位置，所以我又額外分配了 `begin` 與 `end` 兩塊與串列一樣長的空間來進行儲存。
```c
void quicksort_nonrecursive(node_t *list) {
int eleNum = 0;
node_t *elePtr = list;
while (elePtr) {
elePtr = elePtr->next;
eleNum++;
}
int pivot, i = 0, leftIndex, rightIndex, logEleNum = log2(eleNum),
*data = malloc(sizeof(int) * eleNum),
*begin = malloc(sizeof(int) * eleNum),
*end = malloc(sizeof(int) * eleNum);
elePtr = list;
eleNum = 0;
while (elePtr) {
data[eleNum] = elePtr->value;
elePtr = elePtr->next;
eleNum++;
}
begin[0] = 0;
end[0] = eleNum;
while (i >= 0) {
leftIndex = begin[i];
rightIndex = end[i] - 1;
if (leftIndex < rightIndex) {
pivot = data[leftIndex];
while (leftIndex < rightIndex) {
while (data[rightIndex] >= pivot && leftIndex < rightIndex)
rightIndex--;
if (leftIndex < rightIndex)
data[leftIndex++] = data[rightIndex];
while (data[leftIndex] <= pivot && leftIndex < rightIndex)
leftIndex++;
if (leftIndex < rightIndex)
data[rightIndex--] = data[leftIndex];
}
data[leftIndex] = pivot;
begin[i + 1] = leftIndex + 1;
end[i + 1] = end[i];
end[i++] = leftIndex;
}
else {
i--;
}
}
elePtr = list;
for (int i = 0; i < eleNum; i++) {
elePtr->value = data[i];
elePtr = elePtr->next;
}
free(data);
free(begin);
free(end);
}
```
* 遞迴與非遞迴的比較
透過 `clock_gettime` 函式所得到的時間資料，可以將兩種排序方法進行執行時間比較，方法如下，並且利用 `argv` 傳進來的值，以進行任意數量元素的排列，同時利用 `list1` 與 `list2` 將相同的元素放入兩個鍊結串列中，如此便可以讓兩種不同方法分別排序並比較時間
```c
struct timespec start, end, diff;
clock_gettime(CLOCK_MONOTONIC, &start);
// function to measure execution time
lock_gettime(CLOCK_MONOTONIC, &end);
list_display(list1);
if ((end.tv_nsec-start.tv_nsec)<0) {
diff.tv_sec = end.tv_sec - start.tv_sec - 1;
diff.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
} else {
diff.tv_sec = end.tv_sec-start.tv_sec;
diff.tv_nsec = end.tv_nsec-start.tv_nsec;
}
printf("which takes %ld.%09ld seconds\n", diff.tv_sec, diff.tv_nsec);
```
| 節點數量 | 遞迴排序 | 非遞迴排序 |
| --------- | ----------- | ----------- |
| 1,000 | 178.336 us | 138.500 us |
| 10,000 | 2961.681 us | 1808.918 us |
| 100,000 | 63.746 ms | 14.814 ms |
| 1,000,000 | 8.293 s | 0.775 s |
可以看到透過迭代方式進行的快速排序法在時間上優於利用遞迴方式進行的版本。
## linux-list
### 探討與 quiz1 的 quick sort 實作方式的不同
在 linux-list/examples/quick-sort.c 中有實做 `list_qsort` 這個函式，
```c
static void list_qsort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move(&item->list, &list_greater);
}
list_qsort(&list_less);
list_qsort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
與 quiz1 中的 `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 ? &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;
}
```
### 改寫以避免遞迴呼叫
### 根據參考文獻改寫 linux-list
Sign in with Wallet
Connect another wallet