# 2021q1 Homework1 (quiz1) contributed by < [Julian-Chu](https://github.com/Julian-Chu) > ###### tags: `linux2021` ## 程式處理流程 當 pointer to list 為 NULL 直接返回 ```cpp if(!*list) return; ``` 當 pointer to list 不為 NULL 繼續處理 ``` graphviz digraph structs { rankdir=LR node[shape=record] node3 [label="3"] node4 [label="4"] node1 [label="1"]; node2 [label="2"] node5 [label="5"] node3->node5 node5->node2 node2->node1 node1->node4 } ``` 與針對陣列操作的 quicksort 類似，先挑選基準點而後進行比較，這邊利用第一個 node 作為pivot ， 同時把 pivot 與 next node 的連結切斷 ```cpp node_t *pivot = *list; int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL; ``` ``` graphviz digraph structs { rankdir=LR node[shape=record] node3 [label="{<f0>pivot|<f1>3}"] node4 [label="4"] node1 [label="1"]; node2 [label="2"] node5 [label="5"] node3->node5[penwidth=0, arrowhead=none] node5->node2 node1->node4 node2->node1 } ``` 將其他的 node 與 pivot 比較分為兩群 left & right，大於 pivot 放在 right , 其餘放在 left ```cpp 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); } ``` ``` graphviz digraph structs { rankdir=LR node[shape=record] node3 [label="{<f0>pivot|<f1>3}"] node5 [label="{right|5}"] node2 [label="{left|2}"] node1 [label="1"] node4 [label="4"] node5->node4 node2->node1 {rankdir=BT;rank=same; node2, node3, node5} } ``` 對 left 跟 right，繼續處理，直到 left 跟 right 排好序 ```cpp quicksort(&left); quicksort(&right); ``` ``` graphviz digraph structs { rankdir=LR node[shape=record] node3 [label="{<f0>pivot|<f1>3}"] node4 [label="{right|4}"] node1 [label="{left|1}"] node2 [label="2"] node5 [label="5"] node4->node5 node1->node2 {rankdir=BT;rank=same; node1, node3, node4} } ``` 最後利用 left -> pivot -> right 的順序把 linked list 組合起來 ```cpp node_t *result = NULL; list_concat(&result, left); list_concat(&result, pivot); list_concat(&result, right); *list = result; ``` ``` graphviz digraph structs { rankdir=LR node[shape=record] node3 [label="{<f0>pivot|<f1>3}"] node4 [label="{right|4}"] node1 [label="{left|1}"] node2 [label="2"] node5 [label="5"] node4->node5 node1->node2 node2->node3 node3->node4 } ``` ### list_add_node_t 實作上的小差異可能導致 $O(1)$ 與 $O(n)$ 的巨大差異 題目的 list_add_node_t 為 $O(1)$ ```cpp static inline void list_add_node_t(node_t **list, node_t *node_t){ node_t->next = *list; *list = node_t; } ``` 如果實作細節是在 list 的 tail.next 加上節點的話，會導致每次都需要走訪 list 所有節點，導致這個函式的時間複雜度為 $O(n)$ ，由於 quicksort 在這一步只需要分成 left 和 right 兩部分， 不需要保持 left 跟 right 的位置或是插入順序 (quicksort 的 unstable 特性)，`list_add_note_t` 效率更高。 :::warning todo: 閱讀 C11 對 inline 跟 static 的敘述 ::: ### Todo - random - non-recusive quicksort - linux circular doubly-linked list - A Comparative Study of Linked List Sorting Algorithms