# 2021q1 Homework1 (quiz1)
contributed by < `jonathanyang0227` >
### Reviewed by `jhan1998`
1. 尚未完成其他延伸問題。
2. 未解說 poiner to pointer 的用意。
# 作業要求
- [x] 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)，
- [x] 「==延伸問題==」也需要完成
* 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.ioㄡ/@sysprog/linked-list-quiz)
- [ ] * 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
## 程式分析
:::success
解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
* 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
:::
### linklist 結構
```c
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### list_add_note
```c
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
此函式功能為新增一個節點在 node_t的最前方
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="list",shape=plaintext,fontcolor=red];
{
rankdir=LR;
a [label="1"];
b [label="2"];
c [label="3"];
d [label="..."];
NULL1[label="NULL",shape=plaintext]
a->b->c->d->NULL1
}
{
rank="same";
list->a;
}
node_t[label="node_t"color=red];
node_t:n -> a:n [color=red];
}
```
```graphviz
digraph structs {
node[shape=box];
rankdir=LR
{
rankdir=LR
e [label="node_t"];
i [label="1"];
f [label="2"];
g [label="3"];
h [label="4"];
NULL2[label=NULL,shape=plaintext];
e->i->f->g->h->NULL2;
}
{
rank=same;
list[label="list" shape=plaintext,fontcolor=red];
list->e
}
}
```
### list_concat
```c
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
這個函數要看 `qicksort()` 裡，它是出現在 sort 之後，因此可以推測其功能是將排序好的兩個 list 串接起來。
再看 `list_concat` 中， `while(*left)` 後 `*left=right` 推測應為將 `right` 接到 `*left` 的最尾端
故 LLL 應為 走訪到 `left` 的最尾端 `left = &((*left)->next);` 直到 `*left = NULL` 為止
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="left",shape=plaintext,fontcolor=red];
{
rankdir=LR;
a [label="1"];
b [label="2"];
c [label="3"];
d [label="..."];
NULL1[label="NULL",shape=plaintext]
a->b->c->d->NULL1
}
{
rank="same";
list->a;
}
}
```
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="left",shape=plaintext,fontcolor=red];
{
rankdir=LR;
a [label="1"];
b [label="2"];
c [label="3"];
d [label="..."];
NULL1[label="NULL",shape=plaintext]
a->b->c->d->NULL1
}
{
rank="same";
list->NULL1;
}
right[color=red];
NULL1->right:n[color=red];
}
```
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="left",shape=plaintext,fontcolor=red];
{
rankdir=LR;
a [label="1"];
b [label="2"];
c [label="3"];
d [label="..."];
NULL1[label="NULL",shape=plaintext]
right[label="right",color=red];
a->b->c->d->right
}
{
rank="same";
list->right;
}
}
```
### quicksort
```c
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 ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
`qicksort（）`這個函式是要對 list 做排序，首先先找到一個 pivot 的 value 作為基準，目的是要用 p 去走訪 list 裡面的值
```c
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
```
接著往下看 while loop
```c
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? AAA : BBB, n);
}
```
在`list_add_node_t(n->value > value ? AAA : BBB, n);`中可看出若 n比較大，則新增到 AAA 中，若比較小則新增至 BBB 中。
而 AAA 和 BBB 則可以看下面
`quicksort(&left);quicksort(&right);`
可得知
`AAA = &right`
`BBB = &left`
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="list"];
left[label="left"];
right[label="right"];
list->left:n[label=" value < pivot",fontcolor=red]
list->right:n[label=" value > pivot",fontcolor=red]
}
```
接著在後面
```c
list_concat(&result, left);
CCC;
*list = result;
```
當排序好之後，就要將完成的 `left` `right`進行組合，
前面已經得到 `list_concat()`的功能是將兩個 list 連接起來，且為 `left` 接在 `result` 的後面，故應依序連接`left` `pivot` `right`
所以`CCC`應為
`list_concat(&result,n);`
`list_concat(&result,right);`
```graphviz
digraph structs {
rankdir=LR;
node[shape=box];
list[label="pivot",color=red];
left[label="left"];
right[label="right"];
left->"..."->list->right->"...."
}
```
### list_is_ordered
```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;
}
```
這個函數是透過 while 走訪 list 的函數，檢查是否有按照順序排序
其中，下面第一次進去迴圈的時候設定 value
```c
if (first) {
value = list->value;
first = false;
}
```
再來就是檢查後一個有沒有比前一個大，沒有的話就 return false
```c
if (list->value < value)
return false;
value = list->value;
```
### list_display
```c
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");
}
```
這個函數是列出 list 內所有的值
會先透過 `list_is order()` 判斷是不是照順序
```c
printf("%s IN ORDER : ", list_is_ordered(list) ? " " : "NOT");
```
再用 while 迴圈 print 出 list 內所有的值
```c
while (list) {
printf("%d ", list->value);
list = list->next;
}
```
### main
```c
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;
}
```
main 函數中找不到關於 `list_make_node_t()` & `list_free()` 的詳細內容，應該是我們要自己實做
### list_make_node_t
在 `main` 中 `list_make_node_t()`出現在while loop中
```c
size_t count = 20;
node_t *list = NULL;
while (count--)
list = list_make_node_t(list, random() % 1024);
```
可推出這個函式目的是要創造一個大小為 20 的 list ，其值用 random 決定，範圍是 0～1024，故程式碼如下：
```c
static node_t *list_make_node_t(node_t *list, int num)
{
node_t *new = malloc(sizeof(node_t));
new->value = num;
new->next = list;
return new;
}
```
### list_free
這個程式碼出現在 return 之前，故判斷應為將 list 內所有東西清空
```c
void list_free(node_t **list)
{
node_t *p = *list;
while (p) {
node_t *del = p;
p = p->next;
free(del);
}
}
```
### quiz1.c
以下是完整程式碼：
```c=
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
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;
}
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");
}
static node_t *list_make_node_t(node_t *list, int num)
{
node_t *new = malloc(sizeof(node_t));
new->value = num;
new->next = list;
return new;
}
void list_free(node_t **list)
{
node_t *p = *list;
while (p) {
node_t *del = p;
p = p->next;
free(del);
}
}
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;
}
```
執行結果：
```c
joanathan@jonathan:~/linux2021/quiz1$ ./quiz1 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
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
```
### random
延伸問題提到測試程式使用到 random，多執行幾次發現輸出結果相仿
```c
list = list_make_node_t(list, random() % 1024);
```
根據 [rand(3) — Linux manual page](https://man7.org/linux/man-pages/man3/rand.3.html) 可以知道，雖有使用 `rand()` 但 沒有設定 `srand()` 會讓使 `rand()` 自動給值為 1 的種子，而給相同的參數會得到一樣的數字
所以如果我們設定 `srand(time(NULL))` 就可以給讓每次都產生不一樣的數字。
:::warning
其中 我們透過 `time(NULL)` 利用回傳的時間差給予 `srand()` 不同的 seed 使其可以產生不同的數字，但這時會想到一個問題，如果連續（一秒內）執行程式兩次，則 `srand()` 會得到一樣的 seed，會使兩次執行結果一樣，不符合亂數的特性
:::
### [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) (PRNG)
#### 前言—亂數的特性
* **隨機性**：看起來夠亂，沒有規律，所有數字分佈平均
* **不可預測性**：無法從之前的亂數數列猜出下一個亂數的值
* **不可重複性**：以後不可能再有同樣的數列
:::info
**Pseudorandom** 可以滿足前兩者的特性，但仍會有出現重複性的問題，也就是週期
:::
#### PRNG algorithm (大致列舉)
1. [Linear congruential generator](https://en.wikipedia.org/wiki/Linear_congruential_generator)
2. [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister)
3. [Xorshift](https://en.wikipedia.org/wiki/Xorshift)
這次選擇針對 **Mersenne Twister** 做實作
**選擇原因：Mersenne Twister algorithm 廣被各種程式語言採用**
#### Mersenne Twister
The Mersenne Twister was developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士).
* ##### Advantage
* very **long period** of 2^19937^ − 1.
* **k-distributed** to 32-bit accuracy for every 1 ≤ k ≤ 623
* **fast**
:::info
[**k-distributed**](https://en.wikipedia.org/wiki/K-distribution) :對於一個 k 位元長度，能夠在[0,2^k−1^]的區間生成離散型均勻分布的隨機數。
A pseudorandom sequence xi of w-bit integers of period P is said to be k-distributed to v-bit accuracy if the following holds.
Let truncv(x) denote the number formed by the leading v bits of x, and consider P of the k v-bit vectors
$$
{\displaystyle ({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{i+1}),\,...,\,{\text{trunc}}_{v}(x_{i+k-1}))\quad (0\leq i<P)}
$$
Then each of the 2^kv^ possible combinations of bits occurs the same number of times in a period, except for the all-zero combination that occurs once less often.
:::
* ##### Disadvantage
* Relatively **large state buffer**, of 2.5 KiB
* **Mediocre throughput** by modern standards
* **Poor diffusion**: can take a long time to start generating output that passes randomness tests, if the initial state is highly non-random—particularly if the initial state has many zeros.
* Is **not cryptographically secure**
#### **Algorithmic description**
1. Set r w-bit numbers (x~i~, i = 1,2,…, r) randomly as initial values.
2.
$$
A = \begin{pmatrix} 0 & I_{w - 1} \\ a_{w-1} & (a_{w - 2}, \ldots , a_0) \end{pmatrix}
$$
$I_{w - 1}$~ : (w − 1) × (w − 1) identity matrix
$a_{i}$ , $i = 1,…, w$ take values of either 0 or 1.
3. $$
{\displaystyle x_{k+n}:=x_{k+m}\oplus \left(({x_{k}}^{u} \mid {x_{k+1}}^{l})A\right)\qquad \qquad k=0,1,\ldots }
$$
${x_{k}}^{u} \mid {x_{k+1}}^{l}$ : the concatenation of the most significant (upper) w−l bits of x~i~ and the least significant l bits of x~i+1~.
$\oplus$ : exclusive or (XOR)
Therefore:
$$
\boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & x_0 = 0\\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & x_0 = 1\end{cases}
$$
4. $$
\displaystyle z=x_{i+r}\oplus \left({x_{i+r}}^{u} \gg t_{1} \right)\qquad \qquad \\
\displaystyle z=z\oplus \left((z \ll t_{2})\& m_{1} \right)\qquad \qquad \\
\displaystyle z=z\oplus \left((z \ll t_{3})\& m_{2} \right)\qquad \qquad \\
\displaystyle z=z\oplus \left(x \gg t_{4} \right)\qquad \qquad \\
\displaystyle u_{i+r}=z/(2_{w} -1) \qquad \qquad
$$
$t1,t2,t3,t4$ : integers
$m1,m2$ : bit-masks
[參考資料](https://www.sciencedirect.com/topics/computer-science/mersenne-twister)
* **Pseudocode**
```c
// Create a length n array to store the state of the generator
int[0..n-1] MT
int index := n+1
const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of (not lower_mask)
// Initialize the generator from a seed
function seed_mt(int seed) {
index := n
MT[0] := seed
for i from 1 to (n - 1) { // loop over each element
MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
}
}
// Extract a tempered value based on MT[index]
// calling twist() every n numbers
function extract_number() {
if index >= n {
if index > n {
error "Generator was never seeded"
// Alternatively, seed with constant value; 5489 is used in reference C code[53]
}
twist()
}
int y := MT[index]
y := y xor ((y >> u) and d)
y := y xor ((y << s) and b)
y := y xor ((y << t) and c)
y := y xor (y >> l)
index := index + 1
return lowest w bits of (y)
}
// Generate the next n values from the series x_i
function twist() {
for i from 0 to (n-1) {
int x := (MT[i] and upper_mask)
+ (MT[(i+1) mod n] and lower_mask)
int xA := x >> 1
if (x mod 2) != 0 { // lowest bit of x is 1
xA := xA xor a
}
MT[i] := MT[(i + m) mod n] xor xA
}
index := 0
}
```
實作
## 參照 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並改寫 quick sort
:::success
參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
:::
文章中提到的方法
```c
bool quickSort(int *arr, int elements) {
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R ;
beg[0]=0; end[0]=elements;
while (i>=0) {
L=beg[i];
R=end[i]-1;
if (L<R) {
piv=arr[L];
if (i==MAX_LEVELS-1) return NO;
while (L<R) {
while (arr[R]>=piv && L<R) R--;
if (L<R) arr[L++]=arr[R];
while (arr[L]<=piv && L<R) L++;
if (L<R) arr[R--]=arr[L];
}
arr[L]=piv; beg[i+1]=L+1;
end[i+1]=end[i]; end[i++]=L; }
else {
i--; }}
return YES; }
```
此函式利用 beg[] end[] 表示排序的範圍
L R 代表從兩端開始正在排序的數字
```
piv=arr[L];
```
* i=0
先將 arr[L] 放到 pivot
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=4]
B[label=5]
C[label=3]
D[label=6]
E[label=2]
F[label=8]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->A
}
{
rank="same"
R->F
}
A->B->C->D->E->F->NULL1
}
```
```c
while (L<R) {
while (arr[R]>=piv && L<R) R--;
if (L<R) arr[L++]=arr[R];
while (arr[L]<=piv && L<R) L++;
if (L<R) arr[R--]=arr[L];
}
```
R > pivot 的話 R 就向左移
若發現 R<pivot 且 arr[R] 比 arr[L] 小，則 arr[L]=arr[R]，L 向右移
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=4]
B[label=5]
C[label=3]
D[label=6]
E[label=2]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->A
}
{
rank="same"
R->E
}
A->B->C->D->E->F->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=2]
B[label=5]
C[label=3]
D[label=6]
E[label=2]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->B
}
{
rank="same"
R->E
}
A->B->C->D->E->F->NULL1
}
```
L < pivot 的話 L 就向右移
若發現 L > pivot 且 arr[R] 比 arr[L] 大，則 arr[R]=arr[L]，R 向左移
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=2]
B[label=5]
C[label=3]
D[label=6]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->B
}
{
rank="same"
R->D
}
A->B->C->D->E->F->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=2]
B[label=5]
C[label=3]
D[label=6]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->B
}
{
rank="same"
R->D
}
A->B->C->D->E->F->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=2]
B[label=3]
C[label=3]
D[label=6]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->C
R->C
}
A->B->C->D->E->F->NULL1
}
```
```c
arr[L]=piv; beg[i+1]=L+1;
end[i+1]=end[i]; end[i++]=L;
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=4]
A[label=2]
B[label=3]
C[label=4]
D[label=6]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->C
R->C
}
A->B->C->D->E->F->NULL1
}
```
arr[2]=4 beg[1]=3
end[1]=end[0]=6 end[0]=2 i=1
* i=1
L=3
R=5
piv=6
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=6]
A[label=2]
B[label=3]
C[label=4]
D[label=6]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->D
}
{
rank="same"
R->E
}
A->B->C->D->E->F->NULL1
}
```
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=6]
A[label=2]
B[label=3]
C[label=4]
D[label=5]
E[label=5]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->E
}
{
rank="same"
R->E
}
A->B->C->D->E->F->NULL1
}
```
最後 arr[L]=pivot
```graphviz
digraph graphname{
node[shape=box]
pivot[shape=plaintext,fontcolor=red]
L[shape=plaintext,fontcolor=red]
R[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
P[label=6]
A[label=2]
B[label=3]
C[label=4]
D[label=5]
E[label=6]
F[label=7]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same"
pivot->P
}
{
rank="same"
L->E
}
{
rank="same"
R->E
}
A->B->C->D->E->F->NULL1
}
```
TODO 實作
## 探討 [linux-list](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c) 與 [Linux list](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的差別
:::success
* Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- 參考資料: The Linux Kernel API - List Management Functions
:::
### linkedlist 的資料結構 & INIT_LIST_HEAD()
* linux-list
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
這裡定義為 doubly linkedlist
* Linux list
```c
struct list_head {
struct list_head *next, *prev;
};
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}
```
:::info
[WRITE_ONCE](https://github.com/torvalds/linux/blob/614cb5894306cfa2c7d9b6168182876ff5948735/tools/include/linux/compiler.h#L184)
Prevent the compiler from merging or refetching reads or writes.
Ensuring that the compiler does not fold, spindle, or otherwise mutilate accesses that either do not require ordering or that interact with an explicit memory barrier or atomic instruction that provides the required ordering.
The major use cases are:
* Mediating communication betweenprocess-level code and irq/NMI handlers, all running on the same CPU
* Ensuring that the compiler does not fold, spindle, or otherwisemutilate accesses that either do not require ordering or that interactwith an explicit memory barrier or atomic instruction that provides therequired ordering.
此函式是避免 compiler 對程式做優化而造成存取錯誤（race condition)，能禁止 compiler 對此做優化
[參考資料](https://stackoverflow.com/questions/34988277/write-once-in-linux-kernel-lists)
:::
這裡 `WRITE_ONCE()` 使 list 的兩個 pointer 皆指向自己，形成 circular linkedlist
[Kernel documentation](https://www.kernel.org/doc/)
## 研讀[A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)
:::success
研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
:::
論文中提到 5 種排序法，分別是 sediment sort, bubble sort, selection sort, merge sort, quick sort, and tree sort.
### sediment sort
* Pseudocode
```c
void BUBBLEsort(int a[], int n)
{
int bound = n-1, done = 0;
int swapped, i;
do {
swapped = -1;
for (i = 0; i < bound; i++)
if (a[i] > a[i+1]) {
SWAP(a[i], a[i+1]);
swapped = i;
}
if (swapped < 0)
done = 1;
else
bound = swapped;
} while (!done);
}
```
* The complexity : O(n^2^)
* The worst case : n(n+1)/2
### bubble sort
### selection sort
### merge sort
### quick sort
### tree sort
Sign in with Wallet
Connect another wallet