深入 qsort(3)

如果你有學過演算法或資料結構，相信對 quicksort 一定不會陌生，或許細節忘了，但是至少應該有聽過。實作 quicksort 讓我們學習到重要的「divide and conquer」設計典範 (design paradigm)，並且對於操作邊界值有更精確的體體認。我每隔一段時間都會重新實作幾個典型的排序演算法，例如 quicksort、insertion sort、bubble sort、heapsort、merge sort 等等。藉此磨練自己的 coding 技巧，靈活一下自己的腦袋。

實作 quicksort 時，不免讓人想到 standard C library 中的 qsort(3)。從 qsort 這個字眼上，很直覺地想到他可能是由 quicksort 這個名稱來的，甚至直覺地推斷 qsort 就是 quicksort 的實作。實際上只答對了一半，qsort 遠比我原本想像的還要複雜。參考 GNU libc 2.4 中 qsort 的實作部分，在記憶體方面，運用了不少跟硬體平台相關的特性，以加速記憶體的處理。撇開平台相依部分不談，單就演算法設計方面來看也有很多巧妙之處。

void qsort(void *base, size_t nmemb, size_t size, 
           int(*compar)(const void *, const void *));

首先，qsort 會先判斷欲排列元素個數 size 是否小於 1024，若小於 1024 則呼叫 msort_with_tmp 來處理。msort_with_tmp 實作 merge sort 演算法，最後一個參數是一個 size 大小的 buffer，作為 merge sort 所需的 O(n) 空間之用，可以避免過於頻繁的記憶體配置。若是 size 大於 1024，則會根據目前系統的記憶體狀況，決定該使用什麼演算法。在最壞情況下，merge sort 演算法的時間複雜度是 O(n log n)，好過 quicksort 的 O(n²)。由於 merge sort 需要額外的 O(n) 空間，所以在記憶體空間允許的條件之下，會優先使用 merge sort，否則便呼叫 _quicksort。

_quicksort 實作一個真正的 quicksort 演算法，並採用以下幾點優化的設計：

1. Non-recursive (非遞迴) - 使用 stack 資料結構取代遞迴呼叫所需要的 function stack，增進程式執行效率。實際上這個 stack 不用太大，在 32-bit 環境下，最多只需要 32 個元素空間 (在 64-bit 環境下，則為 64 個)。為什麼是 32？因為在 32-bit 環境下 size_t 為 32-bit，log 2³² 為 32。
   
2. 以 median-of-three 方法決定 pivot - 一般 quicksort 演算法通常取開頭元素當作 pivot，但這往往不是一個理想的值，尤其對於已排序的陣列來說，會造成最壞的結果。以陣列開頭、最後與中間位置三值的中位數當作 pivot，比較有機會取到較理想的值。
3. 混合 insertion sort 增加效率 - 對於元素個數少於某個 threshold 的 partition，使用 insertion sort 能夠大大地增加執行效率。對於小陣列而言，insertion sort 會比 quicksort 來的有效率許多。在 GNU libc 2.4 實作中，此 threshold 值設定為 4 (MAX_THRESH)，個人感覺太小了點。有些實作將它設定為 8，如 Visual C++。
   
4. 較小的 partition 優先處理 - 換言之，較大的 partition 先放入 stack 中，此舉保證 log(size) 不會超過 stack 大小。

多讀經典程式碼，實在獲益良多啊！