Erlang寫選擇排序法

-module(sort).
-compile(export_all).

rev_append([], List) ->
    List;
rev_append([A|Rest], List) ->
    rev_append(Rest, [A|List]).

insert_(A, [B|Rest], Acc) when A =< B ->
    rev_append(Acc, [A,B|Rest]);
insert_(A, [], Acc) ->
    rev_append(Acc, [A]);
insert_(A, [B|Rest], Acc) ->
    insert_(A, Rest, [B|Acc]).

select_max([], Acc) ->
    Acc;
select_max([A|Rest], {B,Acc}) when A > B ->
    select_max(Rest, {A,[B|Acc]});
select_max([A|Rest], {B,Acc}) ->
    select_max(Rest, {B,[A|Acc]}).

selection([], Sorted) ->
    Sorted;
selection([A|Rest], Sorted) ->
    {A1, Rest1} = select_max(Rest, {A,[]}),
    selection(Rest1, insert_(A1, Sorted, [])).

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

選擇排序法,selection/2基本跟插入排序法相當類似,只差在要從[A|Rest]中找出最大值。

select_max/2用了Tail Recursion技巧,將list分為一個最大值和剩下其他的數字。

最後稍微借用插入排序法的insert_/3函數,因為功能也能做到簡單的資料合併。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s