home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / QUIKSORT.ZIP / QUIKSORT.PAS
Encoding:
Pascal/Delphi Source File  |  1987-08-03  |  2.6 KB  |  84 lines
  1. {$A-}
  2. Program QS_Demo;
  3.  
  4. Const
  5.    N = 400;
  6.  
  7. Type
  8.    Index = 1..N;
  9.    ToBeSorted = Integer;
  10.    SortArray = Array[1..N] Of ToBeSorted;
  11.  
  12. Var
  13.    Data: SortArray;
  14.    I: Integer;
  15.  
  16.  
  17. {   Quicksort Procedure
  18.    Requirements: $A- directive (Do not generate absolute code, TURBO),
  19.                  Const N = # of items (May be global variable),
  20.                  Type Index = 0..N (Or Integer, maybe - N is minimum.),
  21.                  Type ToBeSorted = Type to do sort on, and
  22.                  Type SortArray = Array[1..N] Of ToBeSorted (N min. again).
  23.    Procedure Syntax: Quicksort(Data) where Data a variable of type SortArray.
  24.                                                                              }
  25. Procedure Quicksort(Var SortData: SortArray);
  26.    Procedure Bubblesort(Low,High: Index);
  27.       Var Switched: Boolean;
  28.           Counter, Pass: Integer;
  29.           Swap: ToBeSorted;
  30.       Begin
  31.          Pass := 1;
  32.          Repeat
  33.             Switched := False;
  34.             For Counter := Low To High-Pass Do
  35.                Begin
  36.                   If SortData[Counter]>SortData[Counter+1] Then
  37.                      Begin
  38.                         Swap := SortData[Counter];
  39.                         SortData[Counter] := SortData[Counter+1];
  40.                         SortData[Counter+1] := Swap;
  41.                         Switched := True
  42.                      End;
  43.                End;
  44.             Pass := Pass + 1;
  45.          Until Switched = False;
  46.       End;
  47.    Procedure Partition(Low,High: Index);
  48.       Var LowPos,HighPos: Index;
  49.           Pivot,Swap: ToBeSorted;
  50.       Begin
  51.          LowPos := Low;
  52.          HighPos := High;
  53.          Pivot := SortData[(Low+High) Div 2];
  54.          Repeat
  55.             While SortData[LowPos] < Pivot Do LowPos := LowPos + 1;
  56.             While Pivot < SortData[HighPos] Do HighPos := HighPos - 1;
  57.             If LowPos <= HighPos Then
  58.                Begin
  59.                   Swap := SortData[LowPos];
  60.                   SortData[LowPos] := SortData[HighPos];
  61.                   SortData[HighPos] := Swap;
  62.                   LowPos := LowPos + 1;
  63.                   HighPos := HighPos - 1;
  64.                End
  65.          Until LowPos>HighPos;
  66.          If HighPos-Low>6 Then Partition(Low,HighPos)
  67.          Else Bubblesort(Low,HighPos);
  68.          If High-LowPos>6 Then Partition(LowPos,High)
  69.          Else Bubblesort(LowPos,High);
  70.       End;
  71.    Begin
  72.       Partition(1,N);
  73.    End;
  74.  
  75. Begin
  76.    For I := 1 To N Do
  77.       Data[I] := Random(1000);
  78.    Writeln('Initialized data... ');
  79.    For I := 1 To N Do
  80.       Write(Data[I]:4);
  81.    Quicksort(Data);
  82.    Writeln('Sorted Data... ');
  83.    For I := 1 To N Do
  84.