Everyone who has studied Computer Science would know about the
Bubble Sort algorithm. This is a simple sorting algorithm which runs at O(n^2). You may wish to consult your standard data structure text or the above hyperlink for further information.
Since this particular blog of mine is about Erlang and also i'm quite "hooked" to it, so again this article is about illustrating this algorithm implemented using Erlang. It's a fun exercise.
I have included source codes for running 2 versions: (a) Non-graphical and (b) Graphical.
%
% This is an attempt to create a GUI version of the "Bubble Sort"
%
% procedure bubblesort(A:list of unsorted items) defined as:
% do
% swapped := false
% for each i in 0 to length(A) -2 do
% if A[i] > A[i+1] then
% swap(A[i], A[i+1])
% swapped := true
% end if
% end for
% while swapped
% end procedure
-module(bsort).
-export([start/1, init/1]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
start(N) -> spawn(bsort, init, [N]).
%
% Standard "for"-loop concept
%
for(N,N,Dict,F,Num) -> Val = F(Num), NewDict = dict:store(N,Val,Dict), NewDict;
for(I,N,Dict,F,Num) -> Val = F(Num), NewDict = dict:store(I,Val,Dict), for(I+1,N,NewDict,F,Num).
% Swaps the value but not the position of the record
%
swap({Pos1,Value1},{Pos2,Value2},Dict) ->
NewDict1 = dict:store(Pos1,Value2,Dict),
NewDict2 = dict:store(Pos2,Value1,NewDict1),
NewDict2.
%
% BubbleSort implementation
%
bsort(D,Swapped) when Swapped =:= false -> D;
bsort(D,Swapped) when Swapped =:= true ->
Len = erlang:length(dict:fetch_keys(D)),
{Again, NewDict} = checkNSwap(D,1,Len, false),
bsort(NewDict,Again).
%
% Check-N-Swap
%
checkNSwap(Dict,N,N,Again) -> {Again,Dict};
checkNSwap(Dict,I,N,Again) ->
Ele1 = dict:fetch(I,Dict),
Ele2 = dict:fetch(I+1,Dict),
if
Ele1 > Ele2 -> NewDict = swap({I,Ele1},{I+1,Ele2},Dict), checkNSwap(NewDict, I+1,N,true);
Ele1 =< Ele2 -> checkNSwap(Dict,I+1,N,Again)
end.
init(N) -> Dict = dict:new(),
NewDict = for(1,N,Dict, fun random:uniform/1, N),
dumpDict(bsort(NewDict,true)).
dumpDict(Dict) ->
Keys = lists:sort(dict:fetch_keys(Dict)),
lists:foreach(fun(X) -> io:format("{~p,~p} ...", [X,dict:fetch(X,Dict)]) end, Keys).
The next is the source code for the graphical version of the "Bubble Sort" and some screen-shots of the algorithm in action. I used an 25 x 25 "grid" composed of buttons (Will explore using the canvas when i have more time) and i tried the 100 x 100 "grid" but it didn't work out on my laptop as i had some resolution problems, but i think as an exercise a 25 x 25 was good enough for me :-)
-module(bsortgui).
-export([start/0]).
%
% BubbleSort implementation
%
bsort(D,Swapped) when Swapped =:= false -> D;
bsort(D,Swapped) when Swapped =:= true ->
{Again, NewDict} = checkNSwap(D,1,25, false),
bsort(NewDict,Again).
%
% Swaps the value but not the position of the record
%
swap({Pos1,Value1,ButId1},{Pos2,Value2,ButId2},Dict) ->
gs:config(ButId1,[{label, {text, ""}}]),
gs:config(ButId2,[{label, {text, ""}}]),
NewButId1 = dict:fetch({Value1,Pos2},Dict),
NewButId2 = dict:fetch({Value2,Pos1},Dict),
gs:config(NewButId1,[{label, {text, Value1}}]),
gs:config(NewButId2,[{label, {text, Value2}}]),
NewDict1 = dict:store(Pos1,{Value2,NewButId2},Dict),
NewDict2 = dict:store(Pos2,{Value1,NewButId1},NewDict1), NewDict2.
sleep(T) ->
receive
after T -> ok end.
%
% Check-N-Swap
%
checkNSwap(Dict,N,N,Again) -> {Again,Dict};
checkNSwap(Dict,I,N,Again) ->
{Ele1,ButId1} = dict:fetch(I,Dict),
{Ele2,ButId2} = dict:fetch(I+1,Dict),
%io:format("Col:~p,Row:~p~n", [I,Ele1]),
%io:format("Col:~p,Row:~p~n", [I+1,Ele2]),
if
Ele1 > Ele2 -> NewDict = swap({I,Ele1,ButId1},{I+1,Ele2,ButId2},Dict), sleep(300), checkNSwap(NewDict, I+1,N,true);
Ele1 =< Ele2 -> checkNSwap(Dict,I+1,N,Again)
end.
forL(N,N,{stretch,_N,_X}) -> [{stretch,_N,_X}];
forL(I,N,{stretch,_N,_X}) -> [{stretch,_N,_X}|forL(I+1,N,{stretch,_N,_X})].
%for(N,N,[H|_], D, F) -> F(H,D);
%for(I,N,[H|T], D, F) -> NewD = F(H,D), for(I+1,N,T,NewD,F).
genBut(Row,Col,Dict) when Row*Col =< 625 ->
if
Col =< 25 ->
ButId = gs:button(packer, [{label, {text, ""}}, {pack_xy, {Col,Row}}]),
NewDict = dict:store({Row,Col}, ButId, Dict), % used later for GUI manipulation
%io:format("genBut(), Row:~p, Col:~p, Id:~p~n", [Row,Col,ButId]),
genBut(Row,Col+1,NewDict);
Col > 25 -> genBut(Row+1, 1, Dict)
end;
genBut(Row,Col,Dict) when Row*Col > 625 -> Dict.
%
% Fill each column with exactly 1 random number
%
fillRand(Col,Dict) when Col =< 25 ->
Ran = random:uniform(25),
if
Col =< 25 ->
ButId = dict:fetch({Ran,Col},Dict),
gs:config(ButId, [{label, {text, Ran}}]),
NewDict = dict:store(Col, {Ran,ButId}, Dict), % used later for GUI manipulation
%io:format("Row:~p,Col:~p,Val:~p~n", [Ran,Col,Ran]),
fillRand(Col+1,NewDict)
end;
fillRand(Col,Dict) when Col > 25 -> Dict.
start() ->
D = dict:new(),
WH = [{width, 800}, {height, 800}],
Win = gs:window(gs:start(), [{map, true}, {configure, true}, {title, "BubbleSort Algorithm"} |WH]),
XOpts = forL(1,25,{stretch,1,15}),
YOpts = forL(1,25,{stretch,1,15}),
gs:frame(packer, Win, [{packer_x, XOpts}, {packer_y, YOpts}]),
NewD = genBut(1,1,D),
NewD2 = fillRand(1,NewD),
gs:config(packer,WH),
bsort(NewD2,true),
io:format("Done~n",[]),
loop().
%
% A typical loop for receiving messages
%
loop() ->
receive
{gs,_Id,destroy,_Data,_Arg} -> bye;
{gs,_Id,configure,_Data,[W,H|_]} ->
gs:config(packer, [{width,W},{height,H}]), %refresh to initial size
loop();
_Other -> loop()
end.
Below are some screenshots.
Let me know your comments if you got any :-)
