2025q1 Homework2 (quiz1+2)

contributed by < TING0419 >

第一週

測驗一

測驗二

測驗三

用8個數字模擬 非遞迴Quicksort

該程式實作了一個基於 struct list_head 的 快速排序，並進行了鏈表構造、shuffle、排序與驗證。

---

1. 定義鏈表節點 (node_t)

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

• value：儲存數值。
• list：使用 Linux Kernel 的 list_head 來形成雙向鏈表。

---

2. 相關工具函式

(1) 獲取鏈表最後一個節點

struct list_head *list_tail(struct list_head *head)
{
    while (head && head->next)
        head = head->next;
    return head;
}

• 作用：尋找並回傳鏈表的最後一個節點。

(2) 計算鏈表長度

int list_length(struct list_head *left)
{
    int n = 0;
    struct list_head *node;
    list_for_each(node, left) n++;
    return n;
}

• 作用：遍歷鏈表並計算節點數量。

(3) 重新構建雙向鏈表

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) 初始化變數

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

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 並進行分割

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

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) 記錄排序區塊並繼續排序

begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;

(5) 處理單獨節點（回溯）

else {
    if (L) {
        L->next = result;
        result = L;
    }
    i--;
}

---

4. 其他功能

(1) 構造鏈表

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) 釋放鏈表記憶體

void list_free(const struct list_head *head)
{
    node_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        free(entry);
    }
}

(3) 驗證鏈表是否排序

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. 主程式執行流程

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）測試不同輸入情況

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. 基礎情況處理

   ​​​if (list_empty(head) || list_is_singular(head))
   ​​​    return;
   

   • 若 head 為空或只有一個元素，直接返回。

2. 初始化 list_less 和 list_greater

   ​​​INIT_LIST_HEAD(&list_less);
   ​​​INIT_LIST_HEAD(&list_greater);
   

   • 用來存放小於和大於 pivot 的節點。

3. 選擇 pivot 並將其從鏈表移除

   ​​​pivot = list_first_entry(head, struct listitem, list);
   ​​​list_del(&pivot->list);
   

   • 取出 pivot 並從鏈表刪除，以便進行分割。

4. 遍歷鏈表，將元素分配到 list_less 和 list_greater

   ​​​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

   ​​​list_quicksort(&list_less);
   ​​​list_quicksort(&list_greater);
   

   • 對 list_less 和 list_greater 分別進行 QuickSort。

6. 重新合併鏈表

   ​​​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 洗牌演算法

原始版

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）

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[] 並洗牌

   ​​​random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
   

   • 這會打亂 values[]。

2. 將 values[] 的數據插入 testlist

   ​​​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[]（作為基準）

   ​​​qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
   

   • 使用標準 qsort() 來排序陣列。

4. 對 testlist 執行 list_quicksort()

   ​​​list_quicksort(&testlist);
   

   • 對雙向鏈表進行 QuickSort。

5. 驗證排序結果

   ​​​list_for_each_entry_safe (item, is, &testlist, list) {
   ​​​    assert(item->i == values[i]);
   ​​​    list_del(&item->list);
   ​​​    free(item);
   ​​​    i++;
   ​​​}
   

   • 確保鏈表排序結果與 values[] 一致。
   • 釋放鏈表的記憶體。

---

測驗二

測驗三