# 2025q1 Homework2 (quiz1+2)
contributed by < `TING0419` >
## 第一週
### 測驗一
### 測驗二
### 測驗三
用8個數字模擬 `非遞迴Quicksort`
```graphviz
digraph QuickSort_Step1 {
node [shape=record];
label="Step 1: Initial List";
list [label="4 | 19 | 6 | 23 | 11 | 30 | 3 | 8", shape=box];
}
```
```graphviz
digraph QuickSort_Step2 {
node [shape=record];
label="Step 2: Select Pivot = 4 and Partition";
stack1 [label="begin[] = [4, 19, 6, 23, 11, 30, 3, 8]", shape=box];
pivot1 [label="Pivot: 4", shape=ellipse];
left1 [label="Left: 3", shape=box];
right1 [label="Right: 19 | 6 | 23 | 11 | 30 | 8", shape=box];
stack1 -> pivot1;
pivot1 -> left1;
pivot1 -> right1;
}
```
```graphviz
digraph QuickSort_Step3 {
node [shape=record];
label="Step 3: Select Pivot = 19 and Partition";
stack2 [label="begin[] = [6, 11, 8] + [Pivot: 19] + [23, 30]", shape=box];
pivot2 [label="Pivot: 19", shape=ellipse];
left2 [label="Left: 6 | 11 | 8", shape=box];
right2 [label="Right: 23 | 30", shape=box];
stack2 -> pivot2;
pivot2 -> left2;
pivot2 -> right2;
}
```
```graphviz
digraph QuickSort_Step4 {
node [shape=record];
label="Step 4: Select Pivot = 6 and Partition";
stack3 [label="begin[] = [6] + [8 -> 11]", shape=box];
pivot3 [label="Pivot: 6", shape=ellipse];
left3 [label="Left: None", shape=box];
right3 [label="Right: 8 | 11", shape=box];
stack3 -> pivot3;
pivot3 -> left3;
pivot3 -> right3;
}
```
```graphviz
digraph QuickSort_Step5 {
node [shape=record];
label="Step 5: Select Pivot = 8 and Partition";
stack4 [label="begin[] = [8] + [11]", shape=box];
pivot4 [label="Pivot: 8", shape=ellipse];
left4 [label="Left: None", shape=box];
right4 [label="Right: 11", shape=box];
stack4 -> pivot4;
pivot4 -> left4;
pivot4 -> right4;
}
```
```graphviz
digraph QuickSort_Step6 {
node [shape=record];
label="Step 6: Select Pivot = 23 and Partition";
stack5 [label="begin[] = [23] + [30]", shape=box];
pivot5 [label="Pivot: 23", shape=ellipse];
left5 [label="Left: None", shape=box];
right5 [label="Right: 30", shape=box];
stack5 -> pivot5;
pivot5 -> left5;
pivot5 -> right5;
}
```
```graphviz
digraph QuickSort_Step7 {
node [shape=record];
label="Step 7: Final Sorted List";
sorted [label="Sorted: 3 | 4 | 6 | 8 | 11 | 19 | 23 | 30", shape=box];
}
```
該程式實作了一個基於 `struct list_head `的 **快速排序**，並進行了鏈表構造、`shuffle`、排序與驗證。
---
#### 1. 定義鏈表節點 (node_t)
```c
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
- `value`：儲存數值。
- `list`：使用 Linux Kernel 的 `list_head` 來形成雙向鏈表。
---
#### 2. 相關工具函式
##### (1) 獲取鏈表最後一個節點
```c
struct list_head *list_tail(struct list_head *head)
{
while (head && head->next)
head = head->next;
return head;
}
```
- 作用：尋找並回傳鏈表的最後一個節點。
##### (2) 計算鏈表長度
```c
int list_length(struct list_head *left)
{
int n = 0;
struct list_head *node;
list_for_each(node, left) n++;
return n;
}
```
- 作用：遍歷鏈表並計算節點數量。
##### (3) 重新構建雙向鏈表
```c
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
head->prev = prev;
}
```
- **作用**：重新構建雙向鏈表，確保 `prev` 指標正確。
---
#### 3. Quick Sort 實作
##### (1) 初始化變數
```c
int n = list_length(list);
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
```
- `max_level = 2 * n`：模擬遞迴的最大深度。
- `begin[]`：模擬遞迴函式的堆疊，儲存子鏈表的開頭。
- `result`：存放最終排序好的鏈表。
- `left` 和 `right`：用來存放比 Pivot 小或大的節點。
##### (2) 執行 Quick Sort
```c
begin[0] = list->next;
list->prev->next = NULL; // Break the link
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
```
- `begin[0] = list->next` 設定初始未排序鏈表的開頭。
- `list->prev->next = NULL` 斷開鏈表，確保不會影響後續操作。
##### (3) 選擇 Pivot 並進行分割
```c
if (L != R) {
struct list_head *pivot = L;
value = list_entry(pivot,node_t,list)->value;
struct list_head *p = pivot->next;
pivot->next = NULL; /* Break the link next to pivot */
```
- 選擇 Pivot（第一個節點）
- 遍歷剩餘節點，依據值大小分到 `left` 或 `right`
```c
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = list_entry(n,node_t,list)->value;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
```
- 比 Pivot 大的值進入 `right`
- 比 Pivot 小或相等的值進入 `left`
##### (4) 記錄排序區塊並繼續排序
```c
begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;
```
##### (5) 處理單獨節點（回溯）
```c
else {
if (L) {
L->next = result;
result = L;
}
i--;
}
```
---
#### 4. 其他功能
##### (1) 構造鏈表
```c
void list_construct(struct list_head *list, int n)
{
node_t *node = malloc(sizeof(node_t));
node->value = n;
list_add(&node->list, list);
}
```
##### (2) 釋放鏈表記憶體
```c
void list_free(const struct list_head *head)
{
node_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
free(entry);
}
}
```
##### (3) 驗證鏈表是否排序
```c
static bool list_is_ordered(const struct list_head *head)
{
int value = list_entry(head->next, node_t, list)->value;
node_t *entry;
list_for_each_entry (entry, head, list) {
if (entry->value < value)
return false;
value = entry->value;
}
return true;
}
```
---
#### 5. 主程式執行流程
```c
int main(int argc, char **argv)
{
struct list_head *list = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(list);
size_t count = 100000;
int *test_arr = malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i){
test_arr[i] = i;
}
shuffle(test_arr, count);
```
1. **初始化鏈表**
2. **建立長度 `100000` 的數列**
3. **隨機打亂（shuffle）測試不同輸入情況**
```c
while (count--)
list_construct(list, test_arr[count]);
quick_sort(list);
assert(list_is_ordered(list));
list_free(list);
free(test_arr);
printf("Test passed \n");
return 0;
```
---
#### 結論
- 使用 `Quick Sort` 演算法來對 **雙向鏈表** 進行排序。
- 透過 `shuffle` 測試不同輸入情況。
- 最後驗證排序結果是否正確，確保排序邏輯沒有錯誤。
## 第二週
### 測驗一
#### 1. 簡介
這段程式碼的主要功能是：
1. **隨機打亂陣列** `values[256]`。
2. **將 `values[]` 中的數據插入 `testlist` 雙向鏈表**。
3. **使用 `qsort()` 排序 `values[]`**。
4. **使用 `list_quicksort()` 進行鏈表排序**。
5. **比對 `testlist` 和 `values[]` 確保排序正確**。
---
#### 2. List QuickSort 實作
1. 基礎情況處理
```c
if (list_empty(head) || list_is_singular(head))
return;
```
- 若 `head` 為空或只有一個元素，直接返回。
2. 初始化 `list_less` 和 `list_greater`
```c
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
- 用來存放小於和大於 `pivot` 的節點。
3. 選擇 `pivot` 並將其從鏈表移除
```c
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
```
- 取出 `pivot` 並從鏈表刪除，以便進行分割。
4. 遍歷鏈表，將元素分配到 `list_less` 和 `list_greater`
```c
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
```
- 小於 pivot 的節點放入 `list_less`。
- 大於 pivot 的節點放入 `list_greater`。
- `list_move_tail()` 確保 QuickSort Stable。
- 若改成`list_move` 則會unstable，交換後原排序在前的會變成在後。
5. **遞迴處理 `list_less` 和 `list_greater`**
```c
list_quicksort(&list_less);
list_quicksort(&list_greater);
```
- 對 `list_less` 和 `list_greater` 分別進行 QuickSort。
6. **重新合併鏈表**
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
- **先加入 pivot**。
- **接著拼接 `list_less`**。
- **最後拼接 `list_greater`**。
---
#### 3. `random_shuffle_array()` - Fisher-Yates 洗牌演算法
##### 原始版
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
uint16_t j = get_unsigned16() % (i + 1);
operations[i] = operations[j];
operations[j] = i;
}
}
```
錯誤點：
- 這段程式碼會 **覆蓋原始數據**，導致某些數字遺失。
##### 改進版（使用 Fisher-Yates Shuffle）
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = len - 1; i > 0; i--) {
uint16_t j = get_unsigned16() % (i + 1);
operations[i] = operations[j];
operations[j] = i;
}
printf("\n ");
}
```
改進點：
- 交換 `operations[i]` 和 `operations[j]`，確保數據不丟失。
- 避免`Modulo Bias`取模偏差，確保隨機分布均勻。
---
#### 4. `main()` - 驗證排序是否正確
1. 初始化 `values[]` 並洗牌
```c
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
```
- 這會打亂 `values[]`。
2. 將 `values[]` 的數據插入 `testlist`
```c
for (i = 0; i < ARRAY_SIZE(values); i++) {
item = (struct listitem *) malloc(sizeof(*item));
item->i = values[i];
list_add_tail(&item->list, &testlist);
}
```
- 用 `malloc()` 分配節點，並加入鏈表尾部。
3. 排序 `values[]`（作為基準）
```c
qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
```
- 使用標準 `qsort()` 來排序陣列。
4. 對 `testlist` 執行 `list_quicksort()`
```c
list_quicksort(&testlist);
```
- 對雙向鏈表進行 QuickSort。
5. 驗證排序結果
```c
list_for_each_entry_safe (item, is, &testlist, list) {
assert(item->i == values[i]);
list_del(&item->list);
free(item);
i++;
}
```
- 確保鏈表排序結果與 `values[]` 一致。
- 釋放鏈表的記憶體。
---
### 測驗二
### 測驗三
Sign in with Wallet
Connect another wallet