# 2021q1 Homework1 (quiz1)
contributed by < `iLeafy11` >
###### tags: `linux2021`

## 作業描述

[作業要求](https://hackmd.io/@sysprog/SJlXFVMzMu)
### 重新完成 2021q1 第 1 週測驗
#### 資料結構
單向連結串列節點結構 Singly Linked List node structure

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

#### LLL=?

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

`list_concat` 為 list concatenate 的實作
如下圖：
:::info
`left` 的生命週期 (life cycle) 只存在於此 function 中，離開 function 後就會被消滅。
:::
首先我們會想要將左邊 list 的最後一格，`NULL` 的值變成 `right` 完成 list concatenate。所以 `while` 迴圈在做的事就是讓 `left` traverse 到達 list 的最尾端。

digraph {
    rankdir=UD
    node [shape=box]
    l [label="left"]
    l [style="dashed"]
    l -> A -> B -> C -> NULL
    {rank=same; A B C NULL right} 
}

我們為了要讓 left 指到正確的位置上，所以在 `while` 迴圈裡面，必須要將 `left` dereference，然後存取下一個節點，再取其 address value 並賦值回 `left`。
:::info
以下圖而言，我們要修改的值是 `C->next` 的值，所以要才取 `C->next` 的 address，因此答案就不可能會是

*left = (*left)->next;

:::
於是程式碼會是：

left = &(*left)->next;

digraph structs {
    rankdir=UD
    node [shape=box]
    l [label="left"]
    l [style="dashed"]
    A -> B -> C -> NULL
    l -> NULL
    {rank=same; A B C NULL right} 
}

最後當 `left` 指向 list 最尾端節點的下一個節點的 address (也就是 `NULL`)，就可以將 `left` dereference 並賦予其值 `right`。

digraph structs {
    rankdir=UD
    node [shape=box]
    l [label="left"]
    l [style="dashed"]
    A -> B -> C -> right
    l -> right
    {rank=same; A B C right} 
}

所以最終 `list_concat` 的程式碼如下：

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

#### AAA=? BBB=? CCC=?

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

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演算法**

Quicksort 首先會挑一個 `pivot` 出來，比 `pivot` 小的值通通擺在左邊，比 `pivot` 大的值會擺在右邊，然後重複此動作，遞迴左邊跟右邊。
底下 Wikipedia 有比較好的解釋：
:::info
1. 挑選基準值：從數列中挑出一個元素，稱為「基準」（pivot），
2. 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成，
3. 遞迴排序子序列：遞迴地將小於基準值元素的子序列和大於基準值元素的子序列排序。

from [Wikipedia](https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F)
:::
AAA 跟 BBB 在 `list_add_node_t` 裡面，而 `list_add_node_t` 做的事情就是在把比 `pivot` 小的值跟比 `pivot` 大的值分開。所以依題目要求以 ascending order，把比較小的值丟去左邊，比較大的值丟去右邊，然後注意傳遞參數的型態是指標的指標 pointer to pointer to `node_t`。
因此 AAA 跟 BBB 的答案就是 `&right` 以及 `&left`。
CCC 的答案則是有關遞迴完了之後將 `left` list 跟 `pivot` node 跟 `right` list 接起來。因為是從左邊接到右邊，所以答案就會是 `list_concat(&result, pivot); list_concat(&result, right);`
### 補齊 `qsort.c` 程式碼
發現原始題目中，尚有兩個函式還沒完成，於是自己簡單實作一下

`list_make_node_t`

static node_t *list_make_node_t(node_t *list, int entry) { /* to be modified */
    node_t *new_node = malloc (1 * sizeof(node_t));
    new_node->value = entry;
    new_node->next = list;
    return new_node;
}

`list_free`

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

之後，用 valgrind 檢測是否有 memory leak

$ gcc -o qsort qsort.c
$ valgrind --leak-check=full ./qsort

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

### Pseudorandom number generator
取代這段：

list = list_make_node_t(list, random() % 1024);

:::info
TODO
1. `include <time.h>` `srand(time(NULL));`
2. 嘗試實現一個 PRNG 並比較其亂度
e.g. [Xorshift](https://en.wikipedia.org/wiki/Xorshift)
:::
### Optimized QuickSort — C Implementation (Non-Recursive)
使用 iterative 比起 recursive 的 Quick Sort 來說，最直接的一點就是不會重複呼叫函式，在 C 語言中，呼叫一次函式都會再次複製傳入該函式的參數的值，速度通常不比 iterative 快。且多次呼叫函式也有可能會有 Stack overflow 的危險。
#### 堆疊 (stack)
使用堆疊 (stack) 實作 iterative quick sort。
堆疊 (stack) 選擇用 linked list 實作。
如果堆疊 (stack) 不用 linked list 實作，勢必要給堆疊 (stack) 制定一段固定大小空間，失去一定的彈性。
雖說抓取 `heap` 的記憶體也有可能會 `malloc failed`，且速度不比直接抓取 `stack` 的記憶體。不過如今已使用 linked list 實作 Quick Sort，我想，如果要用堆疊 (stack) 實現 iterative Quick Sort，那麼堆疊 (stack) 也應當要由 linked list 實作才是。
**`vector.c`**：

typedef struct __vnode {
    node_t *list;
    struct __vnode *next;
} vnode_t;

typedef struct __vector {
    vnode_t *top;
    bool (*isEmpty)(struct __vector *v);
    void (*push)(struct __vector *v, node_t *entry);
    node_t *(*pop)(struct __vector *v);
    void (*delete)(struct __vector *v);
} vector;

bool v_isEmpty(vector *v) 
{
    return (v->top == NULL);
}

void v_push(vector *v, node_t *entry) 
{
    if (!entry) return;
    vnode_t *new_vnode = malloc(sizeof(vnode_t));
    new_vnode->list = entry;
    new_vnode->next = v->top;
    v->top = new_vnode;
}

node_t *v_pop(vector *v) 
{
    if (v->isEmpty(v))
        return NULL;

    vnode_t *target = v->top;
    node_t *pop = target->list;
    v->top = target->next;
    free (target);
    target = NULL;
    return pop;
}

void v_delete(vector *v)
{
    if (v) {
        while (v->pop(v));
        free(v);
    }
}

vector *v_new() 
{
    vector *v = malloc(sizeof(vector));
    if (v) {
        v->top = NULL;
        v->isEmpty = v_isEmpty;
        v->push = v_push;
        v->pop = v_pop;
        v->delete = v_delete;
    }
    return v;
}

:::info
TODO: 程式碼附上解釋
:::
#### 用 Stack 來達成 QuickSort Iterative 的實作
`qsort_iterative.c`：

void quicksort_iterative(node_t **list) 
{
    if (!*list || !(*list)->next) 
        return;

    vector *v = v_new();
    v->push(v, *list);
    node_t *result = NULL;
    while (v->top) {
        node_t *pivot = v->pop(v);
        if (pivot->next) {
            node_t *left = NULL, *right = NULL;
            int value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add_node_t(n->value > value ? &right : &left, n);
            }
            v->push(v, left);
            v->push(v, pivot);
            v->push(v, right);
        } else 
            list_add_node_t(&result, pivot);        
    }
    *list = result;
    v->delete(v);
}

:::info
TODO: 附上更多解釋
:::
不使用 `list_concat` 是因為 `list_add_node_t` 本身是 $O(1)$ 。在 `while` 迴圈中，因為 list 裡面每個元素都會被走過，次數會被 `*n` 次，所以如果用 `list_concat` 可能最糟糕會達到 $O(n^2)$，不過這倒是跟 Quick Sort 的 worst case 一樣，或許影響沒有想像中來的大。

因為額外實作了一個用了 linked list 的堆疊(stack)，有額外動態配置記憶體，所以用一下 valgrind 檢查是否有 memory leak。

$ gcc -o qsort qsort.c
$ valgrind --leak-check=full ./qsort

==7658== Memcheck, a memory error detector
==7658== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7658== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==7658== Command: ./qsort
==7658== 
NOT IN ORDER : 580 747 735 861 37 612 206 179 269 763 156 809 830 11 697 1012 877 319 355 944 
    IN ORDER : 11 37 156 179 206 269 319 355 580 612 697 735 747 763 809 830 861 877 944 1012 
==7658== 
==7658== HEAP SUMMARY:
==7658==     in use at exit: 0 bytes in 0 blocks
==7658==   total heap usage: 55 allocs, 55 frees, 1,912 bytes allocated
==7658== 
==7658== All heap blocks were freed -- no leaks are possible
==7658== 
==7658== For lists of detected and suppressed errors, rerun with: -s
==7658== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

#### 使用 [XOR Linked List](https://en.wikipedia.org/wiki/XOR_linked_list) 實作，改善 Linked List 對於空間的佔用

:::info
TODO
:::

:::info
* tail call optimization

:::