home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / users / Harry / compilers / ExamplePCATPgms / sort.pcat < prev    next >
Text File  |  2003-01-08  |  2KB  |  84 lines
  1. (* quicksort
  2. **
  3. ** This program sorts an array and prints the result using the
  4. ** quicksort algorithm.  For a lucid description of the algorithm,
  5. ** see "Algorithms," by Robert Sedgewick, (2ed., p.115).
  6. **
  7. ** The input array is read in from the input.
  8. *)
  9.  
  10. program is
  11.  
  12.   type A is array of integer;
  13.   var a: A := nil;
  14.  
  15.   procedure readArray () is
  16.     var i: integer := 0;
  17.     begin
  18.       write ("Enter 9 integers (between -9998 and +9998):");
  19.       for i := 1 to 9 do
  20.         loop
  21.           read (a[i]);
  22.           if (a[i] >= -9998) and (a[i] <= 9998) then exit; end;
  23.           write ("Input values must be between -9998 and +9998; try again...");
  24.         end;
  25.       end;
  26.       return;
  27.     end;
  28.  
  29.   procedure printArray () is
  30.     var i: integer := 0;
  31.     begin
  32.       write ("The sorted array is:");
  33.       for i := 1 to 9 do
  34.         write (a[i]);
  35.       end;
  36.       return;
  37.     end;
  38.  
  39.   procedure partition (l, r: integer) : integer is
  40.     var i, j, v, t: integer := 0;
  41.     begin
  42.       v := a[r];
  43.       i := l-1;
  44.       j := r;
  45.       loop
  46.         i := i+1;
  47.         while a[i]<v do
  48.           i := i+1;
  49.         end;
  50.         j := j-1;
  51.         while a[j]>v do
  52.           j := j-1;
  53.         end;
  54.         t := a[i];
  55.         a[i] := a[j];
  56.         a[j] := t;
  57.         if j<=i then exit; end;
  58.       end;
  59.       a[j] := a[i];
  60.       a[i] := a[r];
  61.       a[r] := t;
  62.       return i;
  63.     end;
  64.  
  65.   procedure quicksort (m, n: integer) is
  66.     var i: integer := 0;
  67.     begin
  68.       if n>m then
  69.         i := partition (m, n);
  70.         quicksort (m, i-1);
  71.         quicksort (i+1, n);
  72.       end;
  73.       return;
  74.     end;
  75.  
  76. begin
  77.   a := A [< 11 of 0 >];
  78.   a [0] := -9999;
  79.   a [10] := 9999;
  80.   readArray ();
  81.   quicksort (1,9);
  82.   printArray ();
  83. end;
  84.