[UCR]
[/\]

Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
[<=] [home] [<>] [\/] [=>]

QuickSort()

procedure QSORT(m,n)
//sort records Rm, ...,Rn into nondecreasing order on key K. Key
Km is arbitrarily chosen as the control key. Pointers i and j are
used to partition the subfile so that at any time KlK, l < i
and KlK, l > j. It is assumed that KmKn+1//
  if m < n
     then [im; jn + 1; KKm
           loop
             repeat ii + 1 until KiK;
             repeat jj - 1 until KjK;
             if i < j
                 then call INTERCHANGE (R(i),R(j))
                 else exit
            forever
            call INTERCHANGE (R(m),R(j))
            call QSORT (m, j - 1)
            call QSORT (j + 1, n)]
end QSORT
Horowitz, E.; Sahni, S.
"Fundamentals of Data Structures"; Computer Science Press; 1982.

 

 function partition ( i, j: integer; pivot: keytype ): integer;
 { partitions A[i], . . . ,A[j] so keys < pivot are at the left
   and keys  pivot are on the right.
   Returns the beginning of the group on the right. }
   var
     l, r: integer; { cursors as described above }

     begin
(1)          l := i;
(2)          r := j;
         repeat
(3)             swap(A[l], A[r]);
   
            { now the scan phase begins }
(4)             while A[l].key < pivot do
(5)                l := l + 1;
(6)             while A[r].key > = pivot do
(7)                r := r - 1
             until
(8)             l > r;
(9)          return (l)
     end; { partition } 

Fig. 8.13. The procedure partition.




     procedure quicksort ( i, j: integer );
      { sort elements A[i], . . . ,A[j] of external array A }
      var
         pivot: keytype; { the pivot value }
         pivotindex: integer; { the index of an element of A where
            key is the pivot }
         k: integer; { beginning index for group of elements  pivot }
      begin
(1)      pivotindex := findpivot(i, j);

(2)      if pivotindex <> 0 then begin { do nothing if all keys are equal }
(3)               pivot := A[pivotindex].key;

(4)               k := partition(i, j, pivot);
(5)               quicksort(i, k - 1);
(6)               quicksort(k, j);
         end
      end; { quicksort }

Fig. 8.14. The procedure quicksort.

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.
"Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.