home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0019_QUICK5.PAS.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  2.3 KB  |  86 lines
  1. {
  2. >I'm in need of a FAST way of finding the largest and the smallest
  3. >30 numbers out of about 1000 different numbers.
  4.  
  5.   ...Assuming that the 1000 numbers are in random-order, I imagine
  6.   that the simplest (perhaps fastest too) method would be to:
  7.  
  8.     1- Read the numbers in an Array.
  9.  
  10.     2- QuickSort the Array.
  11.  
  12.     3- First 30 and last 30 of Array are the numbers you want.
  13.  
  14.   ...Here's a QuickSort demo Program that should help you With the
  15.   sort:
  16. }
  17.  
  18. {$A+,B-,D-,E-,F-,I-,L-,N-,O-,R-,S+,V-}
  19. {$M 60000,0,0}
  20.  
  21. Program QuickSort_Demo;
  22. Uses
  23.   Crt;
  24.  
  25. Const
  26.   co_MaxItem = 30000;
  27.  
  28. Type
  29.   Item    = Word;
  30.   ar_Item = Array[1..co_MaxItem] of Item;
  31.  
  32.  
  33.   (***** QuickSort routine.                                           *)
  34.   (*                                                                  *)
  35. Procedure QuickSort({update} Var ar_Data  : ar_Item;
  36.                     {input }     wo_Left,
  37.                                  wo_Right : Word);
  38. Var
  39.   Pivot,
  40.   TempItem  : Item;
  41.   wo_Index1,
  42.   wo_Index2 : Word;
  43. begin
  44.   wo_Index1 := wo_Left;
  45.   wo_Index2 := wo_Right;
  46.   Pivot := ar_Data[(wo_Left + wo_Right) div 2];
  47.   Repeat
  48.     While (ar_Data[wo_Index1] < Pivot) do
  49.       inc(wo_Index1);
  50.     While (Pivot < ar_Data[wo_Index2]) do
  51.       dec(wo_Index2);
  52.     if (wo_Index1 <= wo_Index2) then
  53.       begin
  54.         TempItem := ar_Data[wo_Index1];
  55.         ar_Data[wo_Index1] := ar_Data[wo_Index2];
  56.         ar_Data[wo_Index2] := TempItem;
  57.         inc(wo_Index1);
  58.         dec(wo_Index2)
  59.       end
  60.     Until (wo_Index1 > wo_Index2);
  61.     if (wo_Left < wo_Index2) then
  62.       QuickSort(ar_Data, wo_Left, wo_Index2);
  63.     if (wo_Index1 < wo_Right) then
  64.       QuickSort(ar_Data, wo_Index1, wo_Right)
  65. end;        (* QuickSort.                                           *)
  66.  
  67. Var
  68.   wo_Index  : Word;
  69.   ar_Buffer : ar_Item;
  70.  
  71. begin
  72.   Write('Creating ', co_MaxItem, ' random numbers... ');
  73.   For wo_Index := 1 to co_MaxItem do
  74.     ar_Buffer[wo_Index] := random(65535);
  75.   Writeln('Finished!');
  76.   Write('Sorting  ', co_MaxItem, ' random numbers... ');
  77.   QuickSort(ar_Buffer, 1, co_MaxItem);
  78.   Writeln('Finished!');
  79.   Writeln;
  80.   Writeln('Press the <ENTER> key to display all ', co_MaxItem,
  81.           ' sorted numbers...');
  82.   readln;
  83.   For wo_Index := 1 to co_MaxItem do
  84.     Write(ar_Buffer[wo_Index]:8)
  85. end.
  86.