DataMuseum.dk

top - download

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

└─⟦8e533ec5a⟧ Bits:30004189 COMPAS Pascal v3.02 til CR7
    └─ ⟦this⟧ »QSORT.PAS« 

TextFile

PROGRAM QSORT; (*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
  INDEX = 1..MAX;
  ITEM = INTEGER;
  LIST = ARRAYÆINDEXÅ OF ITEM;

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: INDEX);

PROCEDURE SORT(L,R: INDEX);
VAR
  I,J: INDEX;
  X,Y: ITEM;
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.
«eof»