SORT routine?

[Rod Suskin]

Hi,
Does anyone have or know where I can find a simple QuickSort routine
for numbers? Or any sort routines?
Thanks,
Rod.

[Ruud van der Ham]

rsu...@iafrica.com (Rod Suskin) wrote:

I have developed a general purpose sort routine quite some time ago
and put irt in one of my standard library units. The implementation is
actually quite simple, becuase the application has to provide code for
comparing and swapping the various elements. The only requirement is
thta the elements must be available via an index (like an array or a
random access file).
I have included the code and a short description of the routine.

The sort is implemented as heapsort, because this sorting algorithm
does not need significant memory space (as quicksort needs,
particularly in case of a perfect ordered set!). The efficiency of
this algorithm is quite good, actually outperfing quicksort in many
reallife situations, where the data are already partly sorted..

*START CODE*
Type
USSortLessType=Function(Index1: LongInt; Index2: LongInt):
Boolean;
USSortSwapType=Procedure(Index1: LongInt; Index2: LongInt);

Function USSort(
IndexLow: LongInt;
IndexHigh: LongInt;
USSortLess: USSortLessType;
USSortSwap: USSortSwapType): Byte;

Label
99;

Var
L: LongInt;
I: LongInt;
J: LongInt;
Length: LongInt;
IR: LongInt;
IRRA: LongInt;

Begin
Length:=IndexHigh-IndexLow+1;
If Length>1 Then
Begin
L:=(Length Div 2)+1;
IR:=Length;

While TRUE Do
Begin
If L>1 Then
Begin
Dec(L);
IRRA:=L;
End
Else
Begin
USSortSwap(IR+IndexLow-1,1+IndexLow-1);
IRRA:=1;
Dec(IR);
If IR=1 Then
Begin
Goto 99;
End;
End;
I:=L;
J:=L+L;
While J<=IR Do
Begin
If J<IR Then
Begin
If USSortLess(J+IndexLow-1,J+1+IndexLow-1) Then
Begin
Inc(J);
End;
End;
If USSortLess(IRRA+IndexLow-1,J+IndexLow-1) Then
Begin
USSortSwap(I+IndexLow-1,J+IndexLow-1);
IRRA:=J;
I:=J;
J:=J+J;
End
Else
Begin
J:=IR+1;
End;
End;
End;
99:
End;

USSort:=0;
End; {USSort}

*END CODE*

*START DESCRIPTION*
The functione USSort may be used to sort a set of elements. The
routine
is transparent to the type of information in the set.
The elements in the set are are indexed and the lower and upper
indexed
are given by the parameters IndexLow and IndexHigh.
The calling program should provide a function USSortLess, which
must return TRUE if the element indexed by the first parameter is
less than the element indexed by the second parameter.
Furthermore, a procedure USSortSwap must be provided. This
routine must swap the elements indexed by the two parameters.

The function returns with 0 if the sort completed successfully.
Otherwise,
the error code 1 is returned, indicating insufficient memory to sort
the set.

Example

Var
Table: Array[1..100] Of Real;

Function SortLess(Index1: LongInt; Index2: LongInt): Boolean; Far;
Begin
SortLess:=Table[Index1]<<Table[Index2];
End;

Procedure SortSwap(Index1: LongInt; Index2: LongInt); Far;
Var
Temp: Real;
Begin
Temp:=Table[Index1];
Table[Index1]:=Table[Index2];
Table[Index2]:=Temp;
End;

Begin
{Fill Table}
Result:=USSort(1,100,SortLess,SortSwap);

In this example, the table with 100 reals will be sorted.
*END DOCUMENTATION*

Please let me know if you need further assistance (via the Newsgroup
of email rvd...@ect.nl)

--
rvd...@ect.nl
Ruud Th. van der Ham

[Keith Rogers]

In article <40pprb$6...@grovel.iafrica.com>,

rsu...@iafrica.com (Rod Suskin) wrote:
>Does anyone have or know where I can find a simple QuickSort routine
>for numbers? Or any sort routines?

http://garbo.uwasa.fi/ (or, ftp://garbo.uwasa.fi/pc, the PC ftp site)
is a good place for all kinds of Pascal routines. You should be able
to find what you're looking for there.

Keith
(speaking only for myself)

[Stephan Eggermont]

Ruud van der Ham (rvd...@ect.nl) wrote:
> The sort is implemented as heapsort, because this sorting algorithm
> does not need significant memory space (as quicksort needs,
> particularly in case of a perfect ordered set!). The efficiency of
> this algorithm is quite good, actually outperfing quicksort in many
> reallife situations, where the data are already partly sorted..

Oh no, another victim of a bad quicksort implementation!

A quicksort needs O(log n) stack space, worst case. Just remember to sort
the smallest part first.

A good quicksort also switches to insertion sort for small sets and uses
a smart pivot strategy (at least median of three). And it uses recursion,
not iteration (explicit construction of a stack is slow).

Stephan