# 2021q1 Homework1 (quiz1)
contributed by < `Nahemah1022` >
###### tags: `linux2021`
- [x] 解釋程式運作原理
- [x] 引入其他 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
- [x] 參考 [Optimized QuickSort](https://alienryderflex.com/quicksort/)，避免使用遞迴呼叫
- [ ] 改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例，避免使用遞迴呼叫
- [ ] [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法，並落實於程式碼中
---
## 一、解釋程式運作原理
### 1. 回顧 QuickSort 演算法
- 演算法流程
1. 選定一 pivot
2. 與其他所有 element 並比較其大小，並分別排至其左右
3. 對左、右兩 partitions 再執行上述演算法
4. 已經分割至最小單位後結束
- 分析：
- Divide & Conquer，將問題不斷分割為性質相似的子問題
- 每次選中的 pivot 是影響效能的關鍵
- 若選擇的 pivot **接近中位數**，則能夠將問題分割為等 size 的子問題，能夠在最小的遞迴深度內將子問題並行處理
- 反之則會使結構歪斜，即失去 Divide 的效果
### 2. 程式碼解讀
```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)
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;
}
```
1. `list_add_node_t`：將 `node_t` 插入原有 `list` 中的頭
- 參數意義解析
- `list`：指向原有 linked list 頭的 indirect pointer
- `node_t`：欲插入 linked list 中的節點
- 功能解析
- 先將 `node_t` 連接至原有 linked list 頭
- 再將頭修改為新節點 `node_t`
2. `list_concat`：將兩 linked list 串接
- 參數意義解析
- `left` 原有 linked list 中的任一節點之 indirect pointer
- `right` 欲串接 linked list 的頭
- 功能解析
- 利用迴圈尋找 `left` 的末端位置，並停留在末端的 next 節點
- 將其內容修改為 `right`，即完成串接
:::success
**問題探討：指標的指標**
```graphviz
digraph structs {
rankdir=LR
node [shape=record];
struct1 [label="{value |<n1> next node address}|<a1>node address|direct pointer address"];
struct2 [label="{value |<n2> next node address}|<a2>node address|direct pointer address"];
struct3 [label="{value |<n3> next node address}|<a3>node address|direct pointer address"];
struct1:n1->struct2:a2[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:n2->struct3:a3[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
- **direct pointer 使用上的限制：**
以此函式為例，若將傳入的參數改為 direct pointer `node_t *left` 並在迴圈中使用 `left = left->next` ，待迴圈行至串列尾端時須提前留意該位置的下一個 node address 是否為 `Null` ，若等到 `left == Null` 時才將 `left` assign 為 `right` ，也已經無法回頭修改到前一個 node 的 next 。
- **indirect pointer 如何避開此限制：**
上述問題發生的主要原因在於 **direct pointer 傳值不傳址**，因此無法同時修改到前者的 next 以及後者的 value，但兩者其實是源自於同一個指標變數，因此可以透過題目中的 indirect pointer `node_t **left` 傳址的性質來一次修改到兩者，即可避免在 singly linked list 中時常路過了就無法再回頭修改的難題。
:::
3. quicksort
- 將串列的頭選為 pivot ，以其 value 大小為準將串列切割為兩部份，分別存放置 `*left` 與 `*right` 中
- 對 `*left` 與 `*right` 再次遞迴上述演算法
- 當串列小至不可再分割時 return
- 最後將 `*left`、`pivot` 與 `*right` 串接即完成
---
## 二、引入其他 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
### 1. 問題與原因探討
若多次執行測驗中的測試程式，會發現每次生成的亂數結果相仿，其原因在於 `random()` 函式本身的 [Pseudorandomness](https://en.wikipedia.org/wiki/Pseudorandomness) 特性，函式的 sequence of numbers 產生於 [deterministic](https://en.wikipedia.org/wiki/Deterministic_system) 的演算法，根據一個亂數種子來產生其對應的數序。
而在測試程式中並沒有給定亂數種子，按照 [random](https://linux.die.net/man/3/random) 中的說明 default 值為 `1` ，因此每次產生的數序皆相同。
### 2. 解決方式
修改為如下程式碼，利用 `srandom()` 設置亂數種子，其值為 `<time.h>` 中的 `time(NULL)`
```cpp
int main(int argc, char **argv) {
srandom(time(NULL));
size_t count = 20;
node_t *list = NULL;
while (count--)
list = list_make_node_t(list, random() % 1024);
...
}
```
如此一來程式在被執行時，將會以當下的系統時間作為亂數種子，利用系統時間不會重複出現的特性，即可在每次執行時產生相異的數序
:::warning
**隱憂：程式在相同系統時間下被執行複數次**
- 系統時間戳記的單位是用微秒，因此若程式在同一個微秒被執行兩次，其內容產生的亂數將會相同（此情況容易發生在 Multi-threaded 的程式中）
:::
---
## 三、[Non-Recursive Optimized QuickSort](https://alienryderflex.com/quicksort/)
### 1. 程式解析
```c=
// quickSort
//
// This public-domain C implementation by Darel Rex Finley.
//
// * Returns YES if sort was successful, or NO if the nested
// pivots went too deep, in which case your array will have
// been re-ordered, but probably not sorted correctly.
//
// * This function assumes it is called with valid parameters.
//
// * Example calls:
// quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
// quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7
#define MAX_LEVELS 1000
bool quickSort(int *arr, int elements)
{
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i] - 1;
if (L < R) {
piv = arr[L];
if (i == MAX_LEVELS - 1)
return NO;
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--;
}
}
return YES;
}
```
程式用 `int beg[], end[]` 兩個 `array` 來模擬 recursive 版本 quick sort 中 stack 堆疊的情形，用來紀錄每一層切割形成區段的開始與結束點
- `if` 區段即是 recursive 版本中的 Divide 行為（程式 `24` 行）
1. 選擇區段的開頭作為 pivot
2. 由最右端開始，找出區段中最後一個小於 pivot 的值（R）
3. 由最左端開始，找出區段中第一個大於 pivot 的值（L）
4. 將 R、L 對調，把區段範圍縮小至 L 到 R 並重複上方演算法
5. 當 R、L 相遇時代表 Divide 已完成，將 pivot 插入中間
6. 將左右兩 partitions 端點位置 push 進 stack 中
- `else` 區段即是 recursive 版本中的 Merge 行為（程式 `42` 行）
1. 程式的資料結構為 `array`，順序正確即可無須做 concatenate
2. 因此直接將 stack pop（`i--`）即可
### 2. 應用在 singly linked list 中
> [GitHub](https://github.com/Nahemah1022/Linux2021-quizzes/tree/main/quiz1)
```c=
#define MAX_LEVELS 1000
void q_sort(queue_t *q)
{
char *pivot;
int i = 0;
list_ele_t *beg[MAX_LEVELS] = {NULL}, *end[MAX_LEVELS] = {NULL}, *junc = NULL;
beg[0] = q->head;
end[0] = q->tail;
while (i >= 0) {
list_ele_t *lh = beg[i], *rh = beg[i], *lt = beg[i], *rt = beg[i];
if (beg[i] != end[i]) {
pivot = beg[i]->value;
list_ele_t *p = beg[i];
while (p != end[i]) {
p = p->next;
if (strcasecmp(p->value, pivot) < 0) {
lt = (lh != beg[i]) ? (lt->next = p) : (lh = p);
} else {
rt = (rh != beg[i]) ? (rt->next = p) : (rh = p);
}
}
lt->next = beg[i];
beg[i]->next = rh;
rt->next = NULL;
beg[i + 1] = beg[i];
end[i + 1] = beg[i];
beg[i] = lh;
end[i] = lt;
beg[i + 2] = rh;
end[i + 2] = rt;
i += 2;
} else {
if (beg[i] != junc)
beg[i]->next = junc;
junc = beg[i];
i--;
}
}
q->tail = q->head = beg[0];
while (q->tail->next)
q->tail = q->tail->next;
}
```
- `if` 區段同樣負責做 Divide
1. 將區段開頭（`beg[i]`）設為 pivot
2. `lh`、`lt`、`rh`、`rt` 分別用來紀錄左、右 partition 區段的頭尾
3. 將左、pivot、右 三個區段的端點 push 進 stack（三元樹）
- `else` 區段同樣負責做 Merge
1. 將區段彼此間 linked list 結構串連
2. 將 stack pop （`i--`）
:::warning
在這之前，我曾經嘗試將上述 [non-recursive quick sort]((#1-程式解析)) 的演算法邏輯複製過來，實做出了以下程式，雖然能夠輸出正確的結果，但效能相當不理想，甚至可能比普通的 insertion sort 還要差。
```c=
void q_sort(queue_t *q)
{
char *pivot;
int i = 0;
list_ele_t *beg[q->size], *end[q->size];
list_ele_t *l, *r, *pr;
beg[0] = q->head;
end[0] = q->tail;
while (i >= 0) {
l = beg[i];
r = end[i];
if (l && r && l != r) {
pivot = l->value;
while (l != r) {
pr = r = l;
while (pr != end[i]) { // find the last one smaller than pivot
pr = pr->next;
if (strcasecmp(pr->value, pivot) < 0)
r = pr;
}
if (r != l) { // found
l->value = r->value;
l = l->next;
}
while (strcasecmp(l->value, pivot) <= 0 &&
l != r) { // find the first one bigger than pivot
l = l->next;
}
if (l != r) {
r->value = l->value;
}
}
l->value = pivot;
beg[i + 1] = l->next;
end[i + 1] = end[i];
end[i++] = l;
} else {
i--;
}
}
}
```
我檢討其原因後發現問題出在兩者使用的資料結構，不同於[上方](#1-程式解析)程式使用的 `array` ，本處使用的 `singly linked list` **無法直接造訪前一個 index 的 node**，因此在無法任意修改資料結構的環境下，要作到上述演算法中 *由最右端開始，找出區段中最後一個小於 pivot 的值* ，**勢必要從頭開始找到尾** 並紀錄最小者（即上方程式的 `16` 行），才能夠確保其為 *最後一個*，然而這會使效能遽減，會讓演算法複雜度直接增加 n 個 order。
重新思考上方 [Non-Recursive Quicksort](#1-程式解析) 程式的核心精神其實是在於 **用 stack 去紀錄切割而成的區間端點**，而非左右交換的 partition 演算法，因此我將 partition 的手段從左右交換改回單向造訪並比較，最後才實做出了 performance 正常的 [optimized-non-recur-linkedlist-qsort.c](https://github.com/Nahemah1022/Linux2021-quizzes/blob/main/quiz1/optimized-non-recur-linkedlist-qsort.c) 程式。
:::
---
## 四、[linux-list](https://github.com/sysprog21/linux-list) 中 quick sort 的不同
---
## 五、[A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)
Sign in with Wallet
Connect another wallet