Qsort and Templates

Just felt like I would share a bit more of nifty code with the world. The quick sort algorithm can be kind of confusing to deal with, and someone recently asked me how to do it using templates. Well, here you go.

http://ew.xidus.net/download/qsort

Its quite easy to play with. To change the number of elements to sort just change the ARRAY_LENGTH define. If you do any significant length you can turn off the array output by commenting out the other define.

On my local university's machine, it sorted 5 million random integers in 14 seconds.

[edit]
I've posted a version of Qsort that works in the MIPS assembly language. It appears the format is a bit skewed, and all code in MIPS is pretty ugly, but its there for any interested.

Nice work. If I could make two suggestions:

• Don't make the output flag a preprocessor define; instead you can make it a default argument of the template.
• Similarly don't print to std::cout by default; you can set a template parameter that defaults to address of cout; that way if I want to print, I set the template flag parameter to true and the second argument to some other output stream. This isn't a very important suggestion because it's for debugging, but the first suggestion is a little more important.

But still, very good stuff!


And regarding assembly: MIPS is much, much nicer than x86. x86 is an absolute nightmare... MIPS is actually rather elegant.

That looks neat. Also consider the STL with its sorting abilities.

Do you have an example of this? My use of templates has been rather limited thus far.

I'm sorry, I thought you were outputting inside the quicksort functions, not in the main function. After looking at the code more carefully I see that the #define has no effect whatsoever on the algorithm itself. Sorry for the confusion. :-)

But what I meant is that you can pass arguments to templates that aren't actually types. You can pass in primitive data values, and maybe whole objects (but I'm not at all sure about that, I'd have to check). It lets you do something quite similar to a #define, except that you decide whether or not you want it when you instantiate the template, not once for everybody at compile time.

Heh, no problem :P

But, even so...


Do you have a small example of this?

Sure. See:
http://david.the-haleys.org/programming/misc/quicksort-template.cpp.html

I modified your quicksort to print out the pivot chosen at each step of the quicksort algorithm.

It turns out that I was wrong about default arguments; you can't use them for functions, but only for defining classes it seems. But still, this example shows how you can pass not only types to templates, but also data itself. It's much nicer to specify behavior of a function like that than with #defines, even if strictly speaking #defines are faster since you compile the code as desired, instead of having to make runtime checks all the time.

Ah, I see now. Thanks :)