# 2021q1 Homework1 (quiz1)
contributed by < `IzsKon` >
## 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現
**題目**
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
LLL = ?
a) ```left = left->next```
b) ```left = (*left)->next```
c) ```left = &((*left)->next)```
d) ```*left = (*left)->next```
**答: c**
**解釋:**
函式`list_concat`功能在串接(concatenate)兩個 linked list，while 迴圈的目的在於找到`left`的結尾(NULL)。`left`的型態為指標的指標，因此用`*left`取得下一個 node ，並將下一個 node 的位置(`&`)存入`left`
```graphviz
digraph graphname{
node[shape=box]
list[shape=plaintext]
rankdir=LR
{
rankdir = LR
head[shape=plaintext]
B
C
D
…[shape=plaintext]
}
{
rank="same";
list->head->A
}
A->B->C->D->…
}
```
```graphviz
digraph graphname{
node[shape=box]
list[shape=plaintext]
rankdir=LR
{
rankdir = LR
head[shape=plaintext]
B
C
D
…[shape=plaintext]
}
{
rank="same";
head->A
}
{
rankdir = EW
rank="same";
list->B
}
A->B->C->D->…
}
```
```graphviz
digraph graphname{
node[shape=box]
list[shape=plaintext]
rankdir=LR
{
rankdir = LR
head[shape=plaintext]
B
C
D
…[shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
list->C
}
A->B->C->D->…
}
```
**題目**
```c=
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
```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;
}
```
AAA = ?
a) ```&pivot```
b) ```pivot```
c) ```&left```
d) ```left```
e) ```&right```
f) ```right```
**答: e**
BBB = ?
a) ```&pivot```
b) ```pivot```
c) ```&left```
d) ```left```
e) ```&right```
f) ```right```
**答: c**
CCC = ?
(a) ```list_concat(&result, right)```
b) ```list_concat(&result, pivot); list_concat(&result, right)```
c) ```list_concat(&result, right); list_concat(&result, pivot)```
**答: b**
**解釋:**
這裡就是實作 quicksort 的程式碼。quiksort 的運作方式是將數字以 pivot 為準，切割為數值較大的一邊和數值較小的一邊，然後對每一段繼續做相同的是直到無法再切割，最後再將所有東西合併。
`CCC`就是在將每個 linked list 串接的步驟。因為要求是由小排到大，因次串接的的順序是`left`，`pivot`然後`right`。
while 迴圈的部分就是在將 list 切成兩個，一個是數值比`value`還小的`left`，一個是數值比`value`還大的`right`。
`list_add_node_t`接受的第一個參數型態是`node_t **`，是一個指標的指標，因此這裡放的應該是指`right`和`left`的位置`&right`和`&left`。
- 一開始的linlked list
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
3->2->5->1->4
}
```
- 將list切割成數值較小的`left`與數值較大的`right`
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
right[shape=plaintext]
left[shape=plaintext]
pivot[shape=plaintext]
}
left->2->1
pivot->3
right->5->4
}
```
- 將`left`與`right`繼續做切割，直到一方為NULL(以下以繼續切割`left`為例)
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
left[shape=plaintext]
}
left->2->1
}
```
切割後:
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
right[shape=plaintext]
left[shape=plaintext]
pivot[shape=plaintext]
NULL[shape=plaintext]
}
left->1
pivot->2
right->NULL
}
```
- 若一方為NULL，則依`left`，`pivot`，`right`的順序將它們與最終結果`result`串接
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
result[shape=plaintext]
}
result->1->2
}
```
### 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
因為`random()`並不是真正的隨機，而是公式算出來的，因此每次一開始的亂數種子相同，得到的結果也會相同，為了避免每次執行結果相同，可以使用時間來做為亂數種子```srandom(time(NULL));```
不過因為`time()`的時間精度為秒，因此在同一秒內執行仍然會得出相同結果。有幾種改進方式:
1. 增加時間的精度，使用`gettimeofday()`得到亂數種子，使時間精度詳細到微秒。
2. 使用別的 Pseudorandom number generator，例如`arc4random_uniform()`是使用 entrophy 作為亂數種子。
## 參考 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; }
```
原本使用遞迴的quicksort是利用呼叫function會出現的stack來儲存資料，上面的程式碼將那些隱藏的stack改成了用自己的stack`beg[]`和`end[]`來儲存，可以自行控制stack的最大深度，同時也減少了每次呼叫function所花費的時間。
**實作的程式碼:**
```c=
bool qsort(node_t **list)
{
#define MAX_LEVELS 1000
node_t *stack[MAX_LEVELS] = {*list};
node_t *result = NULL;
int i = 0;
while (i >= 0) {
node_t *left = NULL, *right = NULL, *pivot = NULL;
if (stack[i] != NULL && stack[i]->next != NULL){
if (i == MAX_LEVELS - 1)
return false;
pivot = stack[i];
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
stack[i++] = right;
stack[i++] = pivot;
stack[i] = left;
}
else {
if (stack[i] != NULL)
list_concat(&result, stack[i]);
i--;
}
}
*list = result;
return true;
}
```
實作的部分和參考有一些不同部分。參考程式碼式針對陣列去做排序，而非這裡使用的 singly linked list，因此不適合從後面的數字往前找，所以只有使用到一個`stack`，而非前面的`beg[]`和`end[]`。
這裡實作的方式前半部與使用遞迴的方式相同，就是將 linked list 以`pivot`切割成`right`與`left`，考慮到最後的`list_concat()`是將`result`放在`list`的左邊，因此依`right`、`pivot`、`left`的順序將其放入`stack`，使得`left`會最先被串接到`result`，其次才是`pivot`、`left`。
**範例:**
- 初始的 linlked list
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
head[shape=plaintext]
}
head->3->2->5->1->4
}
```
stack:
|head| | | | |...|
|----|-|-|-|-|---|
- 做初次切割
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
right1[shape=plaintext]
left1[shape=plaintext]
pivot1[shape=plaintext]
}
left1->2->1
pivot1->3
right1->5->4
}
```
stack:
|right1|pivot1|left1| | |...|
|------|------|-----|-|-|---|
- pop `left1`，繼續切割
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
right2[shape=plaintext]
left2[shape=plaintext]
pivot2[shape=plaintext]
NULL[shape=plaintext]
}
left2->1
pivot2->2
right2->NULL
}
```
stack:
|right1|pivot1|right2|pivot2|left2|...|
|------|------|------|------|-----|---|
- 直到 pop 出來的`list == NULL` 或是 `list->next == NULL`(只剩一個元素)，將 pop 出來的 list 串接到`result`
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
result[shape=plaintext]
}
result->1
}
```
stack:
|right1|pivot1|right2|pivot2| |...|
|------|------|------|------|-|---|
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
result[shape=plaintext]
}
result->1->2
}
```
stack:
|right1|pivot1|right2| | |...|
|------|------|------|-|-|---|
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
{
result[shape=plaintext]
}
result->1->2
}
```
stack:
|right1|pivot1| | | |...|
|------|------|-|-|-|---|
Sign in with Wallet
Connect another wallet