Archived

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

Premandrake

Short C++ quicksort example

Recommended Posts

Premandrake    175
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
Beer Hunter    712
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
Premandrake    175
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