Dec 062017
Qsort routine with C source. This is a non-recursive version that greatly improves processing speed. | |||
---|---|---|---|
File Name | File Size | Zip Size | Zip Type |
INT-SORT.C | 1277 | 554 | deflated |
INT-SORT.EXE | 12688 | 7565 | deflated |
LODCSWAP.C | 799 | 345 | deflated |
QDSORT.C | 1293 | 582 | deflated |
QFSORT.C | 1292 | 586 | deflated |
QISORT.C | 1227 | 551 | deflated |
QUICKEST.TXT | 5779 | 2247 | deflated |
QUICKTAB.DOC | 710 | 362 | deflated |
RQSORT.C | 1592 | 701 | deflated |
Download File CSORTS.ZIP Here
Contents of the QUICKEST.TXT file
THE QUICKEST SORT?
by
Ron Andrews
Is the sort routine I am about to describe really the quickest?
Perhaps not; however, I have yet to find one that will beat it in
sorting arrays of random numbers.
Some time ago (years, in fact), I had need of a sort function
to use in a PLI-80 program. I eventually found a really good non-
recursive version of the quicksort algorithm in Niklaus Wirth's book
"Algorithms + Data Structures = Programs". I translated the routine
(which was written in Pascal) into PLI-80, and found it to be quite
fast. Some time later, I needed a sort function for the Whitesmiths
RT-11 "C" compiler because of a serious bug in the supplied function
(when given a sorted array, it recursed itself to death). When
testing the new function (written in "C"), I found it to be
significantly faster than the supplied routine. The speed gain is
probably due to the non-recursive nature of the algorithm. Since
then, I have modified it for all the "C" compilers which I use.
The major modification that I have made to the routine is the
ability to sort almost anything, not just arrays. The sort function
has no knowledge of the data being sorted except for the number of
items. As an example, the Unix-style "qsort" function supplied with
most "C" compilers will not sort multiple items such as a separate
"x", "y", and "z" arrays to sort "z" within "y" within "x".
Defining a structure "struct xyz { int x,y,z; } xyz[n];" will do
something similar and can be sorted; however, this is not always
practical. The data "int x[n],y[n],z[n];" (which might have come
1
from a FORTRAN program) cannot be sorted with the standard "qsort"
function.
The algorithm is quite flexible and may even be (and actually
was) re-written in FORTRAN or assembler. Versions have been adapted
to sort arrays of integers, floats, and doubles. The original
algorithm in the book actually sorted arrays.
The function is called as follows: "rqsort(n,load,check,swap);"
"n" is the number of items to sort (2 - 32767 only).
"load(i)" is a function which loads item "i" into temporary
storage.
The temporary storage must be static and external to the "load"
and "check" functions since it is used by both.
"check(i)" is a function which compares the stored item with
item "i".
Return -1 if temporary < item "i".
Return 0 if temporary == item "i".
Return 1 if temporary > item "i".
It is mandatory that all three conditions be checked!
"swap(i,j)" is a function which swaps items "i" and "j".
Obviously the functions need intimate knowledge of the items
being sorted. Unfortunately, there is a restriction on the number
of objects that can be sorted when using 16-bit integers. Since
most objects are integers or larger and a segment on an 8088-based
computer is only 32768 integers in length, this in not too much of a
restriction. This restriction does not apply to systems using 32-
bit integers; however, the size of "stackl" and "stackr" in the
function should be increased to 36 in order to accommodate more
items. Note that the "unsigned" cast is used in calling the "load"
2
function to prevent integer overflow from causing a negative value
when using 16-bit integers. It should not be necessary when using
32-bit integers. Of course, the function must be compiled for the
correct model. I have used the "static" declaration with the local
variables since this causes slightly faster execution times on an
8088 processor. It should make no difference with an 80286 or 80386
processor.
The general purpose, double, float, and integer versions of the
sort function are included in this package. Sample "load", "check",
and "swap" functions to sort "z" within "y" within "x" are also
included.
I have compared the "C" versions of the algorithm using several
compilers on a PC clone running PC-DOS 3.1 at 8 MHz and on two Unix
systems. The sort functions were compiled with the compiler being
tested. It should be mentioned that the Computer Innovations "C"
compiler was a very old one made in 1984; however, this was not a
compiler test. The test was to compare the supplied "qsort" function
with the new functions. All three PC-DOS compilers have more recent
versions available. With the Unix systems, I was the only user at
the time. The integer size on these systems was 32 bits. The
differences in timing are shown in the accompanying table.
This may not be the quickest sort around. In some cases, such
as already sorted objects, it is not. Despite some shortcomings, I
think it can be a valuable tool where the maximum speed and
versatility is required.
3
December 6, 2017
Add comments