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

> [2021q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
> [GitHub](https://github.com/tigger12613/quiz1)

## 作業要求
- [x] 1. 解釋程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現
- [x] 1.1 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
- [x] 2. 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
- [ ] 3. Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- [ ] 4. 研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中

## 在電腦上重現程式
quiz 缺少兩個函式，予以實作

static node_t *list_make_node_t(node_t *list, long num) {
    node_t *tmp = malloc(sizeof(node_t));
    if (!tmp) {
        return list;
    }
    tmp->value = num;
    tmp->next = list;
    return tmp;
}

static void list_free(node_t **list) {
    node_t *tmp;
    while (*list) {
        tmp = *list;
        *list = (*list)->next;
        free(tmp);
    }
}

運作正常

$ valgrind --leak-check=full ./link_list 
==45637== Memcheck, a memory error detector
==45637== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==45637== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==45637== Command: ./link_list
==45637== 
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 
==45637== 
==45637== HEAP SUMMARY:
==45637==     in use at exit: 0 bytes in 0 blocks
==45637==   total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated
==45637== 
==45637== All heap blocks were freed -- no leaks are possible
==45637== 
==45637== For lists of detected and suppressed errors, rerun with: -s
==45637== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

## 程式運作過程

### Main
產生長度為 20 的 linked list 並隨機給予 0 ~ 1023 的數值，列印 linked list ，排序，再列印 linked list ，確認排序是否正確，free linked list

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;
}

### List add node
將節點插入 list 的頭部

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

digraph a {
    rankdir=LR;
    node[shape=box];
    "node"->"head"
    "head"->"..."
    "..."->"tail"
}

### List concat
將 right list 鏈結在 left list 後面

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}

digraph a {
    rankdir=LR;
    node[shape=box];
    node1 [label = "..."]
    "left"->"..."
    "..."->"left tail"
    "left tail" -> "right"[color = red label="concat"]
    "right"->node1
    node1->"right tail"
}

### Quick sort

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;
}

這段用於把 pivot 拆出來

node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

while loop 把比 pivot 大的放到 right list 上面，小或等於的放到 list list 上面

while (p) {
    node_t *n = p;
    p = p->next;
    list_add_node_t(n->value > value ? &right : &left, n);
}

digraph sort{
    rankdir=LR;
    node[shape=box];
    right
    left
    pivot
    n1 [label = "> pivot"]
    n2 [label = " <= pivot"]
    right-> n1
    left->n2
}

接下來排序 left list and right list ，然後接起來

quicksort(&left);
quicksort(&right);

node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot); list_concat(&result, right);
*list = result;

digraph sort{
    rankdir=LR;
    node[shape=box];
    right
    result
    pivot
    {
        rank = same
        left -> lleft
    }
    
    lright [label = " sorted and > pivot"]
    lleft [label = " sorted and <= pivot"]
    {
        rank = same
        right-> lright
    }
    lleft->pivot [label = "concat" color = "red"]
    pivot->lright [label = "concat" color = "red"]
    result->lleft
    
}

### 隨機種子
加上隨機種子在使用 random() 之前就可以每一次都產生不同的隨機數

srand(time(NULL));

PRNG 使用初始值產生一串帶有隨機性質的數字序列，如果初始值相等，序列也會相等，因此不是真隨機。在使用時使用 time 作為初始值可以讓初始值看似隨機數，產生的數字序列也會看起來隨機。
:::warning
倘若 time 函式得到的時間數值是可預測的話，PRNG 的輸出也可預測，該如何改進？留意到 entropy 相關討論
:notes: jserv
:::

## Iterative quicksort

新增一個 stack 用於紀錄還未排序的 linked list
sorted 紀錄已經排序好的範圍
每次 loop 從 stack 中最右邊的 linked list 進行切分，如果只有一個節點，代表這個節點是 stack 上數值最大的節點，並且小於等於 sorted 鏈上的每一個節點，所以將其放到 sorted 鏈 的第一個上，然後從 stack 上移除($i--$)，持續重複這個過程直到 stack 為空。

void quicksort_iterative(node_t **list)
{
    #define  MAX_LEVELS  1000
    if (!*list)
        return;
    int i = 0, j = 0;
    node_t *stack[MAX_LEVELS];
    node_t *sorted;
    sorted = NULL;
    stack[0] = *list;
    while(i>=0 && i<MAX_LEVELS){
        if(!stack[i]){
            i--;
            continue;
        }
        if(!stack[i]->next){
            stack[i]->next = sorted;
            sorted = stack[i];
            i--;
            continue;
        }
        node_t *pivot = stack[i];
        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);
        }
        stack[i] = left;
        stack[i+1] = pivot;
        stack[i+2] = right;
        i +=2;
    }
    *list = sorted;
}

接著對效能測試，重複 5000 次對長度 1000 的 list 做排序
iterative 版本快了46% 的速度
| recursive version | iterative version |
| ----------------- | ----------------- |
| 0.832864 sec | 0.567636 sec |

`MAX_LEVELS`的數值選擇應該考慮到 worst case 的狀況，如果每一次的 pivot 都選到最小的那一個 也就是說 left 都為 NULL ，也就是需要 $2 \times (n-1)$ 個位置去儲存 linked list node

digraph {
        node [color=black shape=none margin=0 height=.3 ]
        values [label=<
                     <table border="0" cellborder="1" cellspacing="0">
                        <tr>
                            <td port="f0" bgcolor = "lightyellow">  NULL </td>
                            <td port="f1" bgcolor = "lightyellow">  pivot1 </td>
                            <td port="f2" bgcolor = "lightyellow">  NULL </td>
                            <td port="f3" bgcolor = "lightyellow">  pivot2 </td>
                            <td port="f4" bgcolor = "lightyellow">  ... </td>
                            <td port="f5" bgcolor = "lightyellow">  NULL </td>
                            <td port="f6" bgcolor = "lightyellow">  pivot_end </td>
                            <td port="f7" bgcolor = "lightyellow">  right_end </td>
                        </tr>
                    </table>
                        >];
                        "stack"->values:f0
                        { rank=same; "stack"; values }
    }

:::warning
`MAX_LEVELS` 數值設定的依據為何？做數學分析來指定更適切的數值。
:notes: jserv
:::