2024q1 Homework2 (quiz1+2)

contributed by < Randy-Chuang >

2024q1 第 1 週測驗題

測驗 1

先參考 Optimized QuickSort — C Implementation (Non-Recursive) ，以下我把程式碼片段貼入解釋理解過程：

    i = 0; beg[0]=0; end[0]=elements;
    while (i>=0) {
        L=beg[i]; R=end[i]-1;
        if (L<R) {
            // 取區段 (partition) 第一個 element 做 pivot 來比較
            piv=arr[L]; if (i==MAX_LEVELS-1) return NO;
            while (L<R) {
                /// 從區段頭尾比較，根據 pivot 將區段分為小大兩邊
                while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; 
                while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; 
            }
            // 將區端分為小大兩個子區段
            arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; 
        } else {
            i--; // L < R 代表區段排序尚未結束，持續減少讓迴圈運作到結束
        }
    }

範例顯示外層迴圈第一輪結束後的結果：

外層迴圈跑完第一輪陣列 beg[] 和 end[] 內數值的變化：

陣列 \ index	0	1	2	…
beg[]	0 $\to$ 0	0 $\to$ 4	0	0
end[]	8 $\to$ 3	0 $\to$ 8	0	0

配上範例能發現排序過程中 pivot 變數被用來將大小區段分開後，再改變 beg[] 和 end[] 來紀錄目前 Quick Sort 待排序的區段，以每次迴圈迭代而更改的陣列內容當作分枝來看，就能看出 Quick Sort 遞迴樹的變化，行為與 Iterative DFS 中佇列的控制相同。每跑一次迴圈，當次選用的 pivot 就會被擺到左區塊最後，因此左邊區段最後的元素剛好不用再排序 (圖中紅色標示) 。

但是待排序陣列若是排列特殊會讓遞迴樹產生傾斜，極端情況會讓分配不均的小區段一直保留在 beg[] 和 end[] 陣列前端，造成長度不足以紀錄遞迴樹的分枝，因此作者改善程式碼確保迭代過程中優先處理較小的區段，遞迴樹的高度不會超過

$\lceil Lo{g}_2(n)\rceil$ 。

            arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L; 
+           if (end[i]-beg[i] > end[i-1]-beg[i-1]) {
+               swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap;
+               swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; 
+           }
        } else {
            i--; 
        }

測驗程式碼

(*left)->next
(*left)->next
p->next
list_tail(&left)
list_tail(&right)

延伸問題：

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

測驗 2

延伸問題：

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

2024q1 第 2 週測驗題

測驗 1

測驗 2

測驗 3

表單測驗

參考資料

• Graphviz
  • Graphviz Doc / Layout Engines / Gallery / Drawing graphs with dot
  • Multiple graphs inside Graphviz DOT file