2024q1 Homework2 (quiz1+2)

contribute by <Hualing-Chiu>

第一週測驗題

測驗一

延伸問題:

1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
2. 使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

運作原理

list_add

此函式的目的為在鏈結串列前端加入一個新節點，node_t 是要被加入的新節點，當節點加入完成後，將 *list 指回串列的開頭。

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

list_tail

此函式目的在於找到串列尾端，這裡使用間接指標來操作，不斷向後更新，因此 AAAA 應為 (*left)->next。

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next);
    return *left;
}

list_length

此函式是在計算整個串列的長度，當判斷 *left 不為 null 時，不斷將指標向後更新，因此 BBBB 應為 (*left)->next。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next);
    }
    return n;
}

quick_sort

假設原本的鏈結串列為下:

每次都挑選最左邊的節點為 pivot，在進入 while 迴圈之前，將 begin[0] 及 end[0]分別指向串列左端節點及右端節點，進入迴圈後，L 指向 begin[0]的節點，R 指向 end[0] 的節點，p 則是會向後更新去走訪每個節點。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

當n->value > value 條件成立時，會將當前指向的節點加到 right 的開頭，反之則加到 left的開頭。待 p 走訪完整個串列後，會將串列分為 left、right、pivot三個部分，且 begin[0] 與 end[0] 分別指向 left 串列的頭跟尾，begin[1] 與 end[1] 指向 pivot，begin[2] 與 begin[2] 分別指向 right 串列的頭跟尾。

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);

當 L 與 R 從堆疊中取出相同值的情況下，代表子串列只剩下單一元素，即可加入到 result 的開頭，就可得到排序好的串列。

} else {
    if (L)
        list_add(&result, L);
    i--;
}

測驗二

延伸問題

1. 解釋上述程式碼的運作原理，提出改進方案並予以實作。
2. 將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。

Timsort 運作原理

Timsort 是結合合併排序和插入排序的特點，對排序進行優化，尤其是在已經部分排序的序列，先識別出資料中已排序的子序列( run )，透過不斷合併這些 run 來達成全資料範圍的排序。

接著對 Timsort 程式碼進行探討，以圖示為例:

原始的鏈結串列為雙向鏈結串列

在 timsort 函式中，首先先將鏈結串列斷開改成單向串列

head->prev->next = NULL;

接著是 find_run 函式，尋找串列中已經排序好的 run，使用 len 計算 run 的長度，以下用圖示說明 find_run 函式的作法：

• 串列是升序( ascending )
  • 首先將 head 指向開頭，next 指向 list 的下一個節點
  • 若 next 不為空且 cmp(priv, list, next) <= 0 成立，則指標持續向後更新，直到找到非升序的串列為止。
  • 當找到非升序的節點後，斷開它與前一個節點後回傳 result.head 與 result.next。
• 串列是降序( descending )
  • 新增一個 prev 指標實作反轉序列
  • 把需被反轉的節點給 prev
  • 若 next 不為空且 cmp(priv, list, next) <= 0 則繼續走訪，否則離開迴圈。
  • 離開迴圈後回傳 result.head 與 result.next，可以發現此段子序列已排序完成。

再來執行 merge_collapse 函式，此函式目的為確保堆疊上的 run 長度保持平衡，此判斷條件就是測驗二題目所描述的 \(A<=B+C\)

n >= 3 && run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)

此外，還多了一個判斷條件為假設尚未合併的 run 有四個以上，若 \(A<=B+C\) 或 \(B<=C+D\)，則 \(C\) 和 \(B\) 或 \(D\) 選長度小的兩者合併。

n >= 4 && run_size(tp->prev->prev->prev) <= run_size(tp->prev->prev) + run_size(tp->prev)

最後，確保堆疊內的 run 長度都達到平衡後，執行 merge_force_collapse 函式將剩餘的 run 全部合併，接著把雙向鏈結接上變為雙向串列，即完成 Timsort 排序。

執行輸出

Creating sample
==== Testing timesort ====
  Comparisons:    9490
  List is sorted

第二週測驗題

測驗一

首先需先了解 preorder 與 postorder 的定義

• preorder

測驗二

測驗三