# 2021q1 Homework (quiz1)
contributed by <`roger90810`>
- [x] 完成測驗並解釋
- [ ] 引入 [Pseudorandom number generator](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)
- [ ] [Optimized Quciksort (Non-Recursive)](https://alienryderflex.com/quicksort/)
- [ ] 改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例
- [ ] [研讀 A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)
## main 分析
* 程式一開始先建立有 20 個 node 的 list
* 這些 node 的值為 random 產生
```cpp
size_t count = 20;
node_t *list = NULL;
while (count--)
list = list_make_node_t(list, random() % 1024);
```
在給的 code 中沒有 list_make_node_t 這個 function，經過分析後得出此 function 為加入新的 node 到目前 list 的前面，並回傳目前 list 的第一個 node，因此自己加入 list_make_node_t :
```cpp
static node_t *list_make_node_t(node_t *list, int val)
{
node_t *node = (node_t *)malloc(sizeof(node_t));
node->value = val;
node->next = list;
return node;
}
```
此時已經可以透過 list_display 印出整個 list 的值
```
NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359
```
`NULL`, `EXIT_FAILURE`, `EXIT_SUCCESS` macro
在 C11 規格書中的 7.22 General utilities <stdlib.h> 提到 :
> The macros defined are NULL (described in 7.19);
EXIT_FAILURE
and
EXIT_SUCCESS
which expand to integer constant expressions that can be used as the argument to the
exit function to return unsuccessful or successful termination status
* 所以必須 `#include <stdlib.h>`
* 而 `NULL` 的定義則是在 `stddef.h` 中，但 `stdlib.h` 中已經有 `#include <stddef.h>`，所以可以不用自己再 include 一次
實際去查看 stdlib.h 中發現這兩個 macro 其實就是定義一個常數，和一般寫的 `return 0`; 是一樣意思
```cpp
/* We define these the same for all machines.
Changes from this to the outside world should be done in `_exit'. */
#define EXIT_FAILURE 1 /* Failing exit status. */
#define EXIT_SUCCESS 0 /* Successful exit status. */
```
實作 `free_list`
* 在給的程式碼中，有用到 `list_free`，但並沒有實作
* 因此自己加入這段程式碼，並透過 `valgrind` 測試確實 free 掉 list
```cpp
static void list_free(node_t **list)
{
node_t *p = *list;
while (p) {
node_t *n = p;
p = p->next;
free(n);
}
}
```
valgrind 輸出結果:
```shell
==1064== Memcheck, a memory error detector
==1064== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1064== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==1064== Command: ./list
==1064==
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
==1064==
==1064== HEAP SUMMARY:
==1064== in use at exit: 0 bytes in 0 blocks
==1064== total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated
==1064==
==1064== All heap blocks were freed -- no leaks are possible
==1064==
==1064== For lists of detected and suppressed errors, rerun with: -s
==1064== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
## quicksort 分析
quicksort 使用 divide and conquer 的方法，先將問題拆成多個子問題，解決子問題後，再將這些子問題合併，因此朝這個方向去思考，程式應該可以分成兩個部分
1. divide
2. combine
由以下程式碼可得知 pivot 的選擇為 list 的第一個元素
```cpp
node_t *pivot = *list
int value = pivot->value;
```
### 1. divide
* 由以下程式碼推斷，這裡是要將原 list 拆成 left, pivot, right 三個 list
* 首先利用 `pivot->next = NULL` 即可拆出只有 pivot 這個節點的 list
* 接著在 while loop 中，透過和 pivot 比較，可以將所有剩下的 node 拆成兩個 list
* `list left`，此 list 中所有節點的值皆`小於等於 pivot 的值`
* `list right`，此 list 中所有節點的值皆`大於 pivot 的值`
```graphviz
digraph left {
rankdir=LR;
node[shape=box];
left->"..."
"..."->"NULL"
}
```
```graphviz
digraph pivot {
rankdir=LR;
node[shape=box];
pivot->"NULL"
}
```
```graphviz
digraph right {
rankdir=LR;
node[shape=box];
right->"..."
"..."->"NULL"
}
```
```cpp
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL;
node_t *right = NULL;
// while loop ...
quicksort(&left);
quicksort(&right);
```
while loop 的部分，就是如何拆出 left 和 right 這兩個 list
* 由程式碼分析出，n 和 p 的用途為走訪 list
* n 表示當前的節點，p 表示下一個要進行比較的節點
* `list_add_node_t` 的用途為插入一個節點到 list 的前面，因此可推出這邊是要將節點 n 插入到 `list AAA` 或 `list BBB` 的前面
* 觀察程式碼也發現，n 要插到哪裡是由 `n->value > value?` ，也就是和 pivot 的值比較來決定，因此可得出
* 若 n 的值大於 pivot 的值，則需要插入到 `list right`，並且 n 成為 `list right` 的第一個節點
* 若 n 的值小於等於 pivot 的值，則需要插入到 `list left`，並且 n 成為 `list right` 的第一個節點
```cpp
while(p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value? AAA : BBB, n);
}
```
所以得出
* AAA = `(e) &right`
* BBB = `(c) &left`
### 2. Combine
* 將 list 拆開 sort 後，需要將結果合併回來
* 因此需要合併 ```left```, ```pivot```, ```right``` 三個 list
首先分析 `list_concat` 的作法
* 先猜測此函式的用途為在一個 list 後面接上另一個 list
* 只需要將 list 中最後一個節點的 `next` 接到另一個 list 中第一個節點即可
* 這裡的做法 :
* left 一開始指到 list1 的第一個節點，並透過 while loop，最終會指到 list1 `最後一個節點的 next，此時為 NULL`
* 將 `NULL 改成 list2 的第一個節點`，就會使 list1 的最後一個節點接到 list2 的第一個節點，即可完成 concat
```cpp
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
```graphviz
digraph list {
rankdir=LR;
node[shape=box];
first2[color=blue]
"...."[color=blue]
"end2"[color=blue]
first2->"...."
"...."->end2
first1[color=red];
"..."[color=red];
end1[color=red];
first1->"..."
"..."->end1
}
```
```graphviz
digraph list {
rankdir=LR;
node[shape=box];
first1[color=red];
"..."[color=red];
end1[color=red];
first1->"..."
"..."->end1
first2[color=blue]
"...."[color=blue]
"end2"[color=blue]
first2->"...."
"...."->end2
end1->first2
}
```
所以得出
* LLL = `(c) left = &((*left)->next);`
分析完 list_concat 的方法後，即可得知只要依序將 left, pivot, right 接起來，就可以得到遞增順序排序的 list
```cpp
node_t *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
```
所以得出
* CCC = `(b) list_concat(&result, pivot); list_concat(&result, right);`
經過程式碼驗證，可得到正確結果
完整程式碼:
* list.h
```cpp
#ifndef LIST_H_INCLUDE
#define LIST_H_INCLUDE
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
// add node to the front of the list
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); // LLL
*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;
}
#endif
```
* list.c
```cpp
#include "list.h"
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 val)
{
node_t *node = (node_t *) malloc(sizeof(node_t));
node->value = val;
node->next = list;
return node;
}
static void list_free(node_t **list)
{
node_t *p = *list;
while (p) {
node_t *n = p;
p = p->next;
free(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;
}
```
* 輸出結果:
```
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
```
Sign in with Wallet
Connect another wallet