---
# System prepended metadata

title: 2021q1 Homework1 (quiz1)
tags: [LinuxKernel]

---

# 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 為空時。其餘的操作就如同上述的遞迴方式。

 
 
 
