stable_quick_sort.h

Go to the documentation of this file.

#ifndef stable_quicksort_h

template<typename T, typename U>
void concatinate_data( U& lhs, U& pivot, U& rhs, U& output_data)
{
  using namespace std;

  output_data = lhs;
  copy( pivot.begin(), pivot.end(), back_insert_iterator<U >( output_data));
  copy( rhs.begin(), rhs.end(), back_insert_iterator<U >( output_data));
}

template<typename T, typename U>
void stable_quick_sort( const U& input_data, U& output_data) 
{
  using namespace std;

  if (input_data.size() <= 1) {
    output_data = input_data;
    return;
  } 
  int offset = input_data.size() / 2;

  U pivot( 1, input_data[offset]);
  U lhs, rhs;
  typename U::const_iterator pt;
  typename U::const_iterator pt_end;

  pt_end = input_data.begin() + offset;
  for (pt = input_data.begin();
       pt != pt_end;
       ++pt)
    {
      if (*pt < *pivot.begin()) {
        lhs.push_back( *pt);
      } else if (*pivot.begin() < *pt) {
        rhs.push_back( *pt);
      } else {
        if (pivot.size() == 1) {
          pivot.push_front( *pt);
        } else {
          pivot.insert( pivot.end()-1, *pt);
        }
      }
    }

  pt++ = pt_end;
  for (pt = input_data.begin(); 
       pt != input_data.end();
       ++pt)
    {
      if (*pt < *pivot.begin()) {
        lhs.push_back( *pt);
      } else if (*pivot.begin() < *pt) {
        rhs.push_back( *pt);
      } else {
        pivot.push_back( *pt);
      }
    }

  U lhs_sorted;
  stable_quick_sort< T, U>( lhs, lhs_sorted);

  U rhs_sorted;
  stable_quick_sort< T, U>( rhs, rhs_sorted);

  concatinate_data< T, U>( lhs_sorted, pivot, rhs_sorted, output_data);
}

#endif

---