[Home] [Downloads] [Search] [Help/forum]


Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Qsort and Templates

Qsort and Templates

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Posted by Nick Cash   USA  (626 posts)  [Biography] 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
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] 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
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] 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
[Go to top] top

Posted by Nick Cash   USA  (626 posts)  [Biography] 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
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] 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
[Go to top] top

Posted by Nick Cash   USA  (626 posts)  [Biography] 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
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] 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
[Go to top] top

Posted by Nick Cash   USA  (626 posts)  [Biography] 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
[Go to top] 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.


17,246 views.

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]