Erlang寫氣泡排序法

-module(bubble_sort).
-compile(export_all).

bubble([A,B|Rest]) when A > B ->
    [B,A|Rest];
bubble(List = [_,_|_]) ->
    List;
bubble(List) ->
    List.

sort([]) ->
    [];
sort([A|List]) ->
    List1 = sort(List),
    [B|List2] = bubble([A|List1]),
    [B|sort(List2)].

bubble/1先定義很簡單的二個數字互相比較的動作。所有的氣泡操作來自於這個基礎。

而氣泡排序法的處理,重在如何使用二數比大小。普通的程式語言,會引導我們思考從小排到大,而且數字是往陣列的末端浮上去。但是以Erlang的list來說,把前面看成末端比較好,因為讓數字小的「沉」到前端,並且在適當的時候把前端的數字拆走,是比較簡單。

所以sort/1寫成這樣,是稍微粗略了一點,把bubbling與sorting二種功能混為一談。第一次sort(List)產生的是「我們認為它排序了,但實際上可能沒有完全排序好的list」,第二次sort(List2)意義則是,「到最後List2不見得已經排序,所以要再排序一次」。

最後sort/1意思上看起來仍有點怪怪的……

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Fun。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s