# 2021q1 Homerork1 (quiz1)
contributed by < ch1p98 >

* [作業簡介網址](https://hackmd.io/DfTOkdDkRkeJfTnk0cVV0Q?view)

## :penguin:作業要求
重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)，附帶的「==延伸問題==」也需要完成
* 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
* 將你的共筆加到 [2021q1 Homework1 (作業區)](https://hackmd.io/@sysprog/linux2021-homework1)

## 第一週測驗題

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

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

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = 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;
}

* 這裡的quick sort設定該序列的首個元素為pivot，然後將之後的元素和pivot比值。
* 值比pivot小的話就放到左sublist，比pivot大的話就放到右sublist。
* 遞迴呼叫quick_sort，排序左右sublist。直到左右sublist大小皆<=1為止。這是屬於top-down的實作。