home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / turbo5 / qsort.pas < prev    next >
Pascal/Delphi Source File  |  1988-10-09  |  2KB  |  66 lines
  1.  
  2. { Copyright (c) 1985, 88 by Borland International, Inc. }
  3.  
  4. program qsort;
  5. {$R-,S-}
  6. uses Crt;
  7.  
  8. { This program demonstrates the quicksort algorithm, which      }
  9. { provides an extremely efficient method of sorting arrays in   }
  10. { memory. The program generates a list of 1000 random numbers   }
  11. { between 0 and 29999, and then sorts them using the QUICKSORT  }
  12. { procedure. Finally, the sorted list is output on the screen.  }
  13. { Note that stack and range checks are turned off (through the  }
  14. { compiler directive above) to optimize execution speed.        }
  15.  
  16. const
  17.   max = 1000;
  18.  
  19. type
  20.   list = array[1..max] of integer;
  21.  
  22. var
  23.   data: list;
  24.   i: integer;
  25.  
  26. { QUICKSORT sorts elements in the array A with indices between  }
  27. { LO and HI (both inclusive). Note that the QUICKSORT proce-    }
  28. { dure provides only an "interface" to the program. The actual  }
  29. { processing takes place in the SORT procedure, which executes  }
  30. { itself recursively.                                           }
  31.  
  32. procedure quicksort(var a: list; Lo,Hi: integer);
  33.  
  34. procedure sort(l,r: integer);
  35. var
  36.   i,j,x,y: integer;
  37. begin
  38.   i:=l; j:=r; x:=a[(l+r) DIV 2];
  39.   repeat
  40.     while a[i]<x do i:=i+1;
  41.     while x<a[j] do j:=j-1;
  42.     if i<=j then
  43.     begin
  44.       y:=a[i]; a[i]:=a[j]; a[j]:=y;
  45.       i:=i+1; j:=j-1;
  46.     end;
  47.   until i>j;
  48.   if l<j then sort(l,j);
  49.   if i<r then sort(i,r);
  50. end;
  51.  
  52. begin {quicksort};
  53.   sort(Lo,Hi);
  54. end;
  55.  
  56. begin {qsort}
  57.   Write('Now generating 1000 random numbers...');
  58.   Randomize;
  59.   for i:=1 to max do data[i]:=Random(30000);
  60.   Writeln;
  61.   Write('Now sorting random numbers...');
  62.   quicksort(data,1,max);
  63.   Writeln;
  64.   for i:=1 to 1000 do Write(data[i]:8);
  65. end.
  66.