CODEWITHSUNDEEP
c++sortingqsort
Bi.
Bi.

Reputation: 1906

qsort in C++ is slow

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 std::qsort which results in the process running slow (as this process iterates several times).

Is there a better sorting algorithm that I could use?

Upvotes: 1

Views: 3166

Answers (8)

Makach
Makach

Reputation: 7569

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.

Upvotes: 1

Igor Krivokon
Igor Krivokon

Reputation: 10275

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.

Upvotes: 19

David Thornley
David Thornley

Reputation: 57046

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.

Upvotes: 4

Brian Liang
Brian Liang

Reputation: 7774

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.

Upvotes: 5

agorenst
agorenst

Reputation: 2425

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.

Upvotes: 9

Jodi
Jodi

Reputation: 900

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.

Upvotes: 2

Brian Webster
Brian Webster

Reputation: 30855

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.

Upvotes: 4

EFraim
EFraim

Reputation: 13028

  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).

Upvotes: 4

Related Questions