How good is qsort() in stlib.h

[ToniAz]

Hello everyone!

I'm writing a median function that would most probably be called no less than 500,000 times in one run. The data size/cardinality is however 5, 7, or 9 (pretty small). Therefore I really need to cut down on time:

-What sore algorithm does it implement?

-Do I need to to define the comparison function in the same way it is defined here:

http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

I'm not familiar with the syntax...


Thanks!


EDIT: According to the page,

int comparator ( const void * elem1, const void * elem2 );
The function must accept two parameters that are pointers to elements, type-casted as void*. These parameters should be cast back to some data type and be compared.

One down, one to go...

[TheIdeasMan]

ToniAz

If you are writing a C++ program , then use the sort algorithm, this will be as efficient as it can be. Your choice of container will influence the efficiency - map is probably the best as it uses a self balancing AVL tree structure. map is also a good choice given you have 500,000 items.

If you are writing a C program, (I am not sure because sometimes people use a C approach because they haven't discovered the C++ way), then use the qsort.

Generally the library functions are the most efficient way, (that's why they are in the library)

Although with that much data, you should implement your own tree structure ADT, because the computer will struggle dealing with that amount of data in array (for example) no matter how good the library function is .

[ToniAz]

Thanks for your quick reply!

If you are writing a C program, (I am not sure because sometimes people use a C approach because they haven't discovered the C++ way), then use the qsort.

I am actually using C, not C++. And the only data strucure I'm using is a 2D matrix as being consistent with the library tools I'm using.

Although with that much data, you should implement your own tree structure ADT, because the computer will struggle dealing with that amount of data in array (for example) no matter how good the library function is .

I don't think I can have a better representation of my data, as the only representation that means something is matrix form.

Generally the library functions are the most efficient way, (that's why they are in the library)

So you mean, they use a better algorithm than that used by qsort()?

[TheIdeasMan]

I am actually using C, not C++. And the only data strucure I'm using is a 2D matrix as being consistent with the library tools I'm using.

ok, The worry is how much data you have - you could easily overflow the stack / heap or just run out of memory.

How big is the array? Total number of elements 500,000?

Is there any way to process the array in parts? Can the rows be sorted individually?

I don't think I can have a better representation of my data, as the only representation that means something is matrix form.

An array could still be stored in a tree. A tree node could contain a pointer to a row. Although I am not sure whether that would be an advantage or not. You could pull all the data out of the array and into a Binary Sort Tree or AVL tree (with each node containing the data itself ), then get it out in sorted order and put into the new array. That should work but you need to find a C implementation of a AVL tree. You won't need a sort function as such because the way that the tree is built does the sorting.

So you mean, they use a better algorithm than that used by qsort()?

I meant that whatever sort function is in the library (I thought it was qsort) then it will most likely be efficient.

[ToniAz]

I actually ran the application before reading this and was surprised that it didn't impact the running time!! However, I'll look into your suggestion for future work.

All the best.

[TheIdeasMan]

Maybe your library functions implement efficient data structures internally.

I am pleased to be of some help.