# 2021q1 Homework1 (quiz1)
contributed by < `YOYOPIG` >
###### tags: `linux2021`
## TODO list
- [x] 重新回答第 1 周測驗題並解釋原理
- [x] Graphviz 畫出 list
- [x] Pseudorandom number generator
- [x] Optimized QuickSort
- [ ] linux-list
- [ ] [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)
## 程式運作原理
由各 function 名稱不難看出，這支程式主要是在實作對 Singly linked list 的 quick sort 演算法。有了大致的認知後，從 main function 開始 trace code。
### main
``` c
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;
}
```
main function 做的事相當簡單，先隨機產生給定數量(20)的 nodes，印出之後做 sort，再印出排序完的 list。最後，檢查排序是否成功並 free 掉資源。
### 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;
}
```
這支程式最主要的程式碼，我們可以看到有許多行被挖空了 :cry: 只好一步一步慢慢來
首先是 Edge case 的檢查，如果傳入的值為 NULL，則直接 return，作為後續 recursive call 的中斷點。程式碼如下：
``` c
if (!*list)
return;
```
接著，取出 quick sort 演算法中的 pivot node，切開 next 指標。
``` c
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
```graphviz
digraph{
rankdir=LR
pivot [label="pivot" shape="box"]
p [label="p" shape="box"]
n1 [label="Node 1" shape="box"]
n2 [label="Node 2" shape="box"]
n3 [label="Node 3" shape="box"]
n4 [label="Node 4" shape="box"]
remaining [label="......" shape="none"]
pivot -> n1
p -> n2 -> n3 -> n4 -> remaining
}
```
一個一個 traverse 剩下的 nodes，比較它們的值和 pivot 的大小，分成兩堆。較大的那堆應該位在 pivot 的右邊，小的那堆位於 pivot 的左邊。因此，我們可以完成程式碼的填空，`AAA`應為`(e) &right`，`BBB`應為`(c) &left`。完整結果如下：
``` c
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);
}
```
```graphviz
digraph{
rankdir=LR
pivot [label="pivot" shape="box"]
left [label="left" shape="box"]
right [label="right" shape="box"]
small [label="Elements <= pivot (Sorted)" shape="box"]
large [label="Elements > pivot (Sorted)" shape="box"]
n1 [label="Node 1" shape="box"]
pivot -> n1
left ->small
right -> large
}
```
透過 Recursive call 分別對左堆及右堆作排序，最後依照排序好的左堆-> pivot ->排序好的右堆這樣的順序，即可完成對整個 list 的排序。因此，我們可以知道`CCC`應該要選`(b) list_concat(&result, pivot); list_concat(&result, right)`。完整結果如下：
``` c
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
```
```graphviz
digraph{
rankdir=LR
pivot [label="pivot" shape="box"]
left [label="left (Sorted)" shape="box"]
right [label="right (Sorted)" shape="box"]
left -> pivot -> right
}
```
### list_concat
``` c
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
透過程式名稱不難猜出他的功用應該是把兩個 list 串接起來。我們只要找到 left list 的最後一個 node，把該 node 的 next 指向 right list 的 head 即可。因此這裡`LLL`應該要選`(c) left = &((*left)->next)`
## Pseudo Random generator
根據 [GNU C Library 文件](https://www.gnu.org/software/libc/manual/html_node/Pseudo_002dRandom-Numbers.html)說明，要修正輸出結果相仿的問題，可以透過給定不同的 seed value來達成。最常見的作法，便是使用執行程式當下的時間作為選擇 seed 的依據。
``` c
int getRandom() {
srand(time(NULL));
return rand();
}
```
## Optimized quicksort
在這份實作中，利用了 recursive 的形式。儘管程式可讀性不錯，但在反覆的 function call 時，效能相對較差，且需要存大量的資料進 stack，資料量大時可能會有 overflow 的可能。因此，這篇文章指出，可以試著改寫成 iterative 的形式。參考該篇文章的範例程式，改寫成下面這樣：
``` c
node_t *getNode(node_t *head, int cnt) {
node_t *cur = head;
while(cnt>0)
{
cur = cur->next;
cnt--;
}
return cur;
}
void quickSort(node_t *head, int elements) {
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
node_t *pivot;
beg[0]=0;
end[0]=elements;
while (i>=0) {
L=beg[i];
R=end[i]-1;
if (L<R) {
pivot=getNode(head, L);
if (i==MAX_LEVELS-1)
return;
while (L<R) {
while (getNode(head, R)->value>=pivot->value && L<R)
R--;
if (L<R)
{
getNode(head, L)->value=getNode(head, R)->value;
L++;
}
while (getNode(head, L)->value<=pivot->value && L<R)
L++;
if (L<R)
{
getNode(head, R)->value=getNode(head, L)->value;
R--;
}
}
getNode(head, L)->value=pivot->value;
beg[i+1]=L+1;
end[i+1]=end[i];
end[i++]=L;
}
else
i--;
}
return;
}
```
注意，這份程式尚未優化完全，getNode 真的是個~~爛到爆~~的寫法 :crying_cat_face:
主要是先搞懂 iterative 的邏輯(Recursive在可讀性上真的完勝)，附上網站截下原作者的說明圖以供參考
進一步優化的方法可以考慮 pointer to pointer、用 array 存取每個 item 的位置等。若 data structure 改為 doubly linked list，在尋找 node 的過程或許也會比較輕鬆，視真實使用情境(資料種類、資料量等)再選擇適合的優化。
Sign in with Wallet
Connect another wallet