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 Quicksort

Description
Sort an array of numbers into numerical order using Quicksort
  • nested loops: repeat-until, forall, while
  • recursive calls of procedures
  • overloading of subroutines
The idea of the quick sort algorithm is to partition the array that is to be sorted into two parts. The `left' part containing all values smaller than the partitioning value and the `right' part all the values that are larger than this value. The partitioning is then applied to the two subarrays, and so on, until all values are sorted.

Further explanation of this example: 'Mosel User Guide', Sections 9.4 'forward' and 9.5 'Overloading of subroutines'.


Source Files





qsort.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file qsort.mos                                      *
  * ``````````````                                      *
  * Example for the use of the Mosel language           *
  * (Sort an array of numbers into numerical order)     *
  *                                                     *
  * Implements Quicksort:                               *
  * After selecting a partitioning value v the original *
  * array is partitioned into two subarrays by pairwise *
  * exchange of elements. At the end of a round of      *
  * partitioning, all elements in the left subarray are *
  * less or equal the partitioning value, all elements  *
  * in the right subarray are greater or equal v.       *
  * The process is then repeated to the left and right  *
  * subarrays independently, and so on.                 *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: Y. Colombani, 2001                      *
  *******************************************************!)

model "Quick Sort"             ! Start a new model
uses "mmsystem"

parameters
 LIM=50
end-parameters

                               ! Declare a procedure that is defined later
forward procedure qsort(L:array(range) of integer)

declarations
 T:array(1..LIM) of integer
end-declarations

                               ! Generate randomly an array of numbers
 forall(i in 1..LIM) T(i):=round(.5+random*LIM)
 writeln(T)
 stime:=gettime

 qsort(T)                       ! Sort the array

 stime:=gettime-stime
 writeln(T)                     ! Print the sorted array
 writeln(LIM," elements sorted in ",stime,"s")

!***********************************************************************
! Swap the positions of two numbers in an array
!***********************************************************************
 procedure swap(L:array(range) of integer,i,j:integer)
  k:=L(i)
  L(i):=L(j)
  L(j):=k
 end-procedure

!***********************************************************************
! Sorting routine:
!  - determine a partitioning value
!  - partition the array into two subarrays:
!    put all numbers smaller than the partitioning value into the left,
!    all numbers larger than the partitioning value into the right array
!  - recursively sort the two subarrays
!***********************************************************************
 procedure qsort(L:array(range) of integer,s,e:integer)
  v:=L((s+e) div 2)
  i:=s; j:=e
  repeat
   while(L(i)<v) i+=1
   while(L(j)>v) j-=1
   if i<j  then
    swap(L,i,j)
    i+=1; j-=1
   end-if
  until i>=j
  if j<e and s<j then qsort(L,s,j); end-if
  if i>s and i<e then qsort(L,i,e); end-if
 end-procedure

!***********************************************************************
! Start of the sorting process
!***********************************************************************
 procedure qsort(L:array(r:range) of integer)
  qsort(L,r.first,r.last)
 end-procedure

end-model

Back to examples browserPrevious exampleNext example