• #### Why is it faster than qsort()?

Posted by Legacy on 06/22/1999 12:00am

Originally posted by: Martin Ziacek

I received e-mail with request to explain, why my template is faster than qsort() function. I think, it is
interesting question for everyone.

First, I explain quick sort algorithm. It is based on partitioning array in two parts, divided by element called pivot. Pivot could be choose median value of the values from part of array going to be sorted, but it is a big performance hit to look for median value. Therefore it is better choose value from middle of array. After pivot is known, all values smaller than pivot is moved to the lower (left) part of array and bigger values to upper (right) part of array (when array is sorting ascending). And then everything begins again, in both parts of array separately, until whole array is sorted.

Sources for qsort() function you can find in \DevStudio\Vc\Crt\Src\Qsort.c (I installed Visual C++ 5.0 to D:\DevStudio\Vc).

When I compared qsort() sources with my QuickSort() function template, I found:

1. qsort() is not recursive

Author(s) of qsort() uses their own stacks to remember borders of parts of array. It could be performance hit (it needs more CPU clocks than recursive call of function).

2. qsort() is too complicated and too long

In the qsort() you can find plenty of comparisons and calculations. More comparisons & calculations = more instructions = slower function. qsort() function copies more elements of array than it is necessary too. Can not believe? Compare it:

QuickSort():

while (pArr[j] < str) j++;

qsort():

do {
loguy += width;
} while (loguy <= hi && comp(loguy, lo) <= 0);

Above you can see parts from both functions. Both do the same thing.
You can find unnecessary copy operation too.

3. qsort uses 'goto'

I do not think, that 'goto' will produce slower code, but in qsort() function it is used on places, where Pentium processors can not predict, which instructions will be executed, I think. So, it could decrease performance too.

4. optimization for speed and for processor

When you have your own code to compile, you can optimize it for speed and for specific processor. I can say, it will bring much faster code every time. Well, when I rebuild my demo program without optimization for speed, QuickSort() function template left still faster (try it) than qsort() function, but two times slower than version optimized for speed.

So, if my QuickSort() function template and array template are not too fast for you, feel free use them.