quicksort in C++ is slow

Question

I have 9 values in the form of a matrix and need to compute the median from these values as part of a simulation process.

I use quicksort in C++ (i.e qsort()) which results in the process running slow (as this process iterates several times).

Is there a better sorting algorithm that I could use?

Answer 1

Sorting to get a median is very inefficient. You could use STL nth_element instead:

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

Note: the nth_element will modify the vector/array v. Make a copy first if you need to preserve the original.

Answer 2

Please please please never recommend bubble sort except to masochists!

For small values, insertion sort is best, and its good for other applications (nearly sorted data of any length).

Edit: cleaned up formatting, emphasizing suggested answer.

Answer 3

Only 9 values? Quicksort is overkill.

Perhaps use insertion sort, bubble sort or other simpler sorting algorithms when working with smaller datasets.

Performance

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with the substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.

However, granted, you did not even have to sort to get the median as others have suggested.

Answer 4

1. As onebyone mentioned there is no need to sort completely to get a median.

2. STL has sort algorithm which usually can perform comparison inlining. It also has smarter algorithm than guaranteed by qsort, with worstcase of O(NlgN).

Answer 5

Using quicksort for only 9 values is going to be rather inefficient. For such a small sample size, you're much better off utilizing a selection sort or replacement sort... there is very little overhead in these sorting methods.

Quicksort and Mergesort really shine once your sample size reaches a threshold, perhaps 50+.

In these situations, I'd write my own code rather than use a built-in function.

Answer 6

The std::sort() algorithm is almost always preferable to qsort(). It's typically easier to use and runs faster.

If you want to get into detail, there's actually a family of sorting algorithms. Stroustrup writes in The C++ Programming Language that std::sort is often not the exact right thing to use. In this case, std::nth_element() is probably what you want.

Answer 7

You don't have enough values to work with Quicksort and you should use less advanced algorithms (ex: Bubble sort, Insertion sort, ... explanation here.

There is a cost associated to Quicksort's setup and when you don't have enough values, it's useless to use this beast.

Answer 8

Insertion Sort..

On small datasets you can use different algorithms to get optimal performance. QuickSort shines once the dataset grows.

There are different approaches. You can use data structures where you sort on insert, and there are onces where you sort the complete dataset. You just need to find your optimal algorithm.