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





shsortfct.mos

(!******************************************************
   Mosel User Guide Example Problems
   ================================= 

   file shsortfct.mos 
   `````````````````` 
   Combining the 'repeat-until', 'while-do', and 
   'forall-do' loops. Function returning an array.
 
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Nov. 2005
*******************************************************!)

model "Shell sort (fct)"

 declarations
  N: integer                     ! Size of array ANum
  R: range                       ! Index range of the arrays
  ANum: array(R) of real         ! Unsorted array of numbers
  ASorted: array(R) of real      ! Sorted array of numbers
 end-declarations

 forward function shsort(ANum: array(R) of real): array(R) of real

 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
 
 ASorted:= shsort(ANum)
 
 writeln("Ordered array: ")
 forall(i in 1..N) write(ASorted(i), " ")
 writeln

!***************************************************************

 function shsort(ANum: array(R) of real): array(R) of real
  returned:=ANum                 ! Copy the array to be sorted
                                 ! (Return the sorted array)
  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:=returned(i)
      j:=i
      while (returned(j-inc)>v) do   ! Inner loop of straight insertion
        returned(j):=returned(j-inc)
        j -= inc
        if j<=inc then break; end-if
      end-do
      returned(j):= v     
    end-do  
  until (inc<=1)
 end-function
 
end-model

Back to examples browserPrevious exampleNext example