DataMuseum.dk

top - download

    Length: 1664 (0x680)
    Types: TextFile
    Names: »QSORT.PAS«

└─⟦74e5ee6fb⟧ Bits:30002683 PolyPascal-86 v. 3.11 - Piccoline
└─⟦74e5ee6fb⟧ Bits:30003934 SW1402 PolyPascal v3.11 (dk) til Piccoline
    └─ ⟦this⟧ »QSORT.PAS« 

TextFile

PROGRAM qsort; æ$K-,R-å

æ This program demonstrates the quicksort algorithm, which      å
æ provides an extremely effecient method of sorting arrays in   å
æ memory. The program generates a list of 1000 random numbers   å
æ between 0 and 29999, and then sorts them using the QUICKSORT  å
æ procedure. Finally, the sorted list is output on the screen.  å
æ Note that stack and range checks are turned off (through the  å
æ compiler directive above) to optimize execution speed.        å

CONST
  max = 1000;

TYPE
  list = ARRAYÆ1..maxÅ OF integer;

VAR
  data: list;
  i: integer;

æ QUICKSORT sorts elements in the array A with indices between  å
æ LO and HI (both inclusive). Note that the QUICKSORT proce-    å
æ dure provides only an "interface" to the program. The actual  å
æ processing takes place in the SORT procedure, which executes  å
æ itself recursively.                                           å

PROCEDURE quicksort(VAR a: list; lo,hi: integer);

PROCEDURE sort(l,r: integer);
VAR
  i,j,x,y: integer;
BEGIN
  i:=l; j:=r; x:=aÆ(l+r) DIV 2Å;
  REPEAT
    WHILE aÆiÅ<x DO i:=i+1;
    WHILE x<aÆjÅ DO j:=j-1;
    IF i<=j THEN
    BEGIN
      y:=aÆiÅ; aÆiÅ:=aÆjÅ; aÆjÅ:=y;
      i:=i+1; j:=j-1;
    END;
  UNTIL i>j;
  IF l<j THEN sort(l,j);
  IF i<r THEN sort(i,r);
END;

BEGIN æquicksortå;
  sort(lo,hi);
END;

BEGIN æqsortå
  write('Now generating 1000 random numbers...');
  FOR i:=1 TO max DO dataÆiÅ:=random(30000);
  writeln;
  write('Now sorting random numbers...');
  quicksort(data,1,max);
  writeln;
  FOR i:=1 TO 1000 DO write(dataÆiÅ:8);
END.