Matlab 教材：遞迴範例--Quick Sort

遞迴技術的典型範例之一，是 Hoare 在 1962 年提出的所謂 Quick Sort 演算法。 他的基本想法如下。

如果 v 是一個序列，我們要將 v 內的元素從小到大依序排好。 可以這樣想：從 v 內任挑一個元素，稱它為「標竿」 (pole)， 將 v 中所有小於標竿的元素全部挪到它的左邊， 所有不小於 (>=) 標竿的元素都挪到它的右邊。 這樣挪移之後，標竿左邊的元素都比它小、標竿右邊的元素都不比它小。 那麼，如果分別把左邊和右邊的元素都排好順序，整個 v 就完成排序了。 而左邊的元素、右邊的元素，不又是兩個序列嗎？ 何不再用同樣的想法去對付他們。 這就是遞迴想法了。

如果寫了一個函式 qsort() 來實現 Quick Sort 演算法， 就是把 v 分成小於 pole 的序列 u 和不小於 pole 的序列 w， 然後

[qsort(u), pole, qsort(w)]
就是完成排序的答案。

使用遞迴，就像 while 迴圈一樣，得要想一個問題：它如何停止？ 總不能無止境地遞迴下去，那可得不到答案。 以上述的 qsort() 想法為例，顯然 u 和 w 的元素個數至少比 v 少一個 (少了 pole)。因此，每遞迴一層，當作參數的序列元素就少一個 (以上)。 總有一天那序列的元素個數會是一個或零個 (空序列)。 在這個情況下，根本不必排序，只要把傳過來的序列 (只有一個元素、或沒有元素) 再傳回去就好了。這就是 qsort() 的停止方式。

以下就是用 Matlab 來實現 qsort() 的一種寫法。 

function sorted = qsort(v)
n = length(v);                  % n 是 v 的元素個數
if (n > 1)
    u = [];                     % 如果 n > 1 則將 v 分成 u 和 w 兩段
    w = [];                     % 將 u 和 w 準備好，一開始它們是空序列
    pole = v(1);                % pole 即標竿，我們選 v(1) 擔任標竿
    for k = 2:n                 % 把 v 的其他元素一一和標竿比小
        if (v(k) < pole)
            u = [u, v(k)];      % 比標竿小的元素放到 u 序列裡面
	else
	    w = [w, v(k)];      % 其他元素放到 w 序列裡面
	end
    end
    sorted = [qsort(u), pole, qsort(w)];    
else
    sorted = v;    
end                             % 函式結束，把 sorted 序列傳回上層呼叫者

如果

x = [2 0 7 4 9 5];
則
qsort(x)
的排序結果 (當然和 sort(x) 一樣)，是 [0 2 4 5 7 9]。 讓我們來看看 Matlab 實際上依照 qsort() 程式做了什麼？

當 Matlab 呼叫 qsort(x)，開始了第一層的 qsort()， 它得到

v = [2 0 7 4 9 5]
此時 pole 是 2 而
u = [0] 和 w = [7 4 9 5]
第一層呼叫 qsort(u)，這就開始了第二層的第一次。

第二層第一次的 qsort() 函式得到

v = [0]
因為只有一個元素，所以傳回 sorted=[0] 給第一層。 第二層第一次結束，回到第一層。

第一層得到 qsort(u) 的答案 [0]， 接著呼叫 qsort(w)，這就開始了第二層的第二次。

第二層第二次的 qsort() 函式得到

v = [7 4 9 5]
此時 pole 是 7 而
u = [4 5] 和 w = [9]
第二層第二次呼叫 qsort(u)，這就開始了第三層的第一次。

第三層第一次的 qsort() 函式得到

v = [4 5]
此時 pole 是 4 而
u = [] 和 w = [5]
第三層第一次呼叫 qsort(u)，這就開始了第四層的第一次。

第四層第一次的 qsort() 函式得到

v = []
是一個空序列，所以傳回 sorted=[] 給呼叫它的第三層第一次。 第四層第一次結束，回到第三層第一次。

第三層第一次的 qsort(u) 得到答案 []， 接著它呼叫 qsort(w)，這就開始了第四層的第二次。

第四層第二次的 qsort() 函式得到

v = [5]
只有一個元素，所以傳回 sorted=[5] 給呼叫它的第三層第一次。 第四層第二次結束，回到第三層第一次。

第三層第一次的 qsort(w) 得到答案 [5]， 因此它的 sorted=[[],4,[5]]=[4,5] 做出答案了， 傳回給呼叫它的第二層第二次。 第三層第一次結束，回到第二層第二次。

第二層第二次的 qsort(u) 得到答案 [4,5]， 接著它呼叫 qsort(w)，這就開始了第三層的第二次。

第三層第二次的 qsort() 函式得到

v = [9]
只有一個元素，所以傳回 sorted=[9] 給呼叫它的第二層第二次。 第三層第二次結束，回到第二層第二次。

第二層第二次的 qsort(w) 得到答案 [9]， 因此它的 sorted=[[4,5],7,[9]]=[4,5,7,9] 做出答案了， 傳回給呼叫它的第一層。 第二層第二次結束，回到第一層。

第一層 qsort(w) 得到答案 [4,5,7,9]， 因此它的 sorted=[[0],2,[4,5,7,9]]=[0,2,4,5,7,9] 做出答案了， 傳回給呼叫它的 Matlab 介面。 至此，整個 qsort(x) 結束，得到答案 [0 2 4 5 7 9]。

前面的敘述有點亂，讀者不妨試著按照文字敘述畫一張樹狀圖表出來， 比較容易看清楚整個流程。

習題

  1. 理論上，如果 x 有 2n 個元素 (n 是正整數)， 請問 qsort(x) 最多會呼叫幾層的 qsort() 函式？ 什麼情況下發生最多的層數？
  2. 理論上，如果 x 有 2n 個元素 (n 是正整數)， 請問 qsort(x) 最少會呼叫幾層的 qsort() 函式？ 什麼情況下發生最少的層數？
  3. 理論上，如果 x 有 2n 個元素 (n 是正整數)， 請問執行 qsort(x) 的整個過程當中， 最多會執行 v(k)<pole 這個計算多少次？
  4. 理論上，如果 x 有 2n 個元素 (n 是正整數)， 請問執行 qsort(x) 的整個過程當中， 最少會執行 v(k)<pole 這個計算多少次？
[BCC16-B]
單維彰 (2004/05/06) ---
[Prev] [Next] [Up]