Hi guys, I need some help for a homework I have due in 8 hours.
I was assigned to write a recursive sorting algorithm that works with iterators :mad:
After googling, and putting code together I got this.
#include <algorithm>
template<class IT>
void quicksort(IT begin,IT end) { \\begin and end are iterators
typedef typename std::iterator_traits<IT>::value_type T; \\T is the value type of the dereferenced iterator
if (begin != end) {
IT it = partition(begin, end, bind2nd(less<T>(),*begin)); \\I guess this splits it up into magic
if (it != end) quicksort(begin,it); \\magic recursion
if (it != begin) quicksort(it,end);
else quicksort(++it,end);
}
}
But what the hell is this doing??
IT it = partition(begin, end, bind2nd(less<T>(),*begin));
Can someone explain to me what its doing so I can try and finish my program it without using the partition, bind2nd, less(), functions?
Apparently it's equal to this
#include <algorithm>
template< typename IT, typename Compare >
void quick_sort( IT beg, IT end, Compare cmp ) {
if( first != last ) {
IT left = first;
IT right = last;
IT pivot = left++;
while( left != right ) {
if( cmp( *left, *pivot ) ) {
++left;
} else {
while( (left != right) && cmp( *pivot, *right ) )
--right;
MySwap( left, right );
}
}
--left;
MySwap( first, left );
quick_sort( first, left, cmp );
quick_sort( right, last, cmp );
}
}
template< typename BidirectionalIterator >
inline void quick_sort( IT first, IT last ) {
quick_sort( first, last, std::less_equal< typename std::iterator_traits< IT >::value_type >()
);
}
which is what a classmate did, but this has a runtime error, and i have no idea what cmp() does. //compare?? ==?