Erlang程式設計與問題解決/排序

維基教科書,自由的教學讀本


快速排序[編輯]

快速排序是一般接受度較大的排序法。對 Erlang 語言玩家而言,幾乎是入門級的排序法,隨手可得。

快速排序 ( quick sort ) 是一個遞迴過程。對任一列表,隨意取其中一項當做比對項,將列表分為二部份,其中一部份包含列表全部小於比對項的元素,另一部份包含列表全部大於比對項的元素。然後,要對新分出來的二個部份分別做快速排序,將排序好的結果,資料較小的部份放在一邊,資料較大的部份放在另一邊。

quicksort([]) -> [];
quicksort([X|Xs]) ->
    quicksort([Y || Y<-Xs, Y=<X]) ++ [X] ++ quicksort([Z || Z<-Xs, Z>X]).

這樣,程式構成很簡單。雖然程式很簡單,但是效能消耗的因素是在列表串接運算子 ++ ,它的計算方式與以下函數相同:

append([], Ys) -> Ys;
append([X|Xs], Ys) -> [X | append(Xs, Ys)].

強化快速排序[編輯]

函數語言有一個常見的優化法則,稱為尾端遞迴,意思是在函數主體程式中,只在最後做遞迴。尾端遞迴可以減低運作時的系統負擔。有一項與尾端遞迴搭配的技巧,叫做累積變數,是將一個變數傳入函數中,將一些部份計算結果累積到變數中,然後將變數傳遞到遞迴呼叫裏。以下用尾端遞迴和累積變數,將上述 ++ 做一個強化的版本。

append(Xs, Ys) -> append(Xs, [], Ys).

append([], Accumulator, Ys) ->
    lists:reverse(Accumulator) ++ Ys;
append([X|Xs], Accumulator, Ys) ->
    append(Xs, [X|Accumulator], Ys).

隨著遞迴將 [X|Xs] 的元素一個一個反序累積給 Accumulator 。最後,使用 lists:reverse/1Accumulator 反轉順序。總共計算量平均比 ++ 較少。

有了這個優化的 ++/append , quicksort/1 改寫成:

quicksort([]) -> [];
quicksort([X|Xs]) ->
    append(
        quicksort([Y || Y<-Xs, Y=<X]),
        [X | quicksort([Z || Z<-Xs, Z>X]) ]
    ).

氣泡排序[編輯]

氣泡排序 ( bubblesort ) 是程序式語言的入門課程,其中步驟充滿程序性。對一列不知是否排序的數字,用一個二者比大小的函數來逐項比較、逐項影響數列的排列情況。首先,對這列數字由左向右依序兩兩比較大小,如果左方數字比較大,就讓二個數字互換位置。每做完一次這個步驟,數列中有些數字會左移,有些數字會右移,並且可確定最大的數字會靠到最右邊。這樣的步驟稱為掃瞄。而且,按照數列的數目 N ,重覆進行掃瞄步驟 N-1 次,前 N-1 項較大的數字會依序靠右,並且每個都不會比更大的數字靠得更右邊。於是數列排列完成。

以上所述的一次掃瞄, Erlang 可以寫成:

compare([X,Y|Ys]) when X > Y ->
    [Y|compare([X|Ys])];
compare([X,Y|Ys]) ->
    [X|compare([Y|Ys])];
compare(Xs) ->
    Xs.

那麼,氣泡排序就是

bubblesort(Xs) ->
    compare(length(Xs)-1, Xs).

compare(N, Xs) when N > 0 ->
    Rs = compare(Xs),
    compare(N-1, Xs);
compare(_, Xs) ->
    Xs.

bubblesort/1 是主程式, compare/2 決定要掃瞄幾次, compare/1 進行一次掃瞄並拋回結果。

compare/1 在此決定了氣泡排序的主要運作邏輯,而且,也可以藉由改寫這個函數,使排序變成選擇排序

選擇排序[編輯]

選擇排序是,在一列不知是否排序的數字中,找到最小的一個,就把它放到最左邊。對 N 個數字做這個動作 N-1 次,就可以保證數字排列完成。在此,一次找到一個最小的數字並放在左邊的函數,寫成

select([X|Xs]) ->
    case select(Xs) of
        [] ->
            [X];
        [Y|Ys] ->
            if
                X > Y ->
                    [Y,X|Ys];
                true ->
                    [X,Y|Ys]
            end
    end;
select([]) ->
    [].

與以上氣泡排序的程序互相比較,主程式和掃瞄次數的格式一模一樣。選擇排序的 compare/2 ,只要將 bubblesort/1 的 compare/2 改一個呼叫的對象

compare(N, Xs) when N > 0 ->
    Rs = select(Xs),
    compare(N-1, Xs);
compare(_, Xs) ->
    Xs.

同一組程式立刻化身為選擇排序了。

插入排序[編輯]

插入排序 ( insertion sort ) 是 Cormens 等人所著《演算法概論》 ( Introduction to Algorithms ) 書的第一個例子。排序就好像從一列不知是否排序的數字中,隨便挑選每一個數字,將數字仔細放到目的地的正確順序位置。

一個插入數字的動作,是這樣的函數

insert(X, []) ->
    [X];
insert(X, [Y|Ys]) when X > Y ->
    [ Y | insert(X, Ys) ];
insert(X, [Y|Ys]) ->
    [X,Y|Ys].

插入排序的主程式是

insertionsort(Xs) ->
    insert_pile(Xs, []).

insert_pile/2 的二個參數,第一個是原數列,第二個是已排序數列。 insert_pile/2 定義為

insert_pile([], Ys) ->
    Ys;
insert_pile([X|Xs], Ys) ->
    Rs = insert(X, Ys),
    insert_pile(Xs, Rs).

其他排序[編輯]

還有幾種排序,需要更多程式工法。 Erlang 提供開源電信平台 ( Open Telecom Platform , OTP ) 程式庫,使多數經常使用的程式功能、或是較複雜的演算過程,都可以引用此程式庫而加強程式開發效率。因此,像基數排序法 ( radix sort ) 這種較複雜的處理,挪至 Erlang/OTP 介紹之後才討論。 Shell 排序法是依氣泡排序法和插入排序法而設計的加強方法,將來在效率的比較是有趣的討論。另外,也將合併排序 ( merge sort ) 與矩型排序列在後段介紹。