Here's the codes:
Filename: "isort.erl"
-module(isort).
-export([start/1]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
%
%
% The insertion sort is a good middle-of-the-road choice for sorting lists of
% a few thousand items or less. The algorithm is significantly simpler than
% the shell sort, with only a small trade off in efficiency. At the same time
% the insertion sort is over twice as fast as the bubble sort and almost 40%
% faster than the selection sort. The insertion sort shouldn't be used for
% sorting lists larger than a couple thousands items or repetitive sorting
%of lists larger than a couple hundred items
%
% insertionSort(array A)
% for i = 1 to length[A]-1 do
% value = A[i]
% j = i-1
% while j >= 0 and A[j] > value do
% A[j + 1] = A[j]
% j = j-1
% A[j+1] = value
%
genNum(N,N,L,F,Num) -> [F(Num),L];
genNum(I,N,L,F,Num) -> Val = F(Num), genNum(I+1,N,[Val,L],F,Num).
for(N,N,F,L) -> Val = lists:nth(N,L), J = N - 1,T = lists:nth(J,L), F(J,L,Val,T);
for(I,N,F,L) -> Val = lists:nth(I,L), J = I - 1,T = lists:nth(J,L), L2 = F(J,L,Val,T), for(I+1,N,F,L2).
checkNInsert(Index,L,Value,T) when Index >= 1 andalso T > Value ->
{L1,L2} = lists:split(Index,L),
[_H|T1] = L2,
Temp1 = lists:flatten(lists:append([L1],[T])),
Temp2 = lists:append(Temp1, T1),
if
Index - 1 /= 0 ->
NewVal = lists:nth(Index - 1, Temp2),
checkNInsert(Index - 1, Temp2, Value, NewVal);
Index - 1 =:= 0 ->
checkNInsert(Index - 1, Temp2, Value, Value)
end;
checkNInsert(Index,L,Value,T) when Index =< 1 orelse T =< Value ->
{L1,L2} = lists:split(Index,L),
[_H|T1] = L2,
lists:append(lists:append(L1,[Value]),T1).
start(N) ->
L = lists:flatten(genNum(1,N,[],fun random:uniform/1, N)),
for(2, length(L), fun checkNInsert/4, L).
And next is for the graphical version
While the algorithm is executing, you will notice that the buttons will flash every time it detects a re-positioning is required. Here is a screen shot and do let me know if you have any comments, it would be much appreciated; that applies to ideas as well :-)
Filename: "isortgui.erl"
-module(isortgui).
-export([start/0]).
-copyright('Copyright (c) 2007 Raymond Tay').
-vsn('$Revision: 1').
%
% The insertion sort is a good middle-of-the-road choice for sorting lists of
% a few thousand items or less. The algorithm is significantly simpler than
% the shell sort, with only a small trade off in efficiency. At the same time
% the insertion sort is over twice as fast as the bubble sort and almost 40%
% faster than the selection sort. The insertion sort shouldn't be used for
% sorting lists larger than a couple thousands items or repetitive sorting
% of lists larger than a couple hundred items
%
% insertionSort(array A)
% for i = 1 to length[A]-1 do
% value = A[i]
% j = i-1
% while j >= 0 and A[j] > value do
% A[j + 1] = A[j]
% j = j-1
% A[j+1] = value
%
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,F,L) -> {_,Val} = gs:read(dict:fetch({1,N},L),label), J = N - 1, {_,T} = gs:read(dict:fetch({1,J},L),label), {Val1,_} = string:to_integer(Val), {T1,_} = string:to_integer(T),F(J,L,Val1,T1);
for(I,N,F,L) -> {_,Val} = gs:read(dict:fetch({1,I},L),label), J = I - 1, {_,T} = gs:read(dict:fetch({1,J},L),label), {Val1,_} = string:to_integer(Val), {T1,_} = string:to_integer(T), D2 = F(J,L,Val1,T1), for(I+1,N,F,D2).
checkNInsert(Index,L,Value,T) when Index >= 1 andalso T > Value ->
ButId = dict:fetch({1,Index+1},L),
gs:config(ButId, [{label, {text, T}}]),
gs:config(ButId, [flash]),
sleep(50),
if
Index - 1 =:= 0 -> checkNInsert(0,L,Value,Value);
Index - 1 /= 0 ->
{_,Val} = gs:read(dict:fetch({1,Index -1},L),label),
{Val1,_} = string:to_integer(Val),
if
Val1 =< Value -> checkNInsert(Index - 1, L, Value, Value);
Val1 > Value -> checkNInsert(Index - 1, L, Value, Val1)
end
end;
checkNInsert(Index,L,Value,T) when Index =:= 0 orelse T =< Value ->
ButId = dict:fetch({1,Index+1},L),
gs:config(ButId, [{label, {text, Value}}]),
gs:config(ButId, [flash]),
L.
isort(Dict) ->
for(2, 50, fun checkNInsert/4, Dict). % Sort it for 2-to-<number of columns in GUI>
start() ->
D = dict:new(),
WH = [{width, 1000}, {height, 50}],
Win = gs:window(gs:start(), [{map, true}, {configure, true}, {title, "Insertion-Sort Algorithm"} |WH]),
XOpts = forL(1,50,{stretch,1,20}),
YOpts = [{stretch,1,20}],
gs:frame(packer, Win, [{packer_x, XOpts}, {packer_y, YOpts}]),
NewD = genBut(1,1,D),
gs:config(packer,WH),
dumpDict(NewD),
isort(NewD),
dumpDict(NewD),
io:format("algo done~n",[]),
loop().
%
%
% Generate the "button" GUI objects
%
genBut(Row,Col,Dict) when Col =< 50 ->
ButId = gs:button(packer, [{label, {text, random:uniform(50)}}, {pack_xy, {Col,Row}}]),
NewDict = dict:store({Row,Col}, ButId, Dict), % used later for GUI manipulation
genBut(Row,Col+1,NewDict);
genBut(Row,Col,Dict) when Col > 50 -> Dict.
%
% Pretty standard GUI-event loop
%
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.
%
% Pretty standard "sleep" function
%
sleep(T) ->
receive
after T -> ok
end.
%
% Dump the dictionary
%
dumpDict(D) ->
Keys = lists:sort(dict:fetch_keys(D)),
lists:foreach( fun({R,C}) -> Val = gs:read(dict:fetch({R,C},D),label), io:format("{~p,~p}->~p~n", [R,C,Val]) end, Keys).
