Skip to content

Instantly share code, notes, and snippets.

@yohm
Created May 19, 2011 07:13
Show Gist options
  • Save yohm/980335 to your computer and use it in GitHub Desktop.
Save yohm/980335 to your computer and use it in GitHub Desktop.
MyQuickSort error code
// ---------------------------------------
template <class T>
void Swap( std::vector<T>::iterator it1, std::vector<T>::iterator it2) {
T temp = *it1;
*it1 = *it2;
*it2 = temp;
}
// -----------------------------------------
template <class T>
void MyQuickSort( std::vector<T>::iterator begin, std::vector<T>::iterator end) {
if( distance( begin, end) <= 1 ) { return; }
std::vector<T>::iterator pivot = begin;
// Swap( begin, pivot); // since the first element is selected to be the pivot, swapping the pivot position is not necessary
std::vector<T>::iterator it = begin;
it++;
std::vector<T>::iterator last = begin;
for( ; it != end; it++) {
if( *it <= *pivot) {
last++;
Swap( it, last);
}
}
Swap( pivot, last);
MyQuickSort( begin, last);
MyQuickSort( ++last, end);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment