5 replies to this topic

[Wintermute]

Greetings to all. I am trying to make a quicksort that is faster than the qsort function from the library. So far, I've come to discover that if I choose the pivot at the middle of the sorting vector, my qsort beats the library qsort, but this depends on the size of the vector. At 100k elements, it's ok, but at 1kk elements, from 100 test cases, the library beast my version 100-0.
So the problem is at larger vectors, and in choosing the proper pivot. Can somebody please give me some hints? I would very much appreciate it.
I can provide the code I have so far if it's needed.

[Flying Dutchman]

I suppose you could check the vector's size and then call whichever sort fits best for that size.

[Wintermute]

Thanks for the reply, but I know that I can do that if I want to. I just want to make a qsort version that beats the library one, but not by integrating any other kind of sort, just by improving the method of choosing the pivot, or maybe something regarding the sorting vector, but I have ran out of ideas.

[WingedPanther]

You can look at using a hash sort, but you're likely to find that the standard library's qsort has already been highly optimized for a variety of types of data.

[Wintermute]

As a type of data, just take in consideration the integer, maybe double. Looking for any other solutions and thanks for the ones so far.

[Wintermute]

No more thoughts on this? :(