---
# System prepended metadata

title: 2021q1 Homework1 (quize1)

---

# 2021q1 Homework1 (quize1)
contributed by < `jameshuang890902` >

## 進度列表
- [ ] 重新回答第 1 周測驗題，附帶的「延伸問題」也需要完成解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
    - [ ] 延伸問題:
        - [x] 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
            - [x] 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
        - [x] 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
        - [x] Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
            - [x] 參考資料: The Linux Kernel API - List Management Functions
        - [ ] 研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
:::warning
:warning: 比照 課前測驗參考解答: Q1 和 Linked list 題目分析 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
:::





## 第 1 周測驗題
### 選擇題答案
1. `LLL = (c), left = &((*left)->next)`
2. `AAA = (e), &right`
3. `BBB = (c), &left`
4. `CCC = (b), list_concat(&result, pivot); list_concat(&result, right)`
### 完整程式碼
- 首先看到 struct __node 為節點的結構，有一個 int 儲存資料，及一個 next pointer，因此可以推測其為一個單向的 linked list。
:::warning
:question: 為什麼 `__node`？ 有雙底線在前？
:::
```c=
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```
```c= 
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;
}
```
:::warning
:question: `static inline void` 的用途。
:::
```c=
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;
}

static void list_display(node_t *list) {
    printf("%s IN ORDER : ", list_is_ordered(list) ? "   " : "NOT");
    while (list) {
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    size_t count = 20;

    node_t *list = NULL;
    while (count--)
        list = list_make_node_t(list, random() % 1024);

    list_display(list);
    quicksort(&list);
    list_display(list);

    if (!list_is_ordered(list))
        return EXIT_FAILURE;

    list_free(&list);
    return EXIT_SUCCESS;
}        
```
:::danger
:warning: 這裡發現原程式碼中沒有 `list_make_node_t` 的實作。下面是我寫的版本。
```c=
node_t* list_make_node_t(node_t *list, int num)
{
    node_t *temp = (node_t*)malloc(sizeof(node_t));
    
    if(!temp) {
        return NULL;
    } else {
        temp->value = num;
        temp->next = list;
        list = temp;
        temp = NULL;
    }    
}
```
:::

參考執行輸出:
```
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359 
    IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016 
```
## 程式碼分析
### main()
1. 設定 linked list ndoe 個數 `size_t count` ，下面分析以 `size_t count = 5;` 為例。
2. `node_t *list = NULL;`建立一個指向 linked list 的指標，預設為 NULL。
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        d [label="{ <data> NULL}"];
        a:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

```
3. 藉由呼叫 `list_make_node_t()` `count`次來產生linked list，並賦予每個 node `random() % 1024` 所產生的亂數值(0~1023)。這裡假設產生的值依順序為 `{4, 2, 3, 5, 1}`，下面演示 `list_make_node_t()` 的過程。
### list_make_node_t()
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        b [label="{ <data> 4 | <ref>  }"];
        g [label="{ <data> NULL}"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> g:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        g [label="{ <data> NULL}"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        g [label="{ <data> NULL}"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        g [label="{ <data> NULL}"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> list | <ref>  }", width=1.2]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
### main()
4. 以`list_display(list);` 將 linked list 以
     `NOT IN ORDER : 4 2 3 5 1` 的方式顯示。
     
5. 執行 `quicksort(&list);` ，將 linked list 以小到大的排序，當中有用到 `list_concat()` 過程如下：
### list_display(list)
- 如果 *list 指向 NULL 直接結束。
- `if (!*list) return;`
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;

}
```
- `node_t *pivot = *list;``
-  `int value = pivot->value;
-  `node_t *p = pivot->next; `

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

- `pivot->next = NULL;`
- `node_t *left = NULL, *right = NULL;`
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];

        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

``` c
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right : &left, n);
    }
```



```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];

        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];

        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

- `list_add_node_t(n->value > value ? &right : &left, n)`
- 因為目前當下`n = 2 < 4` ，所以執行的等同於`list_add_node_t(&left, n)`。

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```

```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *list | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> 4 | <ref>  }"];
        c [label="{ <data> 2 | <ref>  }"];
        d [label="{ <data> 3 | <ref>  }"];
        e [label="{ <data> 5 | <ref>  }"];
        f [label="{ <data> 1 | <ref>  }"];
        g [label="{ <data> NULL}"];
        h [label="**list",color = green];
        i [label="{ <data> *pivot | <ref>  }",color = blue];
        j [label="{ <data> *p | <ref>  }",color = blue];
        k [label="{ <data> value | <data> 4 }", color = red];
        l [label="{ <data> NULL}"];
        m [label="{ <data> *left | <ref>  }",color = blue];
        n [label="{ <data> *right | <ref>  }",color = blue];
        o [label="{ <data> NULL}"];
        p [label="{ <data> *n | <ref>  }",color = blue];
        q [label="{ <data> NULL}"];
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> l:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> q [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        e:ref:c -> o [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        f:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        i:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        j:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        m:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        p:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        h->a:ref;
}
```
- Stop 當 p 為空指標，因為 `while (p) {}`. 然後把 `left, right` 當作新的 linked list 繼續做上面的拆分。
- 當特定 linked list 只有一個 node 時因為`if (!*list)
        return;`，該分枝便停止拆分。
- 最後從小段的 linked list 開始執行 `list_concat()` ， 示意圖如下：

### list_concat()
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *result | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> left | <ref>  }"];
        c [label="{ <data> pivot | <ref>  }"];
        d [label="{ <data> right | <ref>  }"];
}
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *result | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> left | <ref>  }"];
        c [label="{ <data> pivot | <ref>  }"];
        d [label="{ <data> right | <ref>  }"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
}
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *result | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> left | <ref>  }"];
        c [label="{ <data> pivot | <ref>  }"];
        d [label="{ <data> right | <ref>  }"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
        
```
```graphviz
digraph linkedlist {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> *result | <ref>  }", width=1.2,color = blue]
        b [label="{ <data> left | <ref>  }"];
        c [label="{ <data> pivot | <ref>  }"];
        d [label="{ <data> right | <ref>  }"];
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2,];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
        
```
### main()
- 使用 `list_display(list);`印出排序後的結果。例如 `IN ORDER : 1 2 3 4 5`
- 檢查是否 sort 成功，使用:
    ```
    if (!list_is_ordered(list))
        return EXIT_FAILURE;
    ```
    概念是逐一檢查目前 node 的 value 是復大於上一個 node 的 value。一檢查倒到不是就 `return false;`， 觸發 `EXIT_FAILURE`。
- 再以 `list_free(&list);` 釋放所有 node 的記憶體。
- 最後 `return EXIT_SUCCESS;` 結束程式。


## 修正 random 並引入其他 [Pseudorandom number generator]((https://en.wikipedia.org/wiki/Pseudorandom_number_generator))
- 原程式碼使用到的 [random](https://linux.die.net/man/3/random)。
- 藉由將時間設定成 seed 的方式，使每次執行產生的隨機結果不同，如下。

```c=
#include <time.h>

unsigned int seed = (unsigned int)time(NULL);
srandom(seed);

while (count--)
            list = list_make_node_t(list, random() % 1024);
```

:::danger
:warning: 上面的程式碼存在以下確點
1. 由於 `time()` 是回傳 1970-01-01 00:00:00 +0000 (UTC) 至今的秒數，在同一秒執行會得到相同的亂數。
2. 有不能設置為密碼的缺點，因為別人可以藉由時間翻推 seed ，進而猜到你的亂數組合（或縮小需要猜測範圍）。

參考：[MSC30-C. Do not use the rand() function for generating pseudorandom numbers](https://wiki.sei.cmu.edu/confluence/display/c/MSC30-C.+Do+not+use+the+rand%28%29+function+for+generating+pseudorandom+numbers)
> Pseudorandom number generators use mathematical algorithms to produce a sequence of numbers with good statistical properties, but the numbers produced are not genuinely random.

> The C Standard rand() function makes no guarantees as to the quality of the random sequence produced. The numbers generated by some implementations of rand() have a comparatively short cycle and the numbers can be predictable. Applications that have strong pseudorandom number requirements must use a generator that is known to be sufficient for their needs.
:::
### 實作 [Middle Square Weyl Sequence PRNG](https://en.wikipedia.org/wiki/Middle-square_method#Middle_Square_Weyl_Sequence_PRNG)
- 參考 [Middle-square method](https://en.wikipedia.org/wiki/Middlesquare_method#Middle_Square_Weyl_Sequence_PRNG) 與 [Weyl sequence](https://en.wikipedia.org/wiki/Weyl_sequence)。
-  Middle-square method 的主要的概念是透過上一次所生產的卵是結果，將其平方並取中間位數，座位下一次的亂數種子。
- Weyl sequence 則是透過在運算中添加一個與上面的平方結果等位元的奇數，使得亂數結果在該奇數的位元範圍呈現均勻分布。
- 下面的實作是取中間的 32 位元作為下個 seed `uint64_t *w_rand_ptr`。

```c=
void msws(uint64_t *w_rand_ptr, uint64_t *w_ptr)
{
    uint64_t w_seed = 0xb5ad4eceda1ce2a9;
    *w_rand_ptr *= *w_rand_ptr;
    *w_rand_ptr += (*w_ptr += w_seed);
    *w_rand_ptr = (*w_rand_ptr << 16)>>32;
}
```

- 使用方法如下：
```c=
uint64_t w, w_rand = (uint64_t)time(NULL);

while (count--) {
    msws(&w_rand, &w);
    list = list_make_node_t(list, w_rand % 1024);
}
```



## 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 的迭代版本

### 為了方便實踐 quick sort 所以在 linked list 新增 back link
- 變更 `node_t, list_make_node_t`。
- 新增 `back` 的連接過程。
```c=
typedef struct __node
{
    int value;
    struct __node *next;
    struct __node *back;
} node_t;

void list_make_node_t(node_t **list_head, node_t **list_tail, int num)
{
    node_t *temp = (node_t *)malloc(sizeof(node_t));

    if (!temp)
        return;
    else {
        if(*list_head)
            (*list_head)->back = temp;
        else
            *list_tail = temp;
        temp->value = num;
        temp->next = *list_head;
        *list_head = temp;
        temp = NULL;
    }
}
```
- 下面是非遞迴版本的 quick sort 實作。
- 程式碼存在於 quick-sort_non_recursive.c 。
```c=
void quicksort_non_recursive(node_t *list_head, node_t *list_tail, int count)
{
    #define MAX_LEVELS 1000
    LABLE left = {.node_ptr = list_head},
          right = {.node_ptr = list_tail},
            beg[MAX_LEVELS],
            end[MAX_LEVELS];
    

    int piv = 0, head = -1, tail = -1;

    beg[0].index =0;
    end[0].index = count - 1;
    beg[0].node_ptr = list_head;
    end[0].node_ptr = list_tail;
    head++;
    tail++;

    while (tail >= head) {
        
        left.index = beg[head].index;
        right.index = end[head].index;
        
        left.node_ptr = beg[head].node_ptr;
        right.node_ptr = end[head].node_ptr;

        if (left.index < right.index) {

            piv = beg[head].node_ptr->value;
            
            while (left.index < right.index) {
                
                while (right.node_ptr->value >= piv && left.index < right.index) {
                    right.index--;
                    right.node_ptr = right.node_ptr->back;
                }
                if (left.node_ptr && right.node_ptr &&
                    left.index < right.index) {
                    left.node_ptr->value = right.node_ptr->value;
                    left.node_ptr = left.node_ptr->next;
                    left.index++;
                }
                while (left.node_ptr->value <= piv && left.index < right.index) {
                    left.index++;
                    left.node_ptr = left.node_ptr->next;
                }
                if (left.node_ptr && right.node_ptr &&
                    left.index < right.index) {
                    right.node_ptr->value = left.node_ptr->value;
                    right.node_ptr = right.node_ptr->back;
                    right.index--;
                }
            }
            left.node_ptr->value = piv;

            if (beg[head].index < right.index - 1) {
                tail++;
                beg[tail].node_ptr = beg[head].node_ptr;
                end[tail].node_ptr = right.node_ptr->back;

                beg[tail].index = beg[head].index;
                end[tail].index = right.index - 1;
            }

            if (left.index + 1 < end[head].index) {
                tail++;
                beg[tail].node_ptr = left.node_ptr->next;
                end[tail].node_ptr = end[head].node_ptr;

                beg[tail].index = left.index + 1;
                end[tail].index = end[head].index;
            }
            head++;
        }
    }
}
```
## 探討 Linux 的 linked list 和 linux-list/example/quick-sort.c 的落差
## 改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
```c=
typedef struct stack_ele STACK_ELE;
struct stack_ele {
    struct list_head temp_head;
    int merged;
    int level;
};

static void list_qsort_non_recursive(struct list_head *head)
{
    struct listitem *item = NULL, *is = NULL;

    struct listitem *pivot[256];
    struct stack_ele stack[512];
    int stack_top = -1, stack_bottum = -1, stack_current = -1, pivot_top = -1,
        pivot_bottum = -1, pivot_current = -1;  // 256 as ARRAY_SIZE(values)

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&stack[0].temp_head);  // list_less
    INIT_LIST_HEAD(&stack[1].temp_head);  // list_large

    stack[0].level = 1;
    stack[1].level = 1;

    pivot[0] = list_first_entry(head, struct listitem, list);
    list_del(&pivot[0]->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot[0]->i) < 0)
            list_move_tail(&item->list, &stack[0].temp_head);
        else
            list_move(&item->list, &stack[1].temp_head);
    }

    stack_top += 2;
    stack_bottum++;
    stack_current++;
    pivot_top += 1;
    pivot_bottum++;

    while (stack_top >= stack_current) {
        if (!list_empty(&stack[stack_current].temp_head) &&
            !list_is_singular(&stack[stack_current].temp_head)) {
            stack[stack_current].merged = 1;
            pivot_top++;
            pivot[pivot_top] = list_first_entry(&stack[stack_current].temp_head,
                                                struct listitem, list);
            list_del(&pivot[pivot_top]->list);

            INIT_LIST_HEAD(&stack[stack_top + 1].temp_head);
            INIT_LIST_HEAD(&stack[stack_top + 2].temp_head);

            list_for_each_entry_safe (item, is, &stack[stack_current].temp_head,
                                      list) {
                if (cmpint(&item->i, &pivot[pivot_top]->i) < 0)
                    list_move_tail(&item->list,
                                   &stack[stack_top + 1].temp_head);
                else
                    list_move(&item->list, &stack[stack_top + 2].temp_head);
            }
            stack[stack_top + 1].level = stack[stack_current].level + 1;
            stack[stack_top + 2].level = stack[stack_current].level + 1;
            stack_top += 2;
        } else
            stack[stack_current].merged = 0;
        stack_current++;
    }

    int less_index, greater_index = stack_top, merge_index;
    pivot_current = pivot_top;

    while (greater_index > stack_bottum + 1) {
        less_index = greater_index - 1;
        merge_index = less_index - 1;

        while (stack[merge_index].level != stack[less_index].level - 1)
            merge_index--;
        while (stack[merge_index].merged != 1)
            merge_index--;

        list_add(&pivot[pivot_current]->list, &stack[merge_index].temp_head);
        list_splice(&stack[less_index].temp_head,
                    &stack[merge_index].temp_head);
        list_splice_tail(&stack[greater_index].temp_head,
                         &stack[merge_index].temp_head);

        pivot_current--;
        greater_index = less_index - 1;
        stack[merge_index].merged = 0;
    }
    less_index = greater_index - 1;
    list_add(&pivot[pivot_current]->list, head);
    list_splice(&stack[less_index].temp_head, head);
    list_splice_tail(&stack[greater_index].temp_head, head);
}
```

## 研讀 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf) 並落實於linux-list/example/quick-sort.c

該文章中提及因爲 Doubly-linked list 有向前與向後的 pointer ，所以適合拿來實踐二元樹。

二元樹插入節點的時間複雜度是 $$O(n^2)$$，最差的情況會發生在該二元樹只有一個 leaf 的時候。如果輸入資料皆為隨機，那通常會得到一棵接近平衡的樹，其時間複雜度為 O(nlongn)。參考  A Comparative Study of Linked List Sorting Algorithms 文中的 Table 1, Table 2 可以發現，在他的實驗中 tree sort 比其他五種 sort 執行的更快。

下面是以二元搜尋樹做 sort 的實作。存在 tree-sort.c 與 tree-sort.h。

```c=
void Traverse(struct listitem *root, struct list_head *head)
{
    struct listitem *work;
    if (root->list.prev != &root->list) {
        Traverse(container_of((root->list).prev, struct listitem, list), head);
    }
    work = container_of((root->list).next, struct listitem, list);
    list_add_tail(&root->list, head);

    if (&work->list != &root->list) {
        Traverse(work, head);
    }
}


static void tree_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct listitem *root, *current;
    struct listitem *item = NULL, *is = NULL;

    root = list_first_entry(head, struct listitem, list);
    list_del(&root->list);

    INIT_LIST_HEAD(&root->list);

    list_for_each_entry_safe (item, is, head, list) {
        list_del(&item->list);

        current = root;

        while (1) {
            if (cmpint(&item->i, &current->i) < 0) {
                if (current->list.prev == &current->list) {
                    current->list.prev = &item->list;
                    INIT_LIST_HEAD(&item->list);
                    break;
                } else {
                    current = container_of((current->list).prev,
                                           struct listitem, list);
                }
            } else {
                if (current->list.next == &current->list) {
                    current->list.next = &item->list;
                    INIT_LIST_HEAD(&item->list);
                    break;
                } else {
                    current = container_of((current->list).next,
                                           struct listitem, list);
                }
            }
        }
    }
    Traverse(root, head);
}
```
### 改進上面的程式碼
#### 將 Traverse 改成非遞迴版本的 Traverse_non_recursive
參考： [Inorder Tree Traversal without recursion and without stack!](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)

:::danger
:warning: 下面這個函式還沒完成。
:::
```c=
void Traverse_non_recursive(struct listitem *root, struct list_head *head)
{
    struct listitem *current, *pre;

    if (root == NULL)
        return;

    current = root;
    while (current != NULL) {
        if (current->list.prev == &current->list) {
            list_add_tail(&current->list, head);
            current = container_of((current->list).next, struct listitem, list);
        } else {
            /* Find the inorder predecessor of current */
            pre = container_of((current->list).prev, struct listitem, list);
            while (pre->list.next != &pre->list && pre->list.next != &current->list)
                pre = container_of((pre->list).next, struct listitem, list);

            /* Make current as the right child of its
               inorder predecessor */
            if (pre->list.next != &pre->list) {
                pre->list.next = &current->list;
                current =
                    container_of((current->list).prev, struct listitem, list);
            }

            /* Revert the changes made in the 'if' part to
               restore the original tree i.e., fix the right
               child of predecessor */
            else {
                pre->list.next = &pre->list;
                list_add_tail(&current->list, head);
                container_of((current->list).next, struct listitem, list);
            } /* End of if condition pre->right == NULL */
        }     /* End of if condition current->left == NULL*/
    }         /* End of while */
}
```
#### tree-sort_plus() 新增 min, max 指標的實作。

從二元搜尋樹的原理，我們可以知道，當一顆左邊傾斜的樹插入一個比所有 node 小的 node ，需要很多的比較次數，右邊傾斜的樹插入一個比所有 node 大的 node 也是。

所以我就想，在數建構時將最大與最小的 node 標示出來，當插入 node 就先跟它們做比較，比最小還小，一定放在最小的左邊，比最大還大，一定放在最大的右邊。雖然一班的 node 會要增加兩次的比較。

下面的程式碼 tree-sort_plus() 想實驗看看此方法是否能減少比較次數的，使得時間複雜度更接近 O(nlongn) 。
```c=
static void tree_sort_plus(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct listitem *root, *current;
    struct listitem *min, *max;
    struct listitem *item = NULL, *is = NULL;

    int insert_left = 0, insert_middle = 0, insert_right = 0;

    root = list_first_entry(head, struct listitem, list);
    min = root;
    max = root;

    list_del(&root->list);
    INIT_LIST_HEAD(&root->list);

    

    
    list_for_each_entry_safe (item, is, head, list) {
        list_del(&item->list);
        if (cmpint(&item->i, &min->i) < 0) {
            min->list.prev = &item->list;
            INIT_LIST_HEAD(&item->list);
            min = item;
            insert_left++;

        } else if (cmpint(&item->i, &max->i) > 0) {
            max->list.next = &item->list;
            INIT_LIST_HEAD(&item->list);
            max = item;
            insert_right++;

        } else {
            current = root;
            insert_middle++;

            while (1) {
                if (cmpint(&item->i, &current->i) < 0) {
                    if (current->list.prev == &current->list) {
                        current->list.prev = &item->list;
                        INIT_LIST_HEAD(&item->list);
                        break;
                    } else {
                        current = container_of((current->list).prev,
                                                struct listitem, list);
                    }
                } else {
                    if (current->list.next == &current->list) {
                        current->list.next = &item->list;
                        INIT_LIST_HEAD(&item->list);
                        break;
                    } else {
                        current = container_of((current->list).next,
                                                struct listitem, list);
                        ;
                    }
                }
            }
        }
    }
    printf("\ninsert left: %d, insert right: %d, insert middle: %d\n", insert_left, insert_right, insert_middle);
    /* there are two ways of traverse can choose 8 */
    Traverse(root, head);
    //Traverse_non_recursive(root, head);
        
}
```

下面是執行得到的結果：
```
insert left: 4, insert right: 3, insert middle: 248
```
如果 insert left + insert right 跟 insert middle 相比越大，代表越有機會透過此方法減少比較次數。




