**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 ]