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.

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