FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Sort an array of numbers using Shell's method

Description
Sort an array of numbers into numerical order using Shell's method.
• nested loops: repeat-until, forall-do, while-do
The idea of the Shell sort algorithm is to first sort, by straight insertion, small groups of numbers. Then several small groups are combined and sorted. This step is repeated until the whole list of numbers is sorted.

Further explanation of this example: 'Mosel User Guide', Section 7.2.3 'repeat until'.

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

shsort.mos

(!*******************************************************
* 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

`