#### Archived

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

# Short C++ quicksort example

## 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:


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 on other sites
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 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]

• ### Forum Statistics

• Total Topics
628306
• Total Posts
2981947

• 10
• 11
• 12
• 11
• 10