HackMD2024q1 Homework2 (quiz1+2)
contributed by < Jackiempty >
第一週測驗題
測驗一
測驗一在於參考 Optimized QuickSort — C Implementation (Non-Recursive) 去實作連結佇列的 Quick sort，裡面用了begin[]和end[]去取代原本使用遞迴的方式，具體實作方式如下：
實作方式
每一輪排序是利用 L 及 R 分別指向被排序之鍵結串列的第一個節點與最後一個節點，每次挑選最左邊之節點為 pivot ，利用節點 p, n 走訪整個串列。
p 會存取下一個要走訪的節點，避免因為 n 的移除而無法完成串列的走訪。
過程當中將若 n->value > pivot->value 則將節點 n 加入 right 串列，反之則加入 left 串列。
接下來將當前 begin[i], end[i] 分別設為 left 串列的頭與尾， begin[i+1], end[i+1] 則是直接放入 pivot 節點， begin[i+2], end[i+2] 則是將 right 串列的頭與尾放入。 下一次 iteration 就會對目前的 right 串列進行排序。 right 串列全部排列完成才會對 left 串列進行排序。過程如下圖。
假設原本的鍵結串列如下
隨著 p 逐漸往右邊行進，將大於 pivot->value 的節點放入 right ，將其餘節點放入 left 。
接著left 頭尾被放入了 beg[i], end[i] 中取代了原本的整個佇列， right 頭尾被放入 beg[i+2], end[i+2] 在 i += 2 後會嘗試進行排序，而此時 beg[i] == end[i] 會成立，代表此串列只有一個節點，此時就將該節點加入 result 。接著 i-- 後會將上圖 pivot 節點加入 result ，接著對上圖 left 串列進行排序直到整個串列排序完成。
對應到程式碼
begin[i] = left; end[i] = list_tail(&left); begin[i + 1] = pivot; end[i + 1] = pivot; begin[i + 2] = right; end[i + 2] = list_tail(&right);
當
beg[i], end[i]和beg[i+2], end[i+2], ......都排序完之後，就會開始加入result} else { if (L) list_add(&result, L); i--; }
可改進之處
- 將原本單向的連結佇列改成雙向的，能快速存取 tail 後大幅提升佇列的泛用性(可實作 stack, queue)
- 加入可隨佇列大小調整
max_level的機制，避免記憶體浪費
如果要改成雙向佇列，可參考 list API 的實作方式
typedef struct __node {
- struct __node *left, *right;
- struct __node *next;
long value;
+ struct list_head list;
}
至於max_level的定義方式，我參考了 vax-r 的方式，將其定義為 \(10 \cdot \log _{10} n\) 其中 \(n = list\_length(list)\)
+ int count_level (int n) {
+ int i = 0;
+ while (n /= 10)
+ i++;
+ return i ? (i+1) * 10 : 10;
+ }
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
- int max_level = 2 * n;
+ int max_level = count_level(n);
list API 實作
在將資料結構改成雙向佇列之後，就可以無痛使用 list API 將 Optimized QuickSort — C Implementation (Non-Recursive) 的 quick sort 裡面的動作都替換掉了，以下是我用 list API 實作第一週測驗裡面的 quick sort 的程式碼：
void quick_sort(struct list_head *head, int len)
{
#define max_level 300
int i = 0;
// int max_level = count_level(n);
struct list_head *begin[max_level], *end[max_level];
struct list_head res, l, r;
struct list_head *result = &res, *left = &l, *right = &r;
INIT_LIST_HEAD(result);
INIT_LIST_HEAD(left);
INIT_LIST_HEAD(right);
begin[0] = head->next;
end[0] = head->prev;
while (i >= 0) {
struct list_head temp;
struct list_head *t = &temp;
INIT_LIST_HEAD(t);
if (begin[i] && end[i]) {
t->next = begin[i];
t->prev = end[i];
begin[i]->prev = t;
end[i]->next = t;
}
struct list_head *L = begin[i], *R = end[i];
if (L != R) {
struct list_head *pivot = L;
struct list_head *p = pivot->next;
list_del_init(pivot);
while (p != t) {
struct list_head *n = p;
p = p->next;
list_add(n,
strcmp(list_entry(n, element_t, list)->value,
list_entry(pivot, element_t, list)->value) > 0
? right
: left);
}
begin[i] = list_empty(left) ? NULL : left->next;
end[i] = list_empty(left) ? NULL : left->prev;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = list_empty(right) ? NULL : right->next;
end[i + 2] = list_empty(right) ? NULL : right->prev;
INIT_LIST_HEAD(left);
INIT_LIST_HEAD(right);
i += 2;
} else {
if (!list_empty(t))
list_add(t->next, result);
i--;
}
}
head->next = result->next;
head->prev = result->prev;
result->next->prev = head;
result->prev->next = head;
return;
}
如果眼尖一點的同學就可以發現我是原封不動地複製了測驗題的寫法，過程中遇到了一些問題
-
資料結構不一樣：
這其實是要改進的一個重點，但由於使用雙向佇列時有一個特點，那就是會有一個獨立的head，而要讓這個head適配於測驗中的操作方式有一點點麻煩，在改進的過程中會一直遇到 illegal 的指標操作，所以花了很多時間在 debug -
list API 的操作組合：
這是作業要求的一部分，就是要使用 list API 去實作 quick sort 的函式，而我選擇的方式是直接將這個環節結合HW1的Lab0-C，這樣不僅可以直接在Lab0-C的框架之下測試功能，也有完善的使用介面可以操作，最重要的是還有現成的測試情境可以使用，所以我便在Lab0-C的專案底下開了一個分支並將queue.c裡面的q_sort從原本的 merge sort 改成 quick sort那我遇到的問題是我覺得我目前的寫法還不是 optimized 的寫法，雖然裡面已經有 大量使用 list API 去完成許多動作，但還是有些零散的動作是可以合併成一個 list API 去實作的，所以這會是將來要繼續改進的目標
效能分析
測驗二
嘗試解析 Timsort 的運作原理與重點
Timsort 說明
Timsort 是一種混合了 Insertion sort 和 Merge sort 的排序演算法，能夠同時擁有 Insertion sort 的 best case time 以及 Merge sort 的 worse case time，並且改善了記憶體的管理以及合併的方式，進一步改善了原本存在於 Merge sort 中的這兩個問題
程式碼原理
