home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / PASCALA.ZIP / QUIXCOM.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1991-05-09  |  3.6 KB  |  129 lines
  1. (* Stop recursion after size is 10 and use insertion sort *)
  2. PROGRAM Compsorts(Input,Output,File1);
  3.   mscs55 #7b compare quick sorts.}
  4. CONST MaxSize = 8192;
  5. TYPE  ArrayType = ARRAY[0..MaxSize] OF Integer;
  6. VAR B,C,D: ArrayType;
  7.     StartTime, EndTime, Size: Integer;
  8.     File1: Text;
  9.  
  10. (*********************************************************)
  11. (*  QuickSort-- Recursive version with drag              *)
  12. (*********************************************************)
  13.   PROCEDURE QuickSort  (VAR A: ArrayType; Size:Integer);
  14.  
  15.     PROCEDURE Sort(L,R: Integer);
  16.       VAR Temp, I, J, BegginValue: Integer;
  17.           X,Logme:                Integer;
  18.           Log:                    Real;
  19.  
  20.       BEGIN
  21.       I:= L;
  22.       J:= R;
  23.       BegginValue:= A[(L+R) DIV 2];
  24.       REPEAT
  25.         WHILE A[I] < BegginValue DO  (* Search from left *)
  26.           I:= I+1;
  27.         WHILE A[J] > BegginValue DO (* Search from right *)
  28.           J:= J-1;
  29.         IF I<=J THEN
  30.           BEGIN
  31.             (* Drag Intoduced *)
  32.             For X := 1 to 20 Do
  33.             BEGIN
  34.               LogMe := A[I + J] + X;
  35.               Log   := ln(Logme);
  36.             END;
  37.             (* Drag Concluded *)
  38.           Temp:= A[I];
  39.           A[I]:= A[J];
  40.           A[J]:= Temp;
  41.           I:= I+1;
  42.           J:= J-1;
  43.           END;
  44.       UNTIL  I >= J;
  45.       IF L < J THEN Sort(L,J);
  46.       IF I < R THEN Sort(I,R);
  47.     END;  (* Sort *)
  48.   BEGIN
  49.   Sort(1, Size);
  50.   END;
  51.  
  52.  
  53. (*********************************************************)
  54. (*  QuickSort-- Recursive version till reaches a         *)
  55. (*              certain size.                            *)
  56. (*********************************************************)
  57.   PROCEDURE ReviseQuix(VAR A: ArrayType; Size:Integer);
  58.  
  59.     PROCEDURE RevSort(L,R: Integer);
  60.       VAR Temp, I, J, BegginValue,Pass,
  61.           Z,S: Integer;
  62.       BEGIN
  63.       I:= L;
  64.       J:= R;
  65.       IF (L+R) > 10 THEN  (* if the remaining list is greater than *)
  66.                           (* a certain size do quicksort           *)
  67.                           (* else do insertion sort                *)  
  68.         BEGIN (* Quicksort *)
  69.         BegginValue:= A[(L+R) DIV 2];
  70.         REPEAT
  71.           WHILE A[I] < BegginValue DO  (* Search from left *)
  72.             I:= I+1;
  73.           WHILE A[J] > BegginValue DO (* Search from right *)
  74.             J:= J-1;
  75.           IF I<=J THEN
  76.             BEGIN
  77.             Temp:= A[I];
  78.             A[I]:= A[J];
  79.             A[J]:= Temp;
  80.             I:= I+1;
  81.             J:= J-1;
  82.             END;
  83.         UNTIL  I >= J;
  84.         IF L < J THEN RevSort(L,J);
  85.         IF I < R THEN RevSort(I,R);
  86.         END (* Quicksort *)
  87.       ELSE
  88.         FOR Pass:= L TO R DO  (* Insert item 'Pass' *)
  89.           BEGIN
  90.           Z:= Pass;
  91.           S:= A[Pass];   (* Copy item to be inserted *)
  92.           WHILE S < A[Z-1] DO
  93.             BEGIN
  94.             A[Z]:= A[Z-1]; (* Move item down in list *)
  95.             Z:= Z-1;
  96.             END;
  97.           A[Z]:= S;  (* Perform Insertion *)
  98.           END;
  99.     END;  (* Sort *)
  100.   BEGIN
  101.   RevSort(1, Size);
  102.   END;
  103.  
  104. BEGIN   (*******************  MAIN  ***********************)
  105. Reset(File1);
  106. B[0]:= 0;    (* Bumper for top of list *)
  107. Size:= 0;
  108. WHILE not Eof(File1) DO
  109.   BEGIN
  110.   Size:= Size + 1;
  111.   Readln(File1,B[Size]);
  112.   END;
  113. C:= B; D:= B;
  114.  
  115. Writeln('Array Size: ',Size:0);
  116. Writeln;
  117.  
  118. StartTime:= Clock;
  119. QuickSort  (C, Size);
  120. EndTime:= Clock;
  121. Writeln('QuickTime with drag:  ',EndTime-StartTime:0);
  122.  
  123. StartTime := Clock;
  124. ReviseQuix(D, Size);
  125. EndTime:=Clock;
  126. Writeln('Revised QuickTime:  ',EndTime-StartTime:0);
  127. END.     (****************  COMPSORTS  **********************)
  128. 
  129.