owned this note
owned this note
Published
Linked with GitHub
## 介紹
根據作業 [測驗 1](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1) 介紹的 qsort 演算法原理介紹
:::warning
此處提到的方法是以 swap 為主體，
利用 `L` 與 `R` 去**紀錄需交換的數量**，
再用 `begin[]` 與 `end[] `**作為堆疊，用來紀錄比較的範圍。**
假定下方是起始的陣列內容。
採取 `head` 作為 `pivot`，
並且
`L` 會從左邊開始掃，紀錄有多少值小於 pivot，
`R` 從右邊開始，紀錄有多少值大於 pivot。
:::
### step 0
在 `void quick_sort(node_t **list)` 中會用到下列變數
* `*begin[max_level] `和 `*end[max_level] `：當成堆疊，用來紀錄
0. `*list` 的頭節點，尾端節點
1. `pivot` 節點
2. `*left` 串列的**頭端**和**尾端**節點
3. `*right` 串列的**頭端**和**尾端**節點
* R 變數：會從**右邊**開始掃 `*list` 串列
* L 變數：會從**左邊**開始掃 `*list `串列
在 L 掃 `*list `串列過程中，會用到
`*left` 串列：用來紀錄有多少節點值小於 pivot，
`*right` 串列：用來紀錄有多少節點值大於 pivot。
```c
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];// begin 和 end 陣列是用來存節點位址
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;//頭節點位址
end[0] = list_tail(list);//末端節點位址
```
```graphviz
digraph {
a[label="NULL", shape=box]
b[label="NULL", shape=box]
node [shape=box]
graph [rankdir = "LR"];
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext];
pivot -> 4;
L -> 4;
rank=same {4 pivot L};
R -> 7;
rank=same {7 R};
list->4;
left->a;
right->b;
}
```
陣列的 Graphviz 畫法參考
[Graphviz draw array data structure](https://stackoverflow.com/questions/40541091/graphviz-draw-array-data-structure)
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"" -> "begin[i]" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> begin[0] = *list; | <f1> | <f2> | <f3> | <f4> | <f5> ", color=white];
begin [label="<f0> 4 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; ""; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers:f0 -> begin:f0;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
""->"end[i]" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> end[0] = list_tail(list); | <f1> | <f2> | <f3> | <f4> | <f5> ", color=white];
end [label="<f0> 7 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; ""; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers:f0 -> end:f0;
}
```
---
### step 1
從`*begin[max_level] `取出一個 index 矩陣資料`begin[i]` 當成 L 節點
從`*end[max_level] `取出一個 index 矩陣資料`end[i] `當成 R 節點
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
```
當 `i=0;`時為例
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]" [color=white];
pointers [label="4", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 4 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f0[label=" *L = begin[0]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]" [color=white];
pointers [label="7", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 7 | <f1> [1] | <f2> [2] | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; begin }
edge [color=blue];
pointers-> begin:f0[label=" *R = end[0]",dir=back];
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=18];
"P"->1 [color=white];
node [shape=box]
pivot[label="pivot", shape=box,color=white];
pivot->4[color=white];
rank=same{4 1};
4->1;
}
```
---
### step 2.
比較的**節點n value**(`n->value` ) 和 **pivot 節點的 value** (`value` )
`list_add(n->value > value ? &right : &left, n);`
* `n->value` 值大於 pivot ，則放在 `right` 串列（代表 pivot的右邊）
* 若 `n->value` 值大於 pivot 為否，代表 `n->value` 值小於 pivot ，則放在 `left `串列（代表 pivot 的左邊）
```c
while (p) {
node_t *n = p;
p = p->next;//CCCC
list_add(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=18];
"P"->1 [color=white];
node [shape=box]
pivot[label="pivot", shape=box,color=white];
pivot->4[color=white];
rank=same{pivot 4 7};
4->7;
}
```
:::danger
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
*list = node_t;
}
```
因此經過 `list_add(n->value > value ? &right : &left, n);` 後
right鍊結：
* 頭端節點為 7
* 尾端節點為 5
left鍊結：
* 頭端節點為 2
* 尾端節點為 1
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
1->3->2[dir=back];
5->7[dir=back];
node [shape=plaintext, fontsize=18];
"left"->1[color=white];
"right"->5[color=white];
}
```
:::
---
### step3.
比較結束，將 `begin[i]` 與 `end[i]` 儲存 `left` 的**頭**與**尾**，
`begin[i+1]` 與 `end[i+1]` 儲存 `pivot `，
`begin[i+2]` 與 `end[i+2]` 儲存 `right` 的**頭**與**尾**，
將 i 設為 i + 2 ，也就是堆疊的最上層
```c
if (L != R) {
...
begin[i] = left;//將 begin[i] 設為 left 的頭
end[i] = list_tail(&left) ;//DDDD end[i] 設為 left 的尾
begin[i + 1] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ，
end[i + 1] = pivot;
begin[i + 2] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2
//，也就是堆疊的最上層，
end[i + 2] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
```
當 `i=0;`時為例
```c
begin[0] = left;//將 begin[i] 設為 left 的頭
end[0] = list_tail(&left) ;//DDDD end[i] 設為 left 的尾
begin[1] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ，
end[1] = pivot;
begin[2] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2
//，也就是堆疊的最上層，
end[2] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
//"end[i]" ->"begin[i]" [color=white];
"begin[i]"->"end[i]" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 7 (right 頭) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (right 尾) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "end[i]"; end }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
}
```
---
## 單步執行後面程式過程
### 當 i=2 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[2], *R = end[2];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="5", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (right 尾) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f2[label=" *R = end[2]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="7", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 7 (right 頭) | <f3> [3] | <f4> [4] | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f2[label=" *L=begin[2]",dir=back];
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
7->5;
node [shape=plaintext, fontsize=18];
"L"->7 [color=white];
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
rank=same{pivot 5 7};
7->5;
pivot[label="pivot", shape=box,color=white];
rank=same{pivot 7};
pivot->7[color=white];
node [shape=plaintext, fontsize=18];
"p"->5 [color=white];
}
```
#### step2
```c
while (p) {
node_t *n = p;
p = p->next;//CCCC
list_add(n->value > value ? &right : &left, n);
}
```
:::danger
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
*list = node_t;
}
```
因此經過 `list_add(n->value > value ? &right : &left, n);` 後
right鍊結：
* 頭端節點為 NULL
* 尾端節點為 NULL
left鍊結：
* 頭端節點為 5
* 尾端節點為 5
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
5;
node [shape=plaintext, fontsize=18];
"left"->5;
"right"->"NULL";
}
```
:::
#### step3
當 `i=2;`時為例
```c
begin[2] = left;//將 begin[i] 設為 left 的頭
end[2] = list_tail(&left) ;//DDDD end[i] 設為 left 的尾
begin[3] = pivot;//begin[i+1] 與 end[i+1] 設為 pivot ，
end[3] = pivot;
begin[4] = right;//begin[i+2] 與 end[i+2] 設為 right 的頭與尾，將 i 設為 i + 2
//，也就是堆疊的最上層，
end[4] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
//"end[i]" ->"begin[i]" [color=white];
"begin[i]"->"end[i]" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "end[i]"; end }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
}
```
下一步執行 i=4 的情況
---
### 當 i=4 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[4], *R = end[4];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="NULL", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f4[label=" *R = end[4]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="NULL", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f4[label=" *L=begin[4]",dir=back];
}
```
:::warning
因為 `node_t *L = begin[4], *R = end[4];` **取到的值都是 NULL ( L==R 的條件)**
所以直接跳到
```c
else {
if (L) /// L 為 null 所以不用 list_add（）
list_add(&result, L);
i--;
}
```
執行完 `i--`，回到 `i=3` 的情況，重新執行 step1-step3 步驟
:::
---
### 回到 i=3 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[3], *R = end[3];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="7", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f3[label=" *R = end[3]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="7", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f3[label=" *L=begin[3]",dir=back];
}
```
:::warning
因為 `node_t *L = begin[3], *R = end[3];` **取到的值都是 節點7 ( L==R 的條件)**
所以直接跳到
```c
else {
if (L) /// L 為 節點7 所以執行 list_add（）
list_add(&result, L);
i--;
}
```
`result` 插入 L 節點
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
7;
node [shape=plaintext, fontsize=18];
rank=same{"result " 7};
}
```
執行完 `i--`，回到 `i=2` 的情況，重新執行 step1-step3 步驟
:::
---
### 回到 i=2 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[2], *R = end[2];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="5", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f2[label=" *R = end[2]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="5", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f2[label=" *L=begin[2]",dir=back];
}
```
:::warning
因為 `node_t *L = begin[2], *R = end[2];` **取到的值都是 節點5 ( L==R 的條件)**
所以直接跳到
```c
else {
if (L) /// L 為 節點5 所以執行 list_add（）
list_add(&result, L);
i--;
}
```
`result` 插入 L 節點
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
7->5[dir=back];
node [shape=plaintext, fontsize=18];
rank=same{"result" 7};
}
```
執行完 `i--`，回到 `i=1` 的情況，重新執行 step1-step3 步驟
:::
---
### 回到 i=1 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[1], *R = end[1];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="4", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f1[label=" *R = end[1]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="4", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f1[label=" *L=begin[1]",dir=back];
}
```
:::warning
因為 `node_t *L = begin[1], *R = end[1];` **取到的值都是 節點4 ( L==R 的條件)**
所以直接跳到
```c
else {
if (L) /// L 為 節點4 所以執行 list_add（）
list_add(&result, L);
i--;
}
```
`result` 插入 L 節點
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
7->5->4[dir=back];
node [shape=plaintext, fontsize=18];
rank=same{"result " 7};
}
```
執行完 `i--`，回到 `i=1` 的情況，重新執行 step1-step3 步驟
:::
---
### 回到 i=0 時
#### step1
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];//將 L 與 R 初始化成 begin[0] 和 end[0] ，分別對應鏈結串列的頭跟尾
if (L != R) {
node_t *pivot = L;//選定 L 為 pivot
value = pivot->value;//記下 pivot 節點的 value
node_t *p = pivot->next;//*p 為pivot的下一個節點位址
//因為*p已經先備份好 pivot的下一個節點了
pivot->next = NULL;//因此原來的 pivot先把next 填 NULL，避免誤觸 pivot移動到下個節點
...
```
當 `i=0;`時
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"R" ->"end[i]"[color=white];
pointers [label="1", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
end [label="<f0> 1 (left 尾) | <f1> pivot 4 | <f2> 5 (left 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "R"; pointers }
{ rank=same; "end[i]"; end }
edge [color=blue];
pointers-> end:f0[label=" *R = end[0]",dir=back];
}
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
"L" ->"begin[i]"[color=white];
pointers [label="2", color=black,shape=box];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 2 (left頭) | <f1> pivot 4 | <f2> 5 (left 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "L"; pointers }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
pointers-> begin:f0[label=" *L=begin[0]",dir=back];
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
2->3->1;
node [shape=plaintext, fontsize=18];
"L"->2 [color=white];
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
2;
node [shape=plaintext, fontsize=18];
"pivot"->2 [color=white];
}
```
#### step2
```c
while (p) {
node_t *n = p;
p = p->next;//CCCC
list_add(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
3->1;
node [shape=plaintext, fontsize=18];
"p"->3 [color=white];
node [shape=box]
pivot[label="pivot", shape=box,color=white];
pivot->2[color=white];
rank=same{pivot 2 3};
2->3;
}
```
:::danger
```c
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;//因為新節點的 next 位址都是指向 list head，所以串鍊結時是倒著串
*list = node_t;
}
```
因此經過 `list_add(n->value > value ? &right : &left, n);` 後
right鍊結：
* 頭端節點為 1
* 尾端節點為 1
left鍊結：
* 頭端節點為 3
* 尾端節點為 3
pivot:
* 節點2
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
3;
1;
node [shape=plaintext, fontsize=18];
"right"->3;
"left"->1;
}
```
:::
#### step3
當 `i=0;`時為例
```c
begin[0] = left;//將 begin[0] 設為 left 的頭
end[0] = list_tail(&left) ;//DDDD end[0] 設為 left 的尾
begin[1] = pivot;//begin[1] 與 end[1] 設為 pivot ，
end[1] = pivot;
begin[2] = right;//begin[2] 與 end[2] 設為 right 的頭與尾，將 i 設為 i + 2
//，也就是堆疊的最上層，
end[2] =list_tail(&right) ;//EEEE
left = right = NULL;
i += 2;
```
```graphviz
digraph {
node [shape=plaintext, fontcolor=red, fontsize=18];
//"end[i]" ->"begin[i]" [color=white];
"begin[i]"->"end[i]" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
begin [label="<f0> 1 (left頭) | <f1> pivot 2 | <f2> 3 (right 頭) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
end [label="<f0> 1 (left 尾) | <f1> pivot 2 | <f2> 3 (right 尾) | <f3> pivot 7 | <f4> NULL | <f5> [5]", color=blue, fillcolor=lightblue, style=filled];
{ rank=same; "end[i]"; end }
{ rank=same; "begin[i]"; begin }
edge [color=blue];
}
```
### 回到 i=2 時
#### step1
:::warning
因為
```c
*L = begin[2]～begin[0];
*R = end[2]～end[0];
```
都是 `L==R` 相同節點值
```c
else {
if (L) /// L 為 節點4 所以執行 list_add（）
list_add(&result, L);
i--;
}
```
所以都是重複執行，將 L 節點（`begin[2]～begin[0];` ） 依序插入到 `result` 串列中，變成
```graphviz
digraph {
node [shape=box]
graph [rankdir = "LR"];
7->5->4->3->2->1[dir=back];
node [shape=plaintext, fontsize=18];
rank=same{"result 頭" 1};
rank=same{"result 尾" 7};
}
```
:::
---
## 總結
:::success
* Quick Sort 分類成兩個串列
1. 大於 pivot 的 right 串列
2. 小於 pivot 的 left 串列
* 本來在 Quick Sort 遞迴版，
只要將這兩個串列再代入 `void quick_sort(node_t **list)`
就能進一步排序 right 串列，left 串列裡面的資料大小
* 但是我們 Quick Sort 是**用 "非遞迴" 寫法，**
所以**得拆成兩個子陣列排序**
例如 拆成
`left` 陣列 [5,7]
`right` 陣列 [1,3,2]
兩個子陣列得另外排序
* 幸好我們是用 link list 串列寫法，
**所以不用再額外分配連續空間的子陣列空間**
left 子串列 5-->7
right 子串列 1-->3-->2
* **為了方便管理每個子串列
因此用陣列 `begin[]` 和 `end[]`** 來管理每個子陣列的
head 節點，尾節點，pivot
才能方便調閱每個子串列
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
