home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / turbo55 / install / demos.arc / QSORT.PAS < prev    next >
Pascal/Delphi Source File  |  1989-05-02  |  2KB  |  67 lines
  1.  
  2. { Turbo Sort }
  3. { Copyright (c) 1985, 1989 by Borland International, Inc. }
  4.  
  5. program qsort;
  6. {$R-,S-}
  7. uses Crt;
  8.  
  9. { This program demonstrates the quicksort algorithm, which      }
  10. { provides an extremely efficient method of sorting arrays in   }
  11. { memory. The program generates a list of 1000 random numbers   }
  12. { between 0 and 29999, and then sorts them using the QUICKSORT  }
  13. { procedure. Finally, the sorted list is output on the screen.  }
  14. { Note that stack and range checks are turned off (through the  }
  15. { compiler directive above) to optimize execution speed.        }
  16.  
  17. const
  18.   max = 1000;
  19.  
  20. type
  21.   list = array[1..max] of integer;
  22.  
  23. var
  24.   data: list;
  25.   i: integer;
  26.  
  27. { QUICKSORT sorts elements in the array A with indices between  }
  28. { LO and HI (both inclusive). Note that the QUICKSORT proce-    }
  29. { dure provides only an "interface" to the program. The actual  }
  30. { processing takes place in the SORT procedure, which executes  }
  31. { itself recursively.                                           }
  32.  
  33. procedure quicksort(var a: list; Lo,Hi: integer);
  34.  
  35. procedure sort(l,r: integer);
  36. var
  37.   i,j,x,y: integer;
  38. begin
  39.   i:=l; j:=r; x:=a[(l+r) DIV 2];
  40.   repeat
  41.     while a[i]<x do i:=i+1;
  42.     while x<a[j] do j:=j-1;
  43.     if i<=j then
  44.     begin
  45.       y:=a[i]; a[i]:=a[j]; a[j]:=y;
  46.       i:=i+1; j:=j-1;
  47.     end;
  48.   until i>j;
  49.   if l<j then sort(l,j);
  50.   if i<r then sort(i,r);
  51. end;
  52.  
  53. begin {quicksort};
  54.   sort(Lo,Hi);
  55. end;
  56.  
  57. begin {qsort}
  58.   Write('Now generating 1000 random numbers...');
  59.   Randomize;
  60.   for i:=1 to max do data[i]:=Random(30000);
  61.   Writeln;
  62.   Write('Now sorting random numbers...');
  63.   quicksort(data,1,max);
  64.   Writeln;
  65.   for i:=1 to 1000 do Write(data[i]:8);
  66. end.
  67.