# 2021q1 Homework1 (quiz1)
contributed by < `vivi235711` >
###### tags: `linux`
> [J01: lab0](https://hackmd.io/@sysprog/linux2021-lab0)
> [GitHub](https://github.com/vivi235711/quiz1)

## linked list 的 Quick sort

### 1. 解釋程式運作原理

:::info
- 單向 linked list，已知不存在 circular (環狀結構)
- 依據遞增順序進行 Quick sort
:::

#### linked list

定義結構

digraph __node{
        node[shape=record]       
        node_t [label="<f0> address|<f1> value|<f2> *next"];
}

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

增加node到list上
before:

digraph __node{
    node[shape=record]
    list [label="<f0> list**|<f1> b"]    
}

digraph __node{
    node[shape=record]    
    node_t [label="<f0> a|<f1> node_t|<f2> NULL"]
    old_head [label="<f0> b|<f1> old head|<f2> *next"]; 
}

after:

digraph __node{
    node[shape=record]
    list [label="<f0> list**|<f1> a"]    
}

digraph __node{
    node[shape=record]    
    node_t [label="<f0> a|<f1> node_t|<f2> b"]
    old_head [label="<f0> b|<f1> old head|<f2> *next"]; 
    node_t:f2 -> old_head:f0
}

- 傳 **list 進來，改變 list 指向的 node ， **list 不變

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

合併 (concatenate) 合併左邊與右邊的序列

digraph __node{
    node[shape=record]       
    a [label="<f0> left0|<f1> "]
    b [label="<f0> left1|<f1> "]
    a:f1 -> b:f0
    c [label="<f0> left tail|<f1>"]
    b:f1 -> c:f0[style=dotted]
    d [label="<f0> right0|<f1> "]
    c:f1 -> d:f0[color=red]
}

- whihe 迴圈直到左邊 list 的尾端的 *next(NULL)，再把NULL的值改為右邊list的地址。
- 11 行的 left 是指標，(*left) 是 node ，把 left 指向下一個 node 的地址，因此要加 &()

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

#### Quick sort

Divide and conquer : 將問題切割成數個子問題，直到子問題可輕易求解，合併解即為原問題的解答

1. 從 list 裡選一個 pivot
2. 將 list 分成比 pivot 小與比 pivot 大的兩邊，小的在前大的在後 (以遞增為例)
3. 前後兩個 list 也遞迴進行上述步驟，直到 list 內的個數只有 0 或 1 個

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

- 28 行 : list_add_node_t(n->value > value ? &right : &left, n)
先看list_add_node_t 接收的值
list_add_node_t(node_t **list, node_t *node_t)
- 當 node value > pivot 的時候，將 node 分到 right，否則分到 left，需要傳入 **list，因此需要 &left, &right

對應的測試程式如下:

node_t *list_make_node_t(node_t *list, int num) {
    node_t *item = (struct __node *)malloc(sizeof(node_t));
    item->value = num;
    item->next = NULL;
    list_add_node_t(&list, item);
    return list;
} 
static bool list_is_ordered(node_t *list) {
    bool first = true;
    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

static void list_display(node_t *list) {
    printf("%s IN ORDER : ", list_is_ordered(list) ? "   " : "NOT");
    while (list) {
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}

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

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

結果為


有排序成功

:::warning
但結果都相同
:::

### 2. Pseudorandom number generator

### 3. Non-Recursive Quicksort