Erlang寫氣泡排序法之效率加強版

-module(bubble_sort).
-export([sort/1]).

swap([A,B|Rest]) when A < B ->
    [B,A|Rest];
swap(List) ->
    List.

bubble([], Acc) ->
    Acc;
bubble([A|Rest], Acc) ->
    bubble(Rest, swap([A|Acc])).

bubble(List) ->
    bubble(List, []).

sort([], Acc) ->
    Acc;
sort(List, Acc) ->
    [A|Rest] = bubble(List),
    sort(Rest, [A|Acc]).

sort(List) ->
    sort(List, []).

最後整理成如此成品。

bubble/2藉由Tail Recursion將數字一個接著一個丟到累積變數中,而恰好可以用swap/1把累積變數這個partial list做局部排序。結果,可以保證最大的數字放在前頭。

然後sort/2做的是先bubble,然後把頭一個數字摘出放到累積變數,之後再sort。因為sort/2使用了Tail Recursion技巧,對處理的list附帶有反轉list的效果,最後會產生由小排到大的list。

這個完成版本,可以說是徹底對應了演算法所教導的使用C/C++、Java等等來實作的的氣泡排序法了。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s