ErlangでいろんなSortを書いてみる part1

2ヶ月ぶりの更新になります。

最近Haskellで様々なソートを
実装してみたというブログ記事を読みました。

自分がやったことある関数型言語って何があったかなと
思い出してみると、そういえば
「Erlang」
があったなとふと思い出しました。

それで僕もErlangでソートを実装してみるかと思い
実装してみたわけです。

バブルソート:

sort([]) -> [];
sort(List) ->
	Sorted = bubble_sort(List),
	[Min|More] = lists:reverse(Sorted),
	[Min|sort(lists:reverse(More))].
	
bubble_sort([]) -> [];
bubble_sort(List) when length(List) == 1 -> List;
bubble_sort([X,Y|More]) when X > Y -> [X|bubble_sort([Y|More])];
bubble_sort([X,Y|More]) -> [Y|bubble_sort([X|More])].

シェイカーソート:

shaker_sort([]) -> [];
shaker_sort(List) when length(List) < 2 -> List;
shaker_sort(List) ->
	Upped = shaker_sort(up, List),
	[Min|More] = lists:reverse(Upped),
	Downed = shaker_sort(down, More),
	[Max|Other] = lists:reverse(Downed),
	lists:reverse([Max|lists:reverse([Min|shaker_sort(Other)])]).

shaker_sort(up, []) -> [];
shaker_sort(up, List) when length(List) < 2 -> List;
shaker_sort(up, [X,Y|More]) when Y > X ->
	[Y|shaker_sort(up,[X|More])];
shaker_sort(up, [X|More]) ->
	[X|shaker_sort(up, More)];

shaker_sort(down, []) -> [];
shaker_sort(down, List) when length(List) < 2 -> List;
shaker_sort(down, [X,Y|More]) when Y < X ->
	[Y|shaker_sort(down, [X|More])];
shaker_sort(down, [X|More]) ->
	[X|shaker_sort(down, More)].

選択ソート:

selection_sort([]) -> [];
selection_sort(List) ->
	Min = lists:min(List),
	[Min|selection_sort(List -- [Min])].

挿入ソート:

insertion_sort([], Sorted) -> Sorted;
insertion_sort([Head|More], Sorted) ->
	insertion_sort(More, insert(Sorted, Head)).

insert([],Value) -> [Value];
insert([Head|_] = List,Value) when Head > Value -> [Value|List];
insert([Head|More], Value) -> [Head|insert(More, Value)]. 

今回はこの4つを実装しました。
実際に実装してみるとぜんぜん覚えてなくてびっくりしました。

他のソートを実装して、またブログに上げます。

では今回はこのへんで。