# 2024q1 Homework2 (quiz1+2)
contributed by < [`ICARUSHERALD96500`](https://github.com/ICARUSHERALD96500) >
## [第一週測驗](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)
### 測驗一
**Optimized QuickSort — C Implementation (Non-Recursive)**
#### **Q1.解釋上述程式碼的運作原理，提出改進方案並予以實作。**
Linked list 在 Quick sort 的作法：
step 1. 首先假設開頭 head 為 pivot。
step 2. `L` 從Linked list 的頭開始逐步向尾走訪，尋找比 pivot 大的值。同時，`R` 從尾向頭逐步走訪，尋找比 pivot 小值

digraph structs {
    splines = false;
    
    node[shape = "plaintext"]
    pivot [label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td port="m">pivot</td></tr>
    <tr><td port="n">next</td></tr>
    </table>>];
    
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    "begin[0]" [fontcolor="blue"];
    "end[0]" [fontcolor="blue"];
    
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }

    pivot -> L -> "begin[0]"-> struct0;
    R -> "end[0]" -> struct4;

}

digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>list_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_1[
        weight = 10, style = invis
    ]
    
    list_head:n -> node_1:m;
    node_1:p -> list_head:n;
    
    node_1:n -> NULL;
}

* **結構體**
::: spoiler 程式碼

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

:::
宣告結構體 `node_t` ，包含三個指向另一節點 `node` 的指標、型別為 `long` 的變數，指標 `left`, `right` 分別指向 `begin`, `end` 兩個堆疊，指標 `next` 則指向資料鍊結的下個節點。

digraph G {
    splines = true;
    
    node[shape = "plaintext"]
    
    // begin 節點
    struct[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="2"><b>node_t</b></td></tr>
    <tr><td port="left">left</td><td port="right">right</td></tr>
    <tr><td colspan="2" port="next">next</td></tr>
    <tr><td colspan="2" port="value">value</td></tr>
    </table>>];
    }

:::info
問題：不知道 `left` 、 `right` 的作用
:::
* **新增節點** `void list_add(node_t **list, node_t *node_t)`
::: spoiler 程式碼

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

:::
宣告一個 indirect pointer, 與儲存 `node_t` 節點位址的指標 `*node_t` ，共兩個引數。
`node_t->next = *list` 將節點的 `next` 所指向的位址赴值為 indirect pointer `**list` 最終所指向的相同位置。 也就是 `list` 所指向的位址與 `node_t` 所指相同。這裡我不免疑惑為什麼要把指標的變數名稱命名與結構體所使用的型別相同，都命名為 `node_t` ？

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // list node 
    node_list[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>list </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    // node 1
    node1[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>node_1</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>>];
    node_null [label="Null"]
    {rank = same; node_list node1 node_null}
    node_list:value:e -> node1:n
    node1:next:e -> node_null:n
    
    //node_t
    node_t[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>node_t </b></td></tr>
    <tr><td colspan="1" port="value" color="red">addr</td></tr>
    </table>> color=blue];
    //node 2
    node2[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>node_2</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next" color="red">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>> color=blue];
    // node another
    node_another[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>another node</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>>];                        
    node_null [label="Null"]
    {rank = same; node_t node2 node_another}
    node_t:value:e -> node2:n;
    node2:next:e -> node_another:n
    }

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // argc 1 
    node_list[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>list </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node1[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>node_1</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>>];
    node_null [label="Null"]

    
     // argc 1 
    node_t[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>node_t </b></td></tr>
    <tr><td colspan="1" port="value" color="red">addr</td></tr>
    </table>> color="blue"];
    
    node2[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>node_2</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next" color="red">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>> color="blue"];
    node_null [label="Null"]
    
    node_another[label = <<table border="0" cellborder="1" cellspacing="0">
                            <tr><td colspan="2"><b>another node</b></td></tr>
                            <tr><td port="left">left</td>
                            <td port="right">right</td></tr>
                            <tr><td colspan="2" port="next">next</td></tr>
                            <tr><td colspan="2" port="value">value</td></tr>
                        </table>>]; 
                        
    {rank=same; node_list node_t node2 node1 node_null}
    node_t -> node2:n
    node_list:value:e -> node2:n ;
    node2:next:e -> node1:n ;
    node1:next:e -> node_null:n
}

:::success
**指標的指標**：在 `list_add` 當中第一個引數為 `**list` a pointer to a pointer to a node。這樣作的目的是因為其需要修改 node2 原先所指向 another node 的指標，將其指向 node1，因此最於，指向 node2 的指標 `list` 而言，需要訪問 node2 結構體中的指標 `next`。故為指標的指標。
:::
* **取得節點尾端位址**
::: spoiler 程式碼

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

:::

該函是在間接指標所指向節點的前面插入另一節點，在間接指標所指向位址，且所指節點下一節點皆不為空時，while成立，將間接指標 `left` 賦值為 `(*left)->next` i.e.`AAAA` = `(*left->next)` ，也就是將 `left` 所指移動到下個節點。直到下一節點 `(*left)->next` 為空，退出while，故得到鍊結尾端位址。
* **取得鏈結串列長度**
::: spoiler 程式碼

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

:::
用間接指標所指位址不為空時，變數 `n` 增加1，並將間接指標移動到下一節點，故 `BBBB` 為 `(*left)->next` 。

* **新增鍊結串列節點並賦值**
::: spoiler 程式碼

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->value = n;
    return node;
}

:::
傳入兩個引數，分別為所要在之前新增節點 `list_head` 的位址與所要賦值整數變數 `n`，首先利用 `malloc` 配置 `node_t` 大小的記憶體位址，將該節點的 `next` 指向 `list` 所指的位址，再為`node` 除存的變數賦值。有疑問的是所賦值的型別為整數，與開始結構體宣告 `value` 的型別為 `long` 不同，這樣的結構體是否有浪費記憶體配置的疑慮？
* **釋放鍊結串列記憶體配置**
::: spoiler 程式碼

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

:::
輸入引數為間接指標所指鍊結串列 `head` 的位址，因為當節點被釋放後就無法指向下一節，首先新增一個節點儲存被釋放的節點的下一節點位址，當間接指標所指不為空時， `free` 釋放該節點，後將該只標重新賦值圍下一節點的位址。當一節點不為空時，將 `node` 更新為下一節點的位址。
* **檢驗是否為單調增**
::: spoiler 程式碼

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

:::
函式引數為 `head` 位址，函式中宣告布林值 `first` 紀錄是否為 `list head`，首先輸入`*list`為鍊結開頭，將該節點所存值賦值給在函式中所宣告變數 `value`，接著將 `list` 移動到下一節點。

`quick_sort` 函式初始化：

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // begin[0] 節點
    node_begin[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>begin[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // indirect pointer 節點
    node_indir[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>indir</b></td></tr>
    <tr><td colspan="1" port="value">head_addr</td></tr>
    </table>>];
    // head 節點
    node_head[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>head</b></td></tr>
    <tr><td colspan="1" port="value">address</td></tr>
    </table>>];    
    {rank = same ;node_indir node_head}
    
    node_indir:value:e -> node_head:n ;
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    node_head:value:e -> struct0:n
    node_begin:value -> struct0:n
    node_end:value -> struct4:n
    {rank = same; node_head struct0}
}                    

進入 `while (i>=0)` , `i=0` 時：

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // begin[0] 節點
    node_begin[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>begin[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // L 節點
    node_L[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>L</b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // indirect pointer 節點
    node_indir[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>indir</b></td></tr>
    <tr><td colspan="1" port="value">head_addr</td></tr>
    </table>>];
    // head 節點
    node_head[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>head</b></td></tr>
    <tr><td colspan="1" port="value">address</td></tr>
    </table>>];    
    {rank = same ;node_indir node_head}
    
    node_indir:value:e -> node_head:n ;
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    node_head:value:e -> struct0:n
    node_begin:value -> struct0:n
    node_L:value -> struct0:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    {rank = same; node_head struct0}
}                    

當 `L`、`R` 不是指向同一個鏈結串列節點時：

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // begin[0] 節點
    node_begin[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>begin[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // L 節點
    node_L[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>L</b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // pivot 節點
    node_pivot[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>pivot </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // indirect pointer 節點
    node_indir[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>indir</b></td></tr>
    <tr><td colspan="1" port="value">head_addr</td></tr>
    </table>>];
    // head 節點
    node_head[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>head</b></td></tr>
    <tr><td colspan="1" port="value">address</td></tr>
    </table>>];    
    {rank = same ;node_indir node_head}
    
    node_indir:value:e -> node_head:n ;
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    node_head:value:e -> struct0:n
    node_begin:value -> struct0:n
    node_L:value -> struct0:n
    node_pivot -> struct0:n
    node_p:value -> struct1:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    {rank = same; node_head struct0}
}                    

接著斷開 pivot 所指向的佇列節點與其他鏈結串列的連結：

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // begin[0] 節點
    node_begin[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>begin[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // L 節點
    node_L[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>L</b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // pivot 節點
    node_pivot[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>pivot </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // indirect pointer 節點
    node_indir[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>indir</b></td></tr>
    <tr><td colspan="1" port="value">head_addr</td></tr>
    </table>>];
    // head 節點
    node_head[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>head</b></td></tr>
    <tr><td colspan="1" port="value">address</td></tr>
    </table>>];    
    {rank = same ;node_indir node_head}
    
    node_indir:value:e -> node_head:n ;
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    node_head:value:e -> struct0:n
    node_begin:value -> struct0:n
    node_L:value -> struct0:n
    node_pivot -> struct0:n
    node_p:value -> struct1:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    {rank = same; node_head struct0}
    
    node[shape = plaintext]
    struct0 -> Null
    {rank = same;struct0 Null}
}                    

當 `p` 指向任一節點時，由 `n` 承接 `p` 原來指向的節點，`p` 指向下一節點：

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    
    // begin[0] 節點
    node_begin[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>begin[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // L 節點
    node_L[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>L</b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // pivot 節點
    node_pivot[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>pivot </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // indirect pointer 節點
    node_indir[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>indir</b></td></tr>
    <tr><td colspan="1" port="value">head_addr</td></tr>
    </table>>];
    // head 節點
    node_head[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>head</b></td></tr>
    <tr><td colspan="1" port="value">address</td></tr>
    </table>>];    
    {rank = same ;node_indir node_head}
    
    node_indir:value:e -> node_head:n ;
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    node_head:value:e -> struct0:n
    node_begin:value -> struct0:n
    node_L:value -> struct0:n
    node_pivot -> struct0:n
    node_p:value -> struct2:n
    node_n:value -> struct1:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    {rank = same; node_head struct0}
    
    node[shape = plaintext]
    struct0 -> Null
    {rank = same;struct0 Null}
}                    

比較 `n` 所指向的值與 `pivot` 所指向的值大小。若大於 `pivot` 則，加入 `right`鍊結中;小於則加入 `left` 中。直到 `p` 指向 `null`

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    
    node_p:value -> struct2:n
    node_n:value -> struct1:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 Null}
    node_left:value -> Null
    node_right:value -> struct1:w
    
}                    

`n` 繼續移動至下一節點，並判斷 3 小於 `pivot` 的 4，因此使用 `list_add()`將 其加入 `left` 的鍊結串列中

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> node_Null
    }
    
    node_p:value -> struct3:n
    node_n:value -> struct2:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 Null}
    node_left:value -> Null
    node_right:value -> struct1:w
    
}                    

判斷 `list_add(n->value > value ? &right : &left, n);`

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        // struct2 -> node_Null
        struct3 -> struct4
        struct4 -> node_Null
    }
    
    node_p:value -> struct3:n
    node_n:value -> struct2:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    struct2:e -> Null:s
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 struct2 Null}
    node_left:value -> struct2
    node_right:value -> struct1:n
    
}                    

`n`、`p` 向下一節點移動

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        // struct2 -> node_Null
        struct3 -> struct4
        struct4 -> node_Null
    }
    
    node_p:value -> struct4:n
    node_n:value -> struct3:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    struct2:e -> Null:s
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 struct2 Null}
    node_left:value -> struct2
    node_right:value -> struct1:n
    
}                    

判斷 `list_add(n->value > value ? &right : &left, n);`

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        // struct2 -> node_Null
        struct3 -> struct2
        struct4 -> node_Null
    }
    
    node_p:value -> struct4:n
    node_n:value -> struct3:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    struct2:e -> Null:s
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 struct2 Null}
    node_left:value -> struct3
    node_right:value -> struct1:n
}                    

`n`、`p` 向下一節點移動

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        // struct2 -> node_Null
        struct3 -> struct2
        struct4 -> node_Null
    }
    
    node_p:value -> node_Null
    node_n:value -> struct4:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1:s -> Null
    struct2:e -> Null:w
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 struct2 Null}
    node_left:value -> struct3
    node_right:value -> struct1:n
    
}                    

判斷 `list_add(n->value > value ? &right : &left, n);`

digraph G {
    splines = true;  
    node[shape = "plaintext"]
    // p 節點
    node_p[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>p </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // n 節點
    node_n[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>n </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // R 節點
    node_R[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>R </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // end[0] 節點
    node_end[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>end[0] </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    node[shape=box];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    node_Null [shape=plaintext, label="Null"];
    {
        rank="same";
        // struct0 -> struct1
        // struct2 -> node_Null
        struct3 -> struct2
        struct4 -> struct3
    }
    
    node_p:value -> node_Null
    node_n:value -> struct4:n
    node_R:value -> struct4:n
    node_end:value -> struct4:n
    
    node[shape = "plaintext"]
    struct1 -> Null
    struct2:e -> Null:s
    // right 節點
    node_right[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>right </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    // left 節點
    node_left[label = <<table border="0" cellborder="1" cellspacing="0">
    <tr><td colspan="1"><b>left </b></td></tr>
    <tr><td colspan="1" port="value">addr</td></tr>
    </table>>];
    
    {rank=same; struct1 struct2 Null}
    node_left:value -> struct4
    node_right:value -> struct1:n
    
}                    

至此 `p` 指向 `null` 因此跳出 `while(p)`，
**答案**
AAAA: (*left)->next
BBBB: (*left)->next
CCCC: p->next
DDDD: list_tail(&left)
EEEE: list_tail(&right)

一般的 Quick sort 具有的特點：
1.會因為選擇不同 pivot 有不同結果。e.g.[0 5 <font color="#f00">2</font> 4 7 <font color="#DFCE0A">2</font> 6 <font color="#5EC0D8">2</font> ] 若選擇 <font color="#DFCE0A">2</font> 作為 pivot，經過第一輪排序後會得到 [0 <font color="#DFCE0A">2</font> <font color="#f00">2</font> <font color="#5EC0D8">2</font> 5 4 7 6]。
2.非 in-place：每次將鏈結串列分為兩個子串列，因此會申請兩個新串列來儲存，對每次遞迴的空間複雜度是 $O(n^2)$，最佳狀況是 $O(nlog2n)$。
#### Q2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

快速排序法最糟糕的情況是在每一輪排序中 pivot 恰為佇列中最大或最小值，時間複雜度可能為 $O(n^2)$ 所以若每次都選取固定位置的節點為 pivot 則可能資料本身分佈使得，pivot 特別容易選擇在偏大或偏小的值上。若採用隨機選擇 pivot，則受到鍊結串列資料先驗機率影響的程度也會較小。

因此我使用隨機選擇 pivot 位置的快速排序法，並使用 perf 進行效能測試、並使用隨機資料作為側測資。
**結果如下：**
pivot為鍊結串列的第一個節點
| # node | 1e+5 | 2e+5 | 5e+5 | 1e+6|
| -------- | -------- | -------- |----------|-----
|cache-references| 1.7e+10| 1.5e+10 |12|123|123|
|instruction| 2.5e+11 | 2.5e+11 |12|123|123|
|cycles| 2.2e+11 | 2.4e+11 |12|123|123|
|insn per cycle|1.14 |1.05
|exeution time（s）| 49.71 +- 1.32 | 53.33 +- 1.55

<!-- 因此我認為使用平衡快速排序法可以改善 pivot 選擇的問題，選擇中間值作為 pivot 可以維持切割次數在 $logn$，以避免出現數列僅被分為 1 與 n-2 的情況。 -->

實作上我使用
答案
AAAA: (*left)->next
BBBB: (*left)->next
CCCC: p->next
DDDD: list_tail(&left)
EEEE: (&right)

## [第二周測驗]()

digraph G {
    splines = false;
    node[shape=box];
    struct0 [label= "Color filtering"];
    struct1 [label= "Gaussian Filtering"];
    struct2 [label= "Canny Edging"];
    struct3 [label= "Segmentation"];
    struct4 [label= "Hough Transform"];
    struct5 [label= "Lane Recognition"];
    struct6 [label= "Curve Fitting"];
    {
        rank="same";
        // RawImage->struct0
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> struct5
        struct5 -> struct6
        // struct6 -> uotput
    }
    
}