FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

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





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

Back to examples browserPrevious exampleNext example