# 2021q1 Homework (quiz1)
contributed by < [`bakudr18`](https://github.com/bakudr18)>
###### tags: `linux2021`
> [第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)

## 測驗 `1`
* `LLL` = ?
`(c) left = &((*left)->next)`
`left` 型態為 pointer to pointer to `node_t` ，因此需先 dereference 成 `node_t*` 才可以操作 `next` ，最後 `left` 會指向 address of `next`。

* `AAA` = ?
`(e) &right`
因輸出結果須為 ascending order ，故比 `pivot->value` 大的 `node` 放在右邊，最後注意 `list_add_node_t` 傳入的參數型態為 `node_t**`。
* `BBB` = ?
`(c) &left`
反之，比 `pivot->value` 小的放左邊，理由同上。
* `CCC` = ?
`(b) list_concat(&result, pivot); list_concat(&result, right)`
因為 `pivot` < `right` ，先連結 `pivot` 後再連結 `right`。

## 解釋程式運作原理，搭配 Graphviz 解說
### Quick sort
quick sort 是一種 [divide-and-conquer algorithm](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm)，先選擇一個 pivot ，然後比較各個 node 與 pivot 大小將 list 拆成 left 與 right ， 分別對 left , right 排序後，再依據 left -> pivot -> right 順序重新串接。

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` 會指向 `list` head。

digraph list {
    node [shape=box];
    list[shape=plaintext]
    head[shape=plaintext]
    pivot[shape=plaintext]
    {
        rank="same"
        a [label="74"];
        b [label="84"];
        c [label="61"];
        d [label="23"];
        e [label="99"];
        f [shape=plaintext label="NULL"];

    }
    {
        a->b->c->d->e->f
    }
    {
        list -> head -> a
        pivot -> a
    }
}

然後經過 `while(p)` 後會把 list 拆成 `left`, `right` 和 `pivot` 三組 list

digraph list {
    node [shape=box];
    pivot[shape=plaintext]
    left[shape=plaintext]
    right[shape=plaintext]
    {
        rank="same";
        a [label="74"];
        f [shape=plaintext label="NULL"];
        a->f
    }
    pivot -> a
    {
        rank="same";
        c [label="61"];
        d [label="23"];
        g [shape=plaintext label="NULL"];
        d->c->g
    }
    left->d
    {
        rank="same";
        b [label="84"];
        e [label="99"];
        h [shape=plaintext label="NULL"];
        e->b->h
    }
    right->e
}

接著分別對 `left` , `right` 做 `quicksort`

digraph list {
    node [shape=box];
    pivot[shape=plaintext]
    left[shape=plaintext]
    right[shape=plaintext]
    {
        rank="same";
        a [label="74"];
        f [shape=plaintext label="NULL"];
        a->f
    }
    pivot -> a
    {
        rank="same";
        c [label="61"];
        d [label="23"];
        g [shape=plaintext label="NULL"];
        d->c->g
    }
    left->d
    {
        rank="same";
        b [label="84"];
        e [label="99"];
        h [shape=plaintext label="NULL"];
        b->e->h
    }
    right->b
}

接著對 `left` 與 `pivot` 做 `list_concat`

digraph list {
    node [shape=box];
    result[shape=plaintext]
    right[shape=plaintext]
    {
        rank="same";
        a [label="74"];
        c [label="61"];
        d [label="23"];
        g [shape=plaintext label="NULL"];
        d->c->a->g
    }
    result->d
    {
        rank="same";
        b [label="84"];
        e [label="99"];
        h [shape=plaintext label="NULL"];
        b->e->h
    }
    right->b
}

最後再連結 `right`

digraph list {
    node [shape=box];
    result[shape=plaintext]
    {
        rank="same";
        a [label="74"];
        c [label="61"];
        d [label="23"];
        b [label="84"];
        e [label="99"];
        g [shape=plaintext label="NULL"];
        d->c->a->b->e->g
    }
    result->d
}

## 引入其他 Pseudorandom number generator
#TODO

## 重寫 quick sort ，避免使用遞迴呼叫
使用 iterative 寫法勢必要自行維護 stack ，原作法已經可以將 `list` 拆分成 `left` , `pivot` , `right` 三段 linked-list，為了讓 stack top 的 `list` 是較小值的 `list` 以符合 ascending order ， 因此推入順序會是 `right` 先，然後是 `pivot` ，最後是 `left`，然後在第二次迴圈繼續將 stack top 的 list 分段。 執行過程中的 stack 示意圖如下表示。

|       |            |            |
|       |            |------------|
|       |            |  subleft   | <- sp
|       |            |------------|
|       |            |  subpivot  |
|-------|            |------------|
| left  | <- sp      |  subright  |
|-------|            |------------|
| pivot |            |   pivot    |
|-------|            |------------|
| right |            |   right    |
---------            --------------

直到 stack top 的 sublist 只剩下一個 node 時，就代表這個 node 是 stack 中所有 node 中的最小值，此時才將 node 推入 result list 中。程式碼如下所示。

void quicksort(node_t **list)
{
#define MAX_LEVELS 600
    node_t *stk[MAX_LEVELS];
    node_t dummy;
    node_t *tail = &dummy;
    int sp = 0;
    
    stk[sp] = *list;
    while (sp >= 0) {
        node_t *pivot = stk[sp--];
        if (pivot->next) {
            node_t *left = NULL;
            node_t *right = NULL;
            node_t *p = pivot->next;
            pivot->next = NULL;
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add_node_t(n->value > pivot->value ? &right : &left, n);
            }

            if (right)
                stk[++sp] = right;
            stk[++sp] = pivot;
            if (left)
                stk[++sp] = left;
        } else {
            tail->next = pivot;
            tail = tail->next;
        }
    }
    *list = dummy.next;
}