Mail Archives: djgpp/1997/07/01/16:52:32
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
- Raw text -