函數語言處理氣泡排序法

在碩士班期間擔任幾年的大學基礎程式設計課程的實習助教，在講台上解題，講了氣泡排序法幾乎有十次（對不同班、不同年級）。

for (i=0; i<N; i++)
        for (j=0; j<N-i-1; j++)
                if (A[j] > A[j+1]) {
                        temp = A[j];
                        A[j] = A[j+1];
                        A[j+1] = temp;
                }

二個迴圈洽好代表二層次的工作：裏層負責排列順序、外層負責控制執行次數和調整排序範圍。

用 Haskell 函數語言寫氣泡排序，是將二個層次功能做好，然後組合起來。首先是氣泡調整的部份（如下方的 bubble）， bubble 函數要將一列資料由小（左）排到大（右），而且要從右邊開始向左調整順序，將較小的數字往左邊推。這和上述的普通程式處理方向相反。

bubble :: (Ord a) => [a] -> [a]
bubble [x] = [x]
bubble (x:xs)
        | x > y = y:x:ys
        | otherwise = x:y:ys
        where (y:ys) = bubble xs

次數控制的部份（如下方的 loop）， loop 函數一方面要先將某個 f 函數套到一串數列（xs）上、取回的結果（y:ys）再將 f 函數套上去；另一方面， loop 函數控制執行次數，藉由將 f 函數再次套到上次已經套過 f 函數的結果（y:ys）時，是將第一個數字（y）取出，將 f 函數套在剩餘的數列（ys）上。每次套上 f 函數之後，就取出數列的一個數字，於是剩下的數列越來越小，直到剩下空數列（[]）。

loop :: (Ord a) => ([a] -> [a]) -> [a] -> [a]
loop f [] = []
loop f xs = y : loop f ys
        where (y:ys) = f xs

接下來，氣泡排序程式（如下方的 bubbleSort），是將 loop 函數和 bubble 函數放在一起。

bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort = loop bubble

執行情況：

GHCi, version 6.8.3: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> :load "d:/code/hsBubbleSort/bubbleSort.hs"
[1 of 1] Compiling Main             ( d:/code/hsBubbleSort/bubbleSort.hs, interpreted )
Ok, modules loaded: Main.
*Main> bubbleSort [3,2,9,7,8,5,4]
[2,3,4,5,7,8,9]
*Main> bubbleSort [5]
[5]
*Main> bubbleSort []
[]
*Main>