Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Premandrake

Short C++ quicksort example

This topic is 5610 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I''ve been working with Haskell for a while now and it''s a nice language, but people always see the need to compare code size by resorting to the qsort function or something akin to it. I want to write a qsort function in C++ that equals the terseness of the haskell one (or beats it ) if possible. Here is my start:
  
// Haskell version

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [y|y <- xs, y < x] ++ [x] ++ qsort [y|y <- xs, y >= x]

// C++ version

template<class T,class IT>
void quicksort(IT begin,IT end) {
	if (begin != end) {
		IT it = partition(begin, end, bind2nd(less<T>(),*begin));
		if (it != end) quicksort<T>(begin,it);
		if (it != begin) quicksort<T>(it,end); else quicksort<T>(++it,end);
	}
}
  
Now as you can see the C++ version is slightly longer due to the fact that we don''t have overloaded list operators, so i didn''t create new lists and append them. Of course this also means we are in-place, whereas the Haskell one isn''t.. An example of calling the C++ version:
  
int ary[7] = {5,43,135,1,6,5,68};
vector<int> vec(&myary[0],&myary[7]);
quicksort<int>(vec.begin(),vec.end());
  
Now, I want to get rid of the need for the type T, however since C++ doesn''t have a typeof operator yet, that could be somewhat difficult. Any ideas? Also, any suggestions on how to improve the length would be much appreciated . (Btw, I consider use of STL to be fair game as you can see above).

Share this post


Link to post
Share on other sites
Advertisement
Hmmm...
  
#include <iterator>


template <class IT>
void quicksort(IT begin, IT end) {
typedef typename std::iterator_traits<IT>::value_type T;
// ...



// Or, even better...


#include <algorithm>


template <class IT>
void quicksort(IT begin, IT end) {
std::sort(begin, end); // ;)

}
Also, note that the vector isn''t necessary:
int ary[7] = {5,43,135,1,6,5,68};
quicksort(ary, ary+7);

Share this post


Link to post
Share on other sites
Ah, very nice, thanks .

I must agree that std::sort is the algorithm of choice but as you may have guessed, this is more an esoteric interest thing.

Edit: Oh, I knew vector isn't neccesary there, just trying to illustrate it operates on iterators and while pointers are indeed random access iterators it might lead to a bit of confusion .

[edited by - premandrake on March 7, 2003 8:48:42 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!