Quick Sort

by Stephen R. Schmitt

Definition

Algorithm

1. Choose an element in the array to be the pivot; the rightmost element in the array is chosen in this implementation. Partition the array into two parts such that
   • one contains elements less than the pivot,
   • the other contains the pivot and elements greater than the pivot
2. Return the location of the pivot in the array
3. Repeat step 1 and 2 for each of the sub-arrays formed by the partition.

Zeno source code

Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.

• Download Page

const MAX  : int := 100
type TABLE : array[MAX] of int
var  A     : TABLE
var  N, i  : int

program

   N := 11

   randomize
   for i:=1...N do
      A[i] := randint( 0, 100 )
   end for 
   put_table( A )
   
   quicksort( A, 1, N )
   put_table( A )
   
end program


procedure quicksort( var A : TABLE, left, right: int )

    var pivot : int

    if left < right then
        pivot := partition( A, left, right )
        quicksort( A, left, pivot - 1 )
        quicksort( A, pivot,  right )
    end if  

end procedure


function partition( var A: TABLE, left, right: int ): int

    var p : int := A[right]
    var i : int := left  - 1
    var j : int := right + 1

    repeat
        repeat
            incr i
        until p <= A[i]       
        repeat
            decr j
        until p >= A[j]
        swap( A, i, j )
    until j <= i

    swap( A, i, j )
    return i

end function

procedure swap( var A: TABLE, s, t: int )

   var temp : int := A[s]
   A[s] := A[t]
   A[t] := temp

end procedure

procedure put_table( var A: TABLE )

   var i : int

   for i:=1...N do 
       put A[i]:4...
   end for
   put ""

end procedure

Sample output

  22  47  92  70  54  60  89  30  64  75  98 
  22  30  47  54  60  64  70  75  89  92  98 

AbCd Classics - free on-line books