(!*******************************************************
* Mosel Example Problems *
* ====================== *
* *
* file shsort.mos *
* ``````````````` *
* Example for the use of the Mosel language *
* (Sort an array of numbers into numerical order) *
* *
* Implements Shell' method: first sort, by straight *
* insertion, small groups of numbers. Next, combine *
* several small groups and sort them (possibly repeat *
* this step). Finally, sort the whole list of numbers.*
* *
* The spacings between the numbers of groups sorted *
* on each pass through the data are called the *
* increments. A good choice is the sequence which *
* can be generated by the recurrence *
* i(1)=1, i(k+1)=3i(k)+1, k=1,2,... *
* *
* (c) 2008 Fair Isaac Corporation *
* author: S. Heipcke, 2001 *
*******************************************************!)
model ShellSort ! Start a new model
declarations
N: integer ! Size of array ANum
ANum: array(range) of real ! Unsorted array of numbers
end-declarations
N:=50
forall(i in 1..N)
ANum(i):=round(random*100)
writeln("Given list of numbers (size: ", N, "): ")
forall(i in 1..N) write(ANum(i), " ")
writeln
inc:=1 ! Determine the starting increment
repeat
inc:=3*inc+1
until (inc>N)
repeat ! Loop over the partial sorts
inc:=inc div 3
forall(i in inc+1..N) do ! Outer loop of straight insertion
v:=ANum(i)
j:=i
while (ANum(j-inc)>v) do ! Inner loop of straight insertion
ANum(j):=ANum(j-inc)
j -= inc
if j<=inc then break; end-if
end-do
ANum(j):= v
end-do
until (inc<=1)
writeln("Ordered list: ")
forall(i in 1..N) write(ANum(i), " ")
writeln
end-model
|
