再寫Erlang氣泡排序法

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

swap(A,B) when A > B ->
    {B,A};
swap(A,B) ->
    {A,B}.

bubble({nil,A}) ->
    {nil,A};
bubble({A,B}) ->
    {A1,A2} = bubble(A),
    {A3,A4} = swap(A2,B),
    {{A1,A3},A4};
bubble({A}) ->
    {nil,A}.

tail_list([], Acc) ->
    Acc;
tail_list([A|Rest], Acc) ->
    tail_list(Rest, {Acc,A}).

tail_list(List) ->
    tail_list(List, nil).

sort(nil, Acc) ->
    Acc;
sort(Tail_list, Acc) ->
    {A,B} = bubble(Tail_list),
    sort(A,[B|Acc]).

sort(List) when is_list(List) ->
    sort(tail_list(List));
sort(Tail_list) ->
    sort(Tail_list, []).

這次用比較普通的陣列思考方式處理氣泡排序法。

為了將大的數字浮到末端並且容易拆解,要使用一種反過來的list,稱為tail list。

開始排序一串list時,先轉換為tail list,然後bubble/1針對tail list處理數字順序。

sort/1和tail_list/1都做了Tail Recursion加強。但是我還沒想出要怎麼將bubble/1轉為Tail Recursion。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s