module Sort
export Comparison, Quick, Shell, Bubble
/* by: Catalyst*/
proc Shell (var numbers : array 0 .. * of real, arraysize : int)
var j, increment : int
var temp, temp2 : real
increment := 3
loop
locate (1, 1)
put increment
if increment > 0 then
for i : 0 .. arraysize
j := i
temp := numbers (i)
loop
if (j >= increment) and (numbers (j - increment) > temp) then
numbers (j) := numbers (j - increment);
j := j - increment;
else
exit
end if
end loop
numbers (j) := temp
end for
if (increment / 2 not= 0) then
increment := increment div 2;
elsif (increment = 1) then
increment := 0
else
increment := 1
end if
else
exit
end if
end loop
end Shell
/* by: M. McMullen*/
procedure Comparison (var temp : array 1 .. * of int, dir : string)
var temp1, temp2 : int
var done : array 1 .. upper (temp) of boolean
var complete : boolean := false
for i : 1 .. upper (temp)
done (i) := false
end for
loop
%%% Check Numbers
if dir = "up" or dir = "Up" or dir = "UP" then
for i : 1 .. upper (temp) - 1
if temp (i) < temp (i + 1) then
done (i) := true
elsif temp (i) > temp (i + 1) then
done (i) := false
end if
end for
elsif dir = "down" or dir = "Down" or dir = "DOWN" then
for i : 1 .. upper (temp) - 1
if temp (i) > temp (i + 1) then
done (i) := true
elsif temp (i) < temp (i + 1) then
done (i) := false
end if
end for
end if
done (upper (temp)) := true
for i : 1 .. upper (temp)
if done (i) = true then
complete := true
elsif done (i) = false then
complete := false
exit
end if
end for
exit when complete = true
%%% End Checking
for i : 1 .. upper (temp) - 1
if dir = "up" or dir = "Up" or dir = "UP" then
if temp (i) > temp (i + 1) then
temp1 := temp (i)
temp2 := temp (i + 1)
temp (i) := temp2
temp (i + 1) := temp1
end if
elsif dir = "down" or dir = "Down" or dir = "DOWN" then
if temp (i) < temp (i + 1) then
temp1 := temp (i)
temp2 := temp (i + 1)
temp (i) := temp2
temp (i + 1) := temp1
end if
end if
end for
end loop
end Comparison
/* by Catalyst */
proc Bubble (var a : array 1 .. * of int, var b : array 1 .. * of int, n : int)
var hold : int
for i : 1 .. n
for k : 1 .. n - 1
if a (k) > a (k + 1) then
hold := a (k)
a (k) := a (k + 1)
a (k + 1) := hold
hold := b (k)
b (k) := b (k + 1)
b (k + 1) := hold
end if
end for
end for
end Bubble
/* by Rapscallion */
procedure Partition (var a : array 1 .. * of int, var b : array 1 .. * of int, lo, hi : int, var lo_split, hi_split : int)
pre lo < hi
post lo_split < hi_split
var i := lo;
var j := hi
const median := a (lo) % estimate only; any guess in a(lo..hi) would do
loop
loop
exit when a (i) >= median
i += 1
end loop
loop
exit when a (j) <= median
j -= 1
end loop
if i <= j then
assert a (i) >= median and a (j) <= median
const ai := a (i);
a (i) := a (j);
a (j) := ai
const bi := b (i)
b (i) := b (j);
b (j) := bi
i += 1;
j -= 1
end if
exit when i > j
end loop
lo_split := j;
hi_split := i
end Partition
/* by Rapscallion */
procedure Quick (var a : array 1 .. * of int, var b : array 1 .. * of int, lo, hi : int)
var lo_split, hi_split : int
if lo < hi then
Partition (a, b, lo, hi, lo_split, hi_split)
Quick (a, b, lo, lo_split)
Quick (a, b, hi_split, hi)
end if
end Quick
end Sort |
Register
Wiki
Blog
Search
Turing
Chat Room
Members
