home *** CD-ROM | disk | FTP | other *** search
/ Big Blue Disk 19 / bbd19.zip / QUICK1.PAS < prev    next >
Pascal/Delphi Source File  |  1988-01-01  |  1KB  |  63 lines
  1. PROGRAM Quick1( Input, Output );   { Quicksort program }
  2.  
  3. CONST Size = 20;
  4.  
  5. TYPE List = ARRAY[1..Size] OF INTEGER;
  6.  
  7. VAR
  8.   L: List;      { Array to be sorted }
  9.   K: INTEGER;
  10.  
  11. PROCEDURE Swap( VAR X, Y : INTEGER );
  12. VAR Temp:INTEGER;
  13. BEGIN
  14.   Temp := X;
  15.   X := Y;
  16.   Y := Temp
  17. END;     { Swap }
  18.  
  19. PROCEDURE QSort(
  20.       Left,    { Position of first element }
  21.       Right:   { Position of last element }
  22.        INTEGER
  23.       );
  24.  
  25. VAR
  26.   Up, Down, Pivot: INTEGER;
  27.  
  28. BEGIN
  29.               { Partition values }
  30.   Up := Left;
  31.   Down := Right;
  32.   Pivot := L[ (Left+Right) div 2 ];   { Set pivot value }
  33.   REPEAT
  34.     WHILE L[Up] < Pivot  DO           { Scan forward }
  35.       Up := Up+1;
  36.     WHILE Pivot < L[Down]  DO         { Scan backward }
  37.       Down := Down-1;
  38.     IF  Up <= Down  THEN              { Swap & continue scans }
  39.       BEGIN
  40.         SWAP( L[Up], L[Down] );
  41.         Up := Up+1;
  42.         Down := Down-1
  43.       END
  44.   UNTIL  Up > Down;                   { until scan pointers cross }
  45.  
  46.               { Sort each partition part }
  47.   IF Left < Down
  48.     THEN  QSort( Left, Down );  { Sort left part }
  49.   IF Up < Right
  50.     THEN  QSort( Up, Right );  { Sort right part }
  51. END;     { QSort }
  52.  
  53.  
  54. BEGIN    { Main = QuickSortDemo }
  55.   FOR K := 1 TO Size DO
  56.     L[K] := TRUNC( RANDOM*900 );
  57.   FOR K := 1 TO Size DO
  58.     WRITE( L[K]:4 );
  59.   QSort( 1, Size );
  60.   Writeln;
  61.   FOR K := 1 TO Size DO
  62.     WRITE( L[K]:4 );
  63. END.     { QuickSortDemo }