[ back to toc ]

Quicksort Advanced

Date: 2002/02/04 10:55

Q:
1] I use Redhat 7.2, Visual C++, Miracle C, Borland 5,...

2] I want to make a powerfull sort. I sort a large number of element. Thus
I use Quicksort (and don't want to change but to improve it). I assume
your know the algorithm of quicksort.

The disavantage of quicksort is that it determine the correct place of the
pivot and then remake a quicksort to the left and the right of the pivot
until he sorts 1 element.

I want to accelerate this by using another sort algorithm when there is
few numbers to sort.
I have added a condition in the quicksort :

Quicksort (int i /* the first elmt*/, int j /*last*/)
{
if (i!=j)
{
if (j-i>8)
sequentialsort(i,j)
else
{
/*classic quicksort code*/
...
}
}
..
}

I would like to know if it is possible to determine which sorting
algorithm is better to use in quicksort when j-i is small.

Is sequential sort is approriate in this situation ?
A:
>I assume your know the algorithm of quicksort.

Yes, you are correct.

The speed of a sorting is dependent on the number of comparsons and the
element swaps.

Quick sort garantees that the (probable) number of comparisons is minimal.
It is fully guaranteed or probable guaranteed depending on how you choose
the pivot element. If you choose pivot elements with some simple algorith,
for example choosing allways the first element, then a simple sorted array
will result extremely slow sorting O(n^2).

To determine which is the better in case the array is small, you have to
compare the execution time of the

1. actual implementation of the two sorts
2. on the actual machine architecture
3. with the actual data which looks like that you use (statistically)

To get the deepest details on sorting I recommend the three red book of
Donald Knuth. Also read the small book of Shannon on the information
theory.

Regards,
Peter

[ back to toc ]