---
# System prepended metadata

title: 2021q1 Homework1 (quiz1)
tags: [sysprog2021]

---

# 2021q1 Homework1 (quiz1)
contributed by < `wiasliaw` >

###### tags: `sysprog2021`

## 進度

- [x] 重新回答並解釋運作原理
- [ ] 測試程式使用到 random，請修正「輸出結果相仿」
- [ ] 參考 Optimized QuickSort，並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
- [ ] 請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- [ ] 研讀 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法並落實於上述 (3) 的程式碼中

## 隨堂測驗

### list_concat

```c=
static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}
```
:::info
* 作答
    * 從 while 迴圈和函式命名可以知道要讓 left 指向到 list 的最末端，所以選 `left = &((*left)->next)`
:::

將兩個 linked list 串接起來

* 首先看一下原本的 left 跟 right

```graphviz
digraph list_concat {
    rankdir=LR;
    node [shape=record];
    l0 [label="{<data>L0|<ref>}"];
    l1 [label="{<data>L1|<ref>}"];
    l2 [label="{<data>L2|<ref>}"];
    lNULL [label="NULL",shape=plaintext];
    left [label="left",shape=plaintext];
    r0 [label="{<data>L0|<ref>}"];
    r1 [label="{<data>L1|<ref>}"];
    r2 [label="{<data>L2|<ref>}"];
    rNULL [label="NULL",shape=plaintext];
    right [label="right",shape=plaintext];

    left->l0;
    l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
    l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
    l2:ref:to -> lNULL [arrowtail=dot, dir=both, tailclip=false];
    right->r0;
    r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
    r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
    r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```

* 第 2 到 3 行: 將 left 指向到 linked list 的尾端

```graphviz
digraph list_concat {
    rankdir=LR;
    node [shape=record];
    l0 [label="{<data>L0|<ref>}"];
    l1 [label="{<data>L1|<ref>}"];
    l2 [label="{<data>L2|<ref>}"];
    lNULL [label="NULL",shape=plaintext];
    left [label="left",shape=plaintext];
    r0 [label="{<data>L0|<ref>}"];
    r1 [label="{<data>L1|<ref>}"];
    r2 [label="{<data>L2|<ref>}"];
    rNULL [label="NULL",shape=plaintext];
    right [label="right",shape=plaintext];

    left->lNULL;
    l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
    l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
    l2:ref:to -> lNULL [arrowtail=dot, dir=both, tailclip=false];
    right->r0;
    r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
    r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
    r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```

* 第 4 行: 將 right 接在 left 的末端

```graphviz
digraph list_concat {
    rankdir=LR;
    node [shape=record];
    l0 [label="{<data>L0|<ref>}"];
    l1 [label="{<data>L1|<ref>}"];
    l2 [label="{<data>L2|<ref>}"];
    left [label="left",shape=plaintext];
    r0 [label="{<data>L0|<ref>}"];
    r1 [label="{<data>L1|<ref>}"];
    r2 [label="{<data>L2|<ref>}"];
    rNULL [label="NULL",shape=plaintext];
    right [label="right",shape=plaintext];

    left->r0;
    l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
    l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
    l2:ref:to -> r0 [arrowtail=dot, dir=both, tailclip=false];
    right->r0;
    r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
    r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
    r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```

### 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;
}
```
:::info
* 作答
    * 從三元運算子可知比 pivot 大的要放進 AAA; 小的要放進 BBB，但是從第 22 行可以知道 left 是接在 list 前面，所以要放比 pivot 小的 node，所以 BBB 應為 `&left`，AAA 應為 `&right`。
    * 串接完 left 後，再來需要先接上 pivot，最後才接 right，故選 `list_concat(&result, pivot);list_concat(&result, right)` 
:::

:::danger
不要用「選擇」的思維作答，選擇題只是便於授課教師批改，你應該設想「如果要我憑空撰寫程式，該怎麼做？」
:notes: jserv
:::

實作 quick sort 演算法將 linked list 排序

1. 第 3 行: 確保 list 不是 NULL，假設原本的 list 如下

```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    list [label="list",shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    list->l0
    l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
    l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
    l2:ref:to -> l3:data [arrowtail=dot, dir=both, tailclip=false];
    l3:ref:to -> l4:data [arrowtail=dot, dir=both, tailclip=false];
}
```

2. 第 6 到 10 行:
    * 取出 list 中第一個節點作為 pivot
    * 剩下的 list 存於變數 `p`

```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    list [label="p",shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    pivot [label="pivot",shape=plaintext];
    
    pivot -> l0;
    list->l1
    l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
    l2:ref:to -> l3:data [arrowtail=dot, dir=both, tailclip=false];
    l3:ref:to -> l4:data [arrowtail=dot, dir=both, tailclip=false];
}
```

3. 第 11 行: 建立兩個 linked list，用於儲存與 pivot 的值比較後的結果

```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    left[label="left", shape=plaintext];
    right[label="right", shape=plaintext];
    lNULL[label="NULL",shape=plaintext];
    rNULL[label="NULL",shape=plaintext];
    left -> lNULL;
    right -> rNULL;
}
```

4. 第 12 到 16 行:
    * 依序取出 list `p` 的 node，並和 pivot 比較
    * 較大的放入 right，較小的放入 left

```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    pivot[label="pivot", shape=plaintext];
    left[label="left", shape=plaintext];
    right[label="right", shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    pivot->l0;
    left->l1;
    right->l2;
    l1->l3[arrowtail=dot, dir=both, tailclip=false]
    l2->l4[arrowtail=dot, dir=both, tailclip=false];
}
```

5. 第 18 到 19 行:
    * 將已經拆開的 left 和 right 也執行 `quicksort`
    * 以 right 為例重複步驟 1-4，left 以此類推

```graphviz
digraph quicksort {
    label="Right'";
    labelloc="t";

    rankdir=LR;
    node [shape=record];
    pivot[label="pivot'", shape=plaintext];
    left[label="left'", shape=plaintext];
    right[label="right'", shape=plaintext];
    l2 [label="{<data>5|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    NULL[label="NULL",shape=plaintext];

    pivot->l2;
    left->l4;
    right->NULL;
}
```

6. 第 21 到 24 行: 將執行完 quicksort 的 left 和 right 與 pivot 串接起來

先執行 Right'，會得到新的 right
```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    pivot[label="pivot", shape=plaintext];
    left[label="left", shape=plaintext];
    right[label="right", shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    pivot->l0;
    left->l1;
    right->l4;
    l1->l3[arrowtail=dot, dir=both, tailclip=false]
    l4->l2[arrowtail=dot, dir=both, tailclip=false];
}
```

再來將 left, pivot 和 right 串接起來
```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    pivot[label="pivot", shape=plaintext];
    left[label="left", shape=plaintext];
    right[label="right", shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    pivot->l0;
    left->l1;
    right->l4;
    l1->l3[arrowtail=dot, dir=both, tailclip=false];
    l4->l2[arrowtail=dot, dir=both, tailclip=false];
    l3->l0[arrowtail=dot, dir=both, tailclip=false];
    l0->l4[arrowtail=dot, dir=both, tailclip=false];
}
```

7. 第 25 行: 更新 list

```graphviz
digraph quicksort {
    rankdir=LR;
    node [shape=record];
    left[label="list", shape=plaintext];
    l0 [label="{<data>3|<ref>}"];
    l1 [label="{<data>1|<ref>}"];
    l2 [label="{<data>5|<ref>}"];
    l3 [label="{<data>2|<ref>}"];
    l4 [label="{<data>4|<ref>}"];
    
    left->l1;
    l1->l3[arrowtail=dot, dir=both, tailclip=false];
    l4->l2[arrowtail=dot, dir=both, tailclip=false];
    l3->l0[arrowtail=dot, dir=both, tailclip=false];
    l0->l4[arrowtail=dot, dir=both, tailclip=false];
}
```

---

## random

* 從 [random](https://linux.die.net/man/3/random) 的文件可以得知，如果沒有提供 seed，會自動設定 seed 為 1。

> These sequences are repeatable by calling srandom() with the same seed value. If no seed value is provided, the random() function is automatically seeded with a value of 1.

* 可以用 `srandom(time(NULL))` 提供 seed，但是 `time()` 回傳的是從 1970 年 1 月 1 號到現在的秒數，所以如果在同一秒執行多次的話還是會發現相同的輸出結果。
    * [time() Reference](https://en.cppreference.com/w/c/chrono/time)
    * [time_t reference](https://en.cppreference.com/w/c/chrono/time_t)
:::warning
為何是 1970 年呢？能否從歷史淵源探討這數值的設定？
:notes: jserv
:::
:::info
在 [Wikipedia](https://en.wikipedia.org/wiki/Unix_time#History) 上由提及最初的定義是從第一版「Unix Programmer's Manual」中，將 Unix 時間定義為「自 1971 年 1 月 1 日起，以六十分之一秒為單位」。這樣設計是為了符合當時 Unix 系統上的 clock rate。但是這樣設計 32 bit 的有號整數只能表示約 2.5 年。
\
${\frac{2^{32}}{60*60*60*24*365}\approx 2.25...}$
\
由於範圍有限，Unix 時間重新定義為「以一秒為一單位，並設定 1970 年 1 月 1 日為 0」。

:warning: 除了只從 Wikipedia 擷取字面描述，你嘗試研讀當時硬體規格和推測 clock rate 行為嗎？任何人 (扣除中國人) 都可查閱 Wikipedia 並複製貼上，高等教育不能只做到這樣。追根究底！
:notes: jserv
:::

* 為了修正這個問題，可以用 [entropy](https://en.wikipedia.org/wiki/Entropy_(computing)) 作為 seed。如何產生一個 entropy，我找到 `getentropy()` 或是 `getrandom()`，可以跟 Linux kernel 取得亂數。
    * [初探 Linux kernel 亂數產生器](https://szlin.me/2016/10/05/%E5%88%9D%E6%8E%A2-linux-kernel-%E4%BA%82%E6%95%B8%E7%94%A2%E7%94%9F%E5%99%A8-random-generator/)
    * [getrandom(2) — Linux manual page
](https://man7.org/linux/man-pages/man2/getrandom.2.html)
    * [getentropy(3) — Linux manual page](https://man7.org/linux/man-pages/man3/getentropy.3.html)

:::warning
請問教授，我知道 `random` 是根據 LCG 實作，「引入其他 Pseudorandom number generator」，是指實作其他的 PRNG 演算法嗎？例如：[The Rust Rand Book](https://rust-random.github.io/book/guide-rngs.html) 上面列出的。
> 是，若能進行數學分析更好
> :notes: jserv
:::

---

## Optimized QuickSort

下方[程式碼](https://alienryderflex.com/quicksort/)出處

```cpp=
bool quickSort(int *arr, int elements)
{
#define MAX_LEVELS 1000

    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 false;
            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 true;
}
```

:::warning
提及上方程式碼的出處，及其目標
:notes: jserv
:::


為了了解程式運作，我在 `quickSort` 裡面值入 `printf` 以得到值會迴圈後對 arr 的改變。以下為程式碼，以及其對應輸出。

```c=
void print_arr(int *arr, int elements, char c)
{
    printf("Arr(%c): ", c);
    for (int i = 0; i < elements; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

bool quickSort(int *arr, int elements)
{
#define MAX_LEVELS 1000

    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 false;
            printf("P:%d L:%d R:%d\n", piv, L, R);
            print_arr(arr, elements, 'I');
            while (L < R) {
                while (arr[R] >= piv && L < R)
                    R--;
                if (L < R)
                    arr[L++] = arr[R];
                print_arr(arr, elements, 'R');

                while (arr[L] <= piv && L < R)
                    L++;
                if (L < R)
                    arr[R--] = arr[L];
                print_arr(arr, elements, 'L');
            }
            arr[L] = piv;
            beg[i + 1] = L + 1;
            end[i + 1] = end[i];
            end[i++] = L;
            print_arr(arr, elements, 'F');
        } else {
            i--;
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    int arr[] = {4, 5, 2, 1, 3};
    int n = 5;
    quickSort(arr, n);
    return 0;
}
```

```=
P:4 L:0 R:4
Arr(I): 4 5 2 1 3 
Arr(R): 3 5 2 1 3 
Arr(L): 3 5 2 1 5 
Arr(R): 3 1 2 1 5 
Arr(L): 3 1 2 1 5 
Arr(F): 3 1 2 4 5 
P:3 L:0 R:2
Arr(I): 3 1 2 4 5 
Arr(R): 2 1 2 4 5 
Arr(L): 2 1 2 4 5 
Arr(F): 2 1 3 4 5 
P:2 L:0 R:1
Arr(I): 2 1 3 4 5 
Arr(R): 1 1 3 4 5 
Arr(L): 1 1 3 4 5 
Arr(F): 1 2 3 4 5 
```

根據輸出以及[網站](https://alienryderflex.com/quicksort/)，可以得知
* 第 27 行的 while 迴圈作用在調整陣列，將陣列分成比 pivot 大與比 pivot 小兩個部份。
* `beg` 和 `end` 兩個陣列紀錄了下一次調整陣列的範圍
* pivot 則是取在 `beg` 和 `end` 間的第一個

:::warning
TODO:
* graphviz 代補
* rewrite quicksort
:::

