Date: Tue, 1 Jul 1997 15:41:02 -0400 (EDT)
From: "Art S. Kagel" <kagel AT ns1 DOT bloomberg DOT com>
To: Benjamin D Chambers <chambersb AT juno DOT com>
Cc: djgpp AT delorie DOT com
Subject: Re: QSort speed?
In-Reply-To: <19970701.100927.5183.0.chambersb@juno.com>
Message-Id: <Pine.D-G.3.91.970701152312.372B-100000@dg1>
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Precedence: bulk

On Tue, 1 Jul 1997, Benjamin D Chambers wrote:

> Generally, is qsort pretty fast?
> 
> I had been planning to sort my list using a double linked list, starting
> each time from the previously entered element (since elements tend to
> come in bunches near each other), but would the effort be worth it when I
> could use qsort?  (Or am I going to get the standard "Time it and see"
> answer? :)

Generally, it is best to take advantage of any knowledge you have of the 
existing and new data.  Here are some guidelines:

1) Yes, qsort is very fast (the library version does not exhibit the 
traditional qsort worst case behavior with sorted lists).

2) Even bubble sorting the new elements one at a time starting from the 
beginning of the list will tend to be faster than qsorting the entire 
list repeatedly.  Caviat: This may not be true if the list gets long.

3) If there really is locality to the arriving data elements then your 
plan will be even better.  True locality will solve the problem of long 
lists mentioned in the caviat to 2).

4) If you can batch the inputs, PREPENDING them to the existing list, and 
resort the list after each batch with qsort this MAY be even faster 
overall.  Caviat: Appending the new elements will tend to be slower for 
qsort than prepending.

5) If you can convert your list into a tree structure you will probably 
out-perform all but a best case dataset under option 3.

6) Keep in mind that qsort does not deal with linked lists so either:
  a) If the list is allocated from contiguous memory you can sort it like 
an array and then re-link the list afterwards walking the element array, 
or:
  b) allocate an array of pointers to the list elements and sort that 
array then re-link the list by walking the pointer array.

Art S. Kagel, kagel AT bloomberg DOT com