🔒 Locked

Short C++ quicksort example

Started by Premandrake Mar 7, 2003 at 7:10 PM 1 replies 10.8k views

Original Post

Mar 7, 2003 at 7:10 PM

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).

Beer Hunter

122

Beer Hunter

Mar 7, 2003 at 7:31 PM

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);

Premandrake

Author

Premandrake

Mar 7, 2003 at 7:45 PM

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]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.