PROGRAM QUICKSORT(INPUT, OUTPUT ) ;

(* PARTITION-XCHANGE SORT, AFTER J. SEDGEWICK,  S. HAZEGHI.

   M ::= SIZE OF THE PARTITIONS TO BE BUBBLE-SORTED
   N ::= NUMBER OF ELEMENTS TO BE SORTED ;
   N1 ::= N+1 ;
   STACK_SIZE ::= MAX # OF UNSORTED PARTITIONS ( >= 2*(LOG(N)-3), LOG IS BASE 2)
*)

LABEL 101,111 ;

CONST   M = 9 ;  N = 5009;  N1 = 5010 ;STACK_SIZE = 25;

VAR L,R,P,I,J,V,T,NN,NN1 : INTEGER ;
    A : ARRAY [0..N1] OF INTEGER ;
    STACK : ARRAY [0..STACK_SIZE] OF INTEGER ;
    (* STACK_SIZE  2*(LG(N)-3) *)

PROCEDURE PRINTDATA ;

    (* TO PRINT THE RAW AND SORTED DATA, 10 NUMBERS PER LINE *)

    BEGIN
    FOR I := 1 TO NN1 DO
        BEGIN
        IF (I MOD 10) = 1 THEN  WRITELN() ;
        WRITE(A[I]:6 ) ;
        END;
    END (*PRINTDATA*) ;

    BEGIN  (* QUIKSORT *)

    REPEAT

      WRITELN(' ') ;
      WRITE(' NUMBER OF VALUES TO BE SORTED', ' (0 <= N <= 5000) :') ;
      READ(NN) ;
      WRITELN(NN:6) ;  WRITELN(' ') ;
      IF (NN <= 0) OR (NN > N)  THEN EXIT(99) ;
      NN1 := NN+1 ;

      (* I- GENERATE RANDOM DATA FOR SORTING *)

      WRITELN(' GENERATE N=', NN:6,' RANDOM POSITIVE INTEGERS.') ;
      WRITELN(' ') ;

      A[1] := 0; L := 2; R := NN1; P := 0;
      FOR I := 1 TO NN DO
          BEGIN  A[I+1] := A[I]*31415+4537;
          IF A[I+1] <= 0 THEN
              BEGIN  A[I+1] := -A[I+1] ;
              A[I+1] := A[I+1]+1
              END ;
          END ;

      WRITELN(' ') ;
      WRITELN(' START SORTING :') ;  WRITELN(' ') ;
      PRINTDATA ;

      (* II- PARTITION THE SORT DATA *)

      REPEAT  I := L-1; J := R; V := A[R];
          REPEAT
              REPEAT I := I+1 UNTIL (A[I] >= V) ;
              A[J] := A[I];
              REPEAT J := J-1 UNTIL (A[J] <= V) ;
              IF I >= J THEN GOTO 101 ;
              A[I] := A[J]
          UNTIL  FALSE ;
      101:IF I <> J THEN  J := J+1;
          A[J] := V;
          IF J-L > R-J THEN
              BEGIN
              IF M >= J-L THEN
                  BEGIN  IF P = 0 THEN GOTO 111 ;
                  R := STACK[P+1];  L := STACK[P];  P := P-2;
                  END
              ELSE IF R-J > M THEN
                      BEGIN  P := P+2 ;  STACK[P] := L ;
                      STACK[P+1] := J-1 ;  L := J+1
                      END
                  ELSE  R := J-1
              END
          ELSE IF M >= R-J THEN
                  BEGIN  IF P = 0 THEN GOTO 111 ;
                  R := STACK[P+1];  L := STACK[P];  P := P-2;
                  END
              ELSE IF J-L > M  THEN
                      BEGIN  P := P+2 ;  STACK[P] := J+1 ;
                      STACK[P+1] := R ;  R := J-1
                      END
                  ELSE  L := J+1
      UNTIL  FALSE ;

      (* III- EXCHANGE SORT EACH PARTITION *)

  111:FOR I := 2 TO NN1 DO
          IF A[I] < A[I-1] THEN
              BEGIN
              V := A[I] ;  J := I-1 ;
              REPEAT  A[J+1] := A[J];  J := J-1  UNTIL (A[J] <= V) ;
              A[J+1] := V
              END ;

      WRITELN(' ') ;  WRITELN(' END SORTING N=', NN:6 ,' POSITIVE INTEGERS') ;
      WRITELN(' ');
      PRINTDATA ;


    UNTIL FALSE ;

    END (* QUIKSORT *).