home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / CMPLTPAS.ZIP / QUIKSORT.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1988-07-14  |  2.1 KB  |  69 lines
  1. {->>>>QuickSort<<<<--------------------------------------------}
  2. {                                                              }
  3. { Filename : QUIKSORT.SRC -- Last Modified 7/14/88             }
  4. {                                                              }
  5. { This is your textbook recursive quicksort on an array of key }
  6. { records, which are defined as the type show below:           }
  7. {                                                              }
  8. {     KeyRec = RECORD                                          }
  9. {                Ref     : Integer;                            }
  10. {                KeyData : String30                            }
  11. {              END;                                            }
  12. {                                                              }
  13. {     From: COMPLETE TURBO PASCAL 5.0  by Jeff Duntemann       }
  14. {    Scott, Foresman & Co., Inc. 1988   ISBN 0-673-38355-5     }
  15. {--------------------------------------------------------------}
  16.  
  17. PROCEDURE QuickSort(VAR SortBuf : KeyARRAY;
  18.                         Recs    : Integer); 
  19.  
  20.  
  21. PROCEDURE KeySwap(VAR RR,SS : KeyRec); 
  22.  
  23. VAR 
  24.   T : KeyRec; 
  25.  
  26. BEGIN 
  27.   T := RR; 
  28.   RR := SS; 
  29.   SS := T 
  30. END; 
  31.  
  32.  
  33. PROCEDURE DoSort(Low, High : Integer); 
  34.  
  35. VAR 
  36.   I,J   : Integer; 
  37.   Pivot : KeyRec; 
  38.  
  39. BEGIN 
  40.   { Can't sort if Low is greater than or equal to High... } 
  41.   IF Low < High THEN 
  42.     BEGIN 
  43.       I := Low; 
  44.       J := High; 
  45.       Pivot := SortBuf[J]; 
  46.       REPEAT 
  47.         WHILE (I < J) AND (SortBuf[I].KeyData <= Pivot.KeyData) DO I := I + 1;
  48.         WHILE (J > I) AND (SortBuf[J].KeyData >= Pivot.KeyData) DO J := J - 1;
  49.         IF I < J THEN KeySwap(SortBuf[I],SortBuf[J]); 
  50.       UNTIL I >= J; 
  51.       KeySwap(SortBuf[I],SortBuf[High]); 
  52.       IF (I - Low < High - I) THEN 
  53.         BEGIN 
  54.           DoSort(Low,I-1);    { Recursive calls to DoSort! } 
  55.           DoSort(I+1,High) 
  56.         END 
  57.       ELSE 
  58.         BEGIN 
  59.           DoSort(I+1,High);    { Recursive calls to DoSort! } 
  60.           DoSort(Low,I-1) 
  61.         END 
  62.     END 
  63. END; 
  64.  
  65.  
  66. BEGIN 
  67.   DoSort(1,Recs); 
  68. END;  { QuickSort } 
  69.