Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to "verify" your details, making threats, or asking for money, are
spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the
password reset link.
Entire forum
➜ Programming
➜ General
➜ Qsort and Templates
It is now over 60 days since the last post. This thread is closed.
Refresh page
| Posted by
| Nick Cash
USA (626 posts) Bio
|
| Date
| Thu 04 May 2006 09:25 PM (UTC) Amended on Thu 04 May 2006 09:36 PM (UTC) by Nick Cash
|
| Message
| 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. |
~Nick Cash
http://www.nick-cash.com | | Top |
|
| Posted by
| David Haley
USA (3,881 posts) Bio
|
| Date
| Reply #1 on Thu 04 May 2006 09:54 PM (UTC) |
| Message
| 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. |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | | Top |
|
| Posted by
| Nick Gammon
Australia (23,070 posts) Bio
Forum Administrator |
| Date
| Reply #2 on Thu 04 May 2006 10:25 PM (UTC) |
| Message
| | That looks neat. Also consider the STL with its sorting abilities. |
- Nick Gammon
www.gammon.com.au, www.mushclient.com | | Top |
|
| Posted by
| Nick Cash
USA (626 posts) Bio
|
| Date
| Reply #3 on Sat 06 May 2006 07:19 AM (UTC) |
| Message
|
Quote:
Don't make the output flag a preprocessor define; instead you can make it a default argument of the template.
Do you have an example of this? My use of templates has been rather limited thus far.
|
~Nick Cash
http://www.nick-cash.com | | Top |
|
| Posted by
| David Haley
USA (3,881 posts) Bio
|
| Date
| Reply #4 on Sat 06 May 2006 11:34 PM (UTC) |
| Message
| 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. |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | | Top |
|
| Posted by
| Nick Cash
USA (626 posts) Bio
|
| Date
| Reply #5 on Sun 07 May 2006 12:57 AM (UTC) |
| Message
|
Quote:
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. :-)
Heh, no problem :P
But, even so...
Quote:
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.
Do you have a small example of this? |
~Nick Cash
http://www.nick-cash.com | | Top |
|
| Posted by
| David Haley
USA (3,881 posts) Bio
|
| Date
| Reply #6 on Sun 07 May 2006 02:02 AM (UTC) |
| Message
| 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. |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | | Top |
|
| Posted by
| Nick Cash
USA (626 posts) Bio
|
| Date
| Reply #7 on Sun 07 May 2006 04:10 AM (UTC) |
| Message
| | Ah, I see now. Thanks :) |
~Nick Cash
http://www.nick-cash.com | | Top |
|
The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).
To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.
18,974 views.
It is now over 60 days since the last post. This thread is closed.
Refresh page
![[Go to top]](/images/gototop.gif)
top