# 2021q1 Homework1 (quiz1)
contributed by < `WilliamShen0715` >
## Topic
- [x] 以 linked list 實現 QuickSort 的程式碼原理概述
- [x] 解決 random 多次執行結果相仿之問題
- [x] Non-recursive QuickSort ( Optimized QuickSort )
- [ ] 探討並改寫 linux-list 的 quick sort
- [ ] 基於 A Comparative Study of Linked List Sorting Algorithms 實現高效率的 linked list 排序演算法(https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)
## 針對 linked list 實作 Quick Sort
首先是一些基本型態的宣告以及副程式
### 定義節點
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### 增加新節點至串列
```cpp
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
參數為一個串列與一個節點
1. `node_t->next = *list` 將節點的下一個節點連接串列的排頭
2. `*list = node_t` 將排頭指向此節點
```graphviz
digraph{
rankdir=LR
p [label="new node" shape="box"]
n2 [label="list(A)" shape="box"]
n3 [label="B" shape="box"]
n4 [label="C" shape="box"]
remaining [label="......" shape="none"]
p -> n2 -> n3 -> n4 -> remaining
}
```
```graphviz
digraph{
rankdir=LR
p [label="list(new node)" shape="box"]
n2 [label="A" shape="box"]
n3 [label="B" shape="box"]
n4 [label="C" shape="box"]
remaining [label="......" shape="none"]
p -> n2 -> n3 -> n4 -> remaining
}
```
### 結合左右串列
```cpp
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next)
*left = right;
}
```
參數為左右串列
1. `while (*left) left = &((*left)->next)` 移至左串列末端的下一個節點(NULL)
2. `*left = right` 此節點指向右串列
```graphviz
digraph{
rankdir=LR
n2 [label="left(A)" shape="box"]
n3 [label="NULL" shape="none"]
n4 [label="last node" shape="box"]
remaining [label="......" shape="none"]
n2 -> remaining -> n4 -> n3
}
```
```graphviz
digraph{
rankdir=LR
n2 [label="A" shape="box"]
n3 [label="left(NULL)" shape="none"]
n4 [label="last node" shape="box"]
remaining [label="......" shape="none"]
n2 -> remaining -> n4 -> n3
}
```
```graphviz
digraph{
rankdir=LR
p [label="A" shape="box"]
n2 [label="last node" shape="box"]
n3 [label="..." shape="none"]
n4 [label="right" shape="box"]
remaining [label="......" shape="none"]
p -> remaining -> n2 -> n4 -> n3
}
```
### Quick Sort
``` cpp
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;
}
```
這裡就是 QuickSort 的主程式，主要分成4個步驟:
1. 首先選定 pivot ( 這裡選擇第一個節點當pivot ) 作為分割子問題(子串列)的參考節點
``` cpp
if (!*list) return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
第一行是遞迴的終止條件，接著選擇第一個節點當 pivot，並設定相關初始條件
```graphviz
digraph{
rankdir=LR
pivot [label="NULL" shape="none"]
left [label="value | next" shape="box"]
left -> pivot
}
```
2. 依序走訪整個串列並比較大小，將 pivot 之外的所有點接到 left 跟 right 上，以此分別得到 "全部比 pivot 小" , "pivot" , "全部比 pivot 大" 這3堆，其中大與小分別對應 left 跟 right ，也同時是此排列問題的子問題。
``` c
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);
}
```
以下為示意圖
```graphviz
digraph{
rankdir=LR
pivot [label="B" shape="box"]
left [label="A" shape="box"]
right [label="C" shape="box"]
pivot2 [label="F" shape="box"]
left2 [label="D" shape="box"]
right2 [label="E" shape="box"]
left -> pivot -> right-> left2 -> right2 -> pivot2
}
```
left:
```graphviz
digraph{
rankdir=LR
pivot [label="D(<pivot)" shape="box"]
left [label="A(<pivot)" shape="box"]
right [label="E(<pivot)" shape="box"]
left -> pivot -> right
}
```
right:
```graphviz
digraph{
rankdir=LR
pivot [label="C(>pivot)" shape="box"]
left [label="B(>pivot)" shape="box"]
right [label="F(>pivot)" shape="box"]
left -> pivot -> right
}
```
3. 對 left , right 2個子串列分別做遞迴呼叫，由此得到排序好的左串列跟右串列
``` c
quicksort(&left);
quicksort(&right);
```
這裡就因此以遞迴的方式排好 left 跟 right 中的所有節點
4.這裡以前面的副程式 list_concat 結合 left, right 跟 pivot ，最終得到排序好的字串
```cpp
void quicksort(node_t **list)
{
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
}
```
這個排好的串列即為最後的 result
```graphviz
digraph{
rankdir=LR
pivot [label="pivot" shape="box"]
left [label="left (Sorted)" shape="box"]
right [label="right (Sorted)" shape="box"]
left -> pivot -> right
}
```
## random 多次執行結果相仿之問題
:::danger
下方的「一般來說」對於論述有幫助嗎？充其量只是某一個使用方式，連解決方案都稱不上。工程人員說話要精準。
:notes: jserv
:::
呼叫 [random(3)](https://man7.org/linux/man-pages/man3/random.3.html) 會有輸出相同的問題，這是由於沒有設定用於亂數的種子。一般來說，給予包含時間資訊的種子可以有效避免這種問題。
e.g. 下面將 `srand(time(NULL))` 執行後再執行 rand()，再分別執行 2 次看看結果
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void main()
{
srand(time(NULL));
printf("%d\n", rand());
}
```
第一次:
```1979```
第二次:
```1985```
第三次:
```1995```
結果確實都不一樣。不過看起來卻不夠"亂"，這是因為當執行的時間很接近時，時間種子所的到的值也會相對接近。
由於 C 的 rand() 產生亂數的原理是基於 Linear Congruential Method 的 Pseudorandom， 也就是將前一項 rand 值以線性的方式對應，再取餘數
遞迴關係如下:
```Rn =( a*Rn-1 + b ) mod K```
a,b 是常數， K為給定的範圍區間
若未設定隨機函數的種子，則首項預設為0，否則首項就是給定的種子，因此，我們發現，儘管給定了時間作為亂數種子，卻沒有改變"決定亂數的方式"，造成亂數分佈不理想。
對於隨機性問題的改良方案，在 C++ STL 中有能夠調整對應參數的 [<random>](https://www.cplusplus.com/reference/random/) 可用。
在這之中，有別於常常被使用的時間做為種子，這個函式庫提供了專門用於產生亂數種子的 std::random_device ，因為它足夠隨機卻不適合預測大數的特性，可作為更好用的亂數種子。
使用上則必須在呼叫前分別事先執行2個步驟以確保數字的分布足夠亂:
1.設定引擎 ( engine )
2.設定資料分布 ( distribution )
這分別對應決定隨機的演算法以及給定數值的區間，以此可以得到符合預期的亂數
:::danger
注意作業規範：中英文間用一個空白字元區隔。注重細節並充分掌握，來日才可挑戰 Linux 核心這樣的龐然大物。
上述的描述不足以解釋亂數產生器原理和考量，請改進！
:notes: jserv
:::
---
## Non-recursive QuickSort ( Optimized QuickSort )
參考 [Optimized QuickSort](https://alienryderflex.com/quicksort/) 此篇的做法，並將它原本的陣列改為鏈結串列的方式呈現，基本想法是將原本遞迴的部分以堆疊的方式處理，將操作的頭尾指標放入堆疊中，再逐一取出來處理。
基本的宣告與初始化與上面遞迴版本的處理相同，只改變 quicksort 這個主程式片段。
程式碼如下:
```cpp
void quicksort_iterative(node_t **list)
{
#define MAX_LEVELS 1000
if (!*list)
return;
int i = 0, j = 0;
node_t *stack[MAX_LEVELS];
node_t *sorted;
sorted = NULL;
stack[0] = *list;
```
首先是對於相關面術語堆疊的宣告，這裡宣告了一個堆疊作為每次執行 quicksort 的位置紀錄，包含首尾，所以每次操作時接放入或取出頭部和尾部的指標。
這裡定義 MAX_LEVELS 代表的是堆疊的空間大小，須確保切割的片段數 < ( MAX_LEVELS\2 ) 以免造成記憶體錯誤。
從這裡也可以看出，前面所實作的遞迴版本，若每次的 pivot 選取不當，無法有效的區分出兩個區域，而是集中在一邊，則可能造成 O(n) 的空間複雜度，理想狀況則是 O(lgn) ，相較於這裡使用的方法，這裡每次切割的堆疊皆只會用到2個指標的大小，在空間的利用上有很大的改善。
```iterate2
while(i>=0 && i<MAX_LEVELS){
if(!stack[i]){
i--;
continue;
}
if(!stack[i]->next){
stack[i]->next = sorted;
sorted = stack[i];
i--;
continue;
}
node_t *pivot = stack[i];
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);
}
stack[i] = left;
stack[i+1] = pivot;
stack[i+2] = right;
i +=2;
}
*list = sorted;
}
```
這裡的行為就是檢查堆疊並將它一一取出，每次取出之後，跟遞迴版本的操作相同，分為左右兩個子串列，並將這兩個子串列連同 pivot 依序放入此堆疊中。
用這個方式不斷的操作此堆疊，拆分 left 跟 right ，直到 stack 為空，跳出此迴圈，此時得到的鏈結串列即為排序好的串列。
## 探討並改寫 linux-list 的 quick sort
## 基於 A Comparative Study of Linked List Sorting Algorithms 實現高效率的 linked list 排序演算法
Sign in with Wallet
Connect another wallet