Dec 062017
 
Qsort routine with C source. This is a non-recursive version that greatly improves processing speed.
File CSORTS.ZIP from The Programmer’s Corner in
Category C Source Code
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

Leave a Reply