# 2021q1 Homework1 (quiz1) contributed by < `yellow-hank` > ###### tags: `LinuxKernel` ## Linked list 結構 ```cpp typedef struct __node { int value; struct __node *next; } node_t; ``` - 結構示意圖 ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> value|<f1> next\n}"]; } ``` ## Quick sort recursive 實作 ```cpp 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; } ``` ### 執行示意圖 - 原始排序 ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> 3|<f1> next\n}"]; struct2 [label="{<f0> 5|<f1> next\n}"]; struct3 [label="{<f0> 1|<f1> next\n}"]; struct4 [label="{<f0> 4|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{list}"]; struct6 -> struct1:f0; struct1:f1 -> struct2:f0; struct2:f1 -> struct3:f0; struct3:f1 -> struct4:f0; struct4:f1 -> struct5:f0; } ``` - 選擇第一個當作 pivot ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> 3|<f1> next\n}"]; struct2 [label="{<f0> 5|<f1> next\n}"]; struct3 [label="{<f0> 1|<f1> next\n}"]; struct4 [label="{<f0> 4|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{list}"]; struct7 [label="{pivot}"]; struct1:f1 -> struct2:f0; struct2:f1 -> struct3:f0; struct3:f1 -> struct4:f0; struct4:f1 -> struct5:f0; struct6 -> struct1:f0; struct7 -> struct1:f0; } ``` - 走訪每個節點把大於 pivot 放入 right 裡，小於的放入 left 中 ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> 3|<f1> next\n}"]; struct2 [label="{<f0> 5|<f1> next\n}"]; struct3 [label="{<f0> 1|<f1> next\n}"]; struct4 [label="{<f0> 4|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{left}"]; struct7 [label="{right}"]; struct8 [label="{pivot}"]; struct2:f1 -> struct4:f0; struct3:f1 -> struct5:f0; struct6 -> struct3:f0; struct7 -> struct2:f0; struct8 -> struct1:f0; } ``` - 繼續排序 right 和 left - 先顯示 left 的部分 ， pivot 再次指向第一個值 ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 1|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{list}"]; struct8 [label="{pivot}"]; struct3:f1 -> struct5:f0; struct6 -> struct3:f0; struct8 -> struct3:f0; } ``` - 走訪每個節點把大於 pivot 放入 right 裡，小於的放入 left 中 ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 1|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct8 [label="{pivot}"]; struct6 [label="{left}"]; struct7 [label="{right}"]; struct8 -> struct3:f0; struct7 -> struct5:f0; } ``` - 進行合併，依序放入 left, pivot, right ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 1|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct8 [label="{list}"]; struct6 [label="{left}"]; struct7 [label="{right}"]; struct9 [label="{pivot}"]; struct8 -> struct3:f0; struct7 -> struct5:f0; struct3 -> struct5:f0; struct9 -> struct3:f0; } ``` - 顯示 right 的部分 ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 5|<f1> next\n}"]; struct5 [label="{<f0> 4|<f1> next\n}"]; struct6 [label="{list}"]; struct8 [label="{pivot}"]; struct3:f1 -> struct5:f0; struct6 -> struct3:f0; struct8 -> struct3:f0; } ``` - 走訪每個節點把大於 pivot 放入 right 裡，小於的放入 left 中 ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 5|<f1> next\n}"]; struct5 [label="{<f0> 4|<f1> next\n}"]; struct8 [label="{pivot}"]; struct6 [label="{right}"]; struct7 [label="{left}"]; struct8 -> struct3:f0; struct7 -> struct5:f0; } ``` - 進行合併，依序放入 left, pivot, right ```graphviz digraph structs { node[shape=record] struct3 [label="{<f0> 4|<f1> next\n}"]; struct5 [label="{<f0> 5|<f1> next\n}"]; struct8 [label="{list}"]; struct6 [label="{right}"]; struct7 [label="{left}"]; struct9 [label="{pivot}"]; struct8 -> struct3:f0; struct7 -> struct3:f0; struct3 -> struct5:f0; struct9 -> struct5:f0; } ``` - 兩個 quick sort 回傳後的結果 ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> 3|<f1> next\n}"]; struct2 [label="{<f0> 4|<f1> next\n}"]; struct3 [label="{<f0> 1|<f1> next\n}"]; struct4 [label="{<f0> 5|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{left}"]; struct7 [label="{right}"]; struct8 [label="{pivot}"]; struct2:f1 -> struct4:f0; struct3:f1 -> struct5:f0; struct6 -> struct3:f0; struct7 -> struct2:f0; struct8 -> struct1:f0; } ``` - 進行合併，依序放入 left, pivot, right ```graphviz digraph structs { node[shape=record] struct1 [label="{<f0> 3|<f1> next\n}"]; struct2 [label="{<f0> 4|<f1> next\n}"]; struct3 [label="{<f0> 1|<f1> next\n}"]; struct4 [label="{<f0> 5|<f1> next\n}"]; struct5 [label="{<f0> 2|<f1> next\n}"]; struct6 [label="{left}"]; struct7 [label="{right}"]; struct8 [label="{pivot}"]; struct9 [label="{list}"]; struct2:f1 -> struct4:f0; struct3:f1 -> struct5:f0; struct5:f1 -> struct1:f0; struct1:f1 -> struct2:f0; struct6 -> struct3:f0; struct7 -> struct2:f0; struct8 -> struct1:f0; struct9 -> struct3:f0; } ``` - 完成排序 ## 使用其他 Pseudorandom number generator - 原本的 quick sort 是使用 random 函式產生亂數，但是多執行幾次就會發現產生的亂數都一樣。 - 擷取部分程式碼 ```cpp while (count--) list = list_make_node_t(list, random() % 1024); ``` - 後來選擇使用 srand 函式來產生亂數 ```cpp srand(time(NULL)); while (count--) list = list_make_node_t(list, rand() % 1024); ``` - 以現在的時刻當作 seed 來產生亂數，但是這種方式會讓人有疑惑，亂數的因子裡面還有一個時間，所以還有改善的空間。 ## non-recursive quick sort 實作 ```cpp void nr_quicksort(node_t **list) { #define MAX_LEVELS 1000 //list is empty or only one in it if(!*list || !(*list)->next) return; int top;//for stack node_t *stack[MAX_LEVELS]; node_t *result = NULL; node_t *pivot ; stack[0] = (*list); while(top>=0 && top < MAX_LEVELS) { if(!stack[top]) { top--; continue; } if(!stack[top]->next) { stack[top]->next = result; result = stack[top]; top--; continue; } pivot = stack[top]; node_t *n = pivot->next; int value = pivot->value; pivot->next = NULL; node_t *right = NULL,*left = NULL; while(n) { node_t *tmp = n; n = n->next; list_add_node_t(tmp->value > value ? &right : &left, tmp); } stack[top++] = left; stack[top++] = pivot; stack[top] = right; } *list = result; return; } ``` - 藉由宣告一個結構指標陣列，來實作 stack ，所以最大的深度為1000，若是超過程式會有錯誤。 - 每一次 quick sort subroutine 執行完後，會將 left, pivot, right 依照順序放入 stack 中，接下來從 stack 的頂端拿出一個進行排序，結束的時間點就是stack 為空時。其餘的操作就如同上述的遞迴方式。