<![CDATA[size : 4617
uploaded_on : Tue Aug 11 00:00:00 1998
modified_on : Wed Dec 8 14:03:08 1999
title : Quick sort
org_filename : QUICKSRT.PAS
author : Unknown
authoremail :
description : demonstrates quick sort
keywords :
tested : not tested yet
submitted_by : The CKB Crew
submitted_by_email : ckb@netalive.org
uploaded_by : nobody
modified_by : nobody
owner : nobody
lang : pas
file-type : text/plain
category : pascal-alg-sortsearch
__END_OF_HEADER__
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Program Name : QuickSrt.Pas
Written By : Brad Prendergast
E-Mail : mrealm@ici.net
Web Page : http://www.ici.net/cust_pages/mrealm/BANDP.HTM
Program
Compilation : Borland Turbo Pascal 7.0
Program Description :
This program demonstrates the basics behind the Quick Sort algorithm. This
program is not complex nor is it intended to be. The purpose of this is to
demonstrate the basic building blocks needed to build complex programs. The
Quick Sort Algorithm is widely accepted as the fastest general purpose sort.
The Quick Sort begins by estimating the midrange value in the array. Once
this is determined it breaks the array into two portions, to the left of
the midrange and to the right. Everything less than the midrange goes to
the left and higher to the right. It breaks these two portions down further
repeating this process over until the array has been sorted. If you need
further assistance on this method feel free to e-mail mrealm@ici.net
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
Program QuickSrt;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
{ These are the standard set of compiler directives I opt to use }
{$DEFINE DEBUG}
{$DEFINE Error_Checking}
{$IFDEF Error_Checking}
{$I+} {L I/O Checking }
{$Q+} {L Overflow Checking }
{$R+} {L Range Checking }
{$S+} {L Stack Overflow Checking }
{$ELSE}
{$I-} {L I/O Checking }
{$Q-} {L Overflow Checking }
{$R-} {L Range Checking }
{$S-} {L Stack Overflow Checking }
{$ENDIF}
{$UNDEF Error_Checking}
{$IFDEF DEBUG}
{$D+} {G Debug Information }
{$L+} {G Local Symbol Information }
{$Y+} {G Symbolic Reference Information }
{$ELSE}
{$D-} {G Debug Information }
{$L-} {G Local Symbol Information }
{$Y-} {G Symbolic Reference Information }
{$ENDIF}
{$A+} {G Align Data}
{$B-} {L Short Circuit Boolean Evaluation }
{$E-} {G Disable Emulation }
{$F+} {L Allow Far Calls }
{$G+} {G Generate 80286 Code }
{$N-} {G Disable Numeric Processing }
{$P+} {G Enable Open Parameters }
{$O+} {G Overlay }
{$T-} {G Type @ Operator }
{$V+} {L Var String Checking }
{$X+} {G Extended Syntax Enabled }
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
uses
crt;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
const
numberlocations = 20;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
type
sorted_array = array [ 1..numberlocations ] of integer;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
var
count : integer;
sorted : sorted_array;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
Procedure Switch ( var a, b : integer );
var
c : integer;
begin
c := a;
a := b;
b := c;
end;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
Procedure PartialSort ( l, r : integer; var a : sorted_array);
var
i1, l1, r1, i, j, k : integer;
begin
k := ( a[ l ] + a[ r ] ) div 2;
i := l;
j := r;
repeat
while a[ i ] < k do
inc ( i,1 );
while k < a[ j ] do
dec ( j, 1 );
if i <= j then
begin
switch ( a[ i ], a[ j ] );
inc ( i, 1 );
dec ( j, 1 );
end;
until i > j;
if l < j then
PartialSort ( l, j, a );
if i < r then
PartialSort ( i, r, a );
end;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
Procedure Quicksort ( var item : sorted_array; count : integer );
begin
PartialSort ( 1, count, item );
end;
{=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=}
Begin
clrscr;
Randomize;
Writeln ('Before : ');
for count := 1 to numberlocations do
Begin
sorted[ count ] := random ( 100 );
write ( sorted[ count ]:2, ' ');
end;
QuickSort ( sorted, numberlocations );
writeln;
Writeln ('After : ');
for count := 1 to numberlocations do
write ( sorted[ count ]:2, ' ');
End.
]]>