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?? ==?

Edited 6 Years Ago by -DLS-: n/a

This article has been dead for over six months. Start a new discussion instead.