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

Gammon Software Solutions forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Qsort and Templates
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?
Qsort and Templates

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Posted by Nick Cash   USA  (626 posts)  [Biography] bio
Date Thu 04 May 2006 09:25 PM (UTC)  [ quote  ]

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   Moderator
Date Reply #1 on Thu 04 May 2006 09:54 PM (UTC)  [ quote  ]
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  (18,772 posts)  [Biography] bio   Forum Administrator
Date Reply #2 on Thu 04 May 2006 10:25 PM (UTC)  [ quote  ]
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)  [ quote  ]
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   Moderator
Date Reply #4 on Sat 06 May 2006 11:34 PM (UTC)  [ quote  ]
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)  [ quote  ]
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   Moderator
Date Reply #6 on Sun 07 May 2006 02:02 AM (UTC)  [ quote  ]
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)  [ quote  ]
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.

5,917 views.

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Go to topic:           Search the forum

[Go to top] top

[Home]

Written by Nick Gammon - 5K

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

[Best viewed with any browser - 2K]    [Internet Contents Rating Association (ICRA) - 2K]    [Web site powered by FutureQuest.Net]