home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / MODULA2 / SORT_MD2.ZIP / QUIKSORT.MD2 < prev   
Encoding:
Text File  |  1987-02-14  |  1.4 KB  |  62 lines
  1.  
  2. QUIKSORT.MD2
  3.   (* This module should be saved under the name QWKSORT.CAP.  *)
  4.  
  5.  
  6. PROCEDURE QuickSort( A : ARRAY OF Item ; N : CARDINAL );
  7. (* Capsule QuickSort: A skeleton procedure for using the      *)
  8. (* quicksort algorithm.  See reference 3.              *)
  9.  
  10. PROCEDURE Compare ( S1, S2 : ARRAY OF CHAR): BOOLEAN;
  11. (* Compare two strings of the same maximum lengths.          *)
  12.  
  13. CONST eos = 0C; (* End-Of-String *)
  14.  
  15. VAR Less, Stop : BOOLEAN;
  16.     i : CARDINAL;
  17.  
  18. BEGIN
  19.     Less := FALSE;
  20.     Stop := FALSE;
  21.     i := 0;
  22.       WHILE (i <= HIGH(S1)) AND (Less = FALSE) AND (Stop = FALSE) DO
  23.     IF (S1[i] <> eos) AND (S2[i] <> eos)
  24.       THEN (* Proceed in comparison *)
  25.         IF (S1[i] < S2[i]) THEN Less := TRUE ELSE INC(i) END;
  26.       ELSE Stop := TRUE (* Reached the end of string *)
  27.     END;
  28.       END;
  29.     RETURN Less;
  30. END Compare;
  31.  
  32. PROCEDURE Sort( L, R : CARDINAL);
  33.  
  34. VAR i, j : CARDINAL;
  35.     X, W : Item;
  36.  
  37. BEGIN
  38.     X := A[(L + R) DIV 2];
  39.     REPEAT
  40.       WHILE Compare(A[i].key,X.key) DO INC(i) END;
  41.       WHILE Compare(X.key,A[i].key) DO DEC(j) END;
  42.       IF i <= j THEN
  43.     W = A[i] := A[i] ; A[i] := A[j] ; A[j] := W ;
  44.     INC(i) ; DEC(j)
  45.       END;
  46.     UNTIL i > j ;
  47.     IF L < j THEN Sort(L,j) END;
  48.     IF i < R THEN Sort(i,R) END;
  49. END Sort;
  50.  
  51. BEGIN
  52.  
  53.     Sort(1,N)
  54.  
  55. END QuickSort;
  56.  
  57. 
  58.     IF L < j THEN Sort(L,j) END;
  59.     IF i < R THEN Sort(i,R) END;
  60. END Sort;
  61.  
  62. BEGIN
  63.