# 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, ¤t->i) < 0) {
if (current->list.prev == ¤t->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 == ¤t->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 == ¤t->list) {
list_add_tail(¤t->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 != ¤t->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 = ¤t->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(¤t->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, ¤t->i) < 0) {
if (current->list.prev == ¤t->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 == ¤t->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 相比越大，代表越有機會透過此方法減少比較次數。
Sign in with Wallet
Connect another wallet