FICO Xpress Optimization Examples Repository: Sort an array of numbers using Shell's method

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'.

shsort.zip

[download all files]

Source Files

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

shsort.mos	[download]
shsortfct.mos	[download]

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, rev. Sep. 2022
*******************************************************!)

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: break
      end-do
      returned(j):= v     
    end-do  
  until (inc<=1)
 end-function
 
end-model