stable_quick_sort.h File Reference

---

Detailed Description

This header files contains the defintion of the template function stable_quick_sort.

Definition in file stable_quick_sort.h.

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
template<typename T, typename U>
void	concatinate_data (U &lhs, U &pivot, U &rhs, U &output_data)
template<typename T, typename U>
void	stable_quick_sort (const U &input_data, U &output_data)

---

Function Documentation

template<typename T, typename U>

void concatinate_data	(	U &	lhs,
		U &	pivot,
		U &	rhs,
		U &	output_data
	)

Assumes:
U is a container for objects of class T
U has a begin, and end function
U has an assignment operator<br/> Error Behavior:
if any of the assumptions do not hold, the code will not compile
Description:
This function concatinates the data in lhs, pivot, and rhs and stores the data in output_data

Definition at line 14 of file stable_quick_sort.h.

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

Assumes:
U is a container for objects of class T
U has a begin, and end function
U has a random access iterator
U has a bidirctional iterator
U has a const forward iterator
U has a size function
U has a push_back, push_front and insert function
U has a copy constructor and a default constructor
U has an assignment operator<br/> U has a constructor which can copy a value an arbitrary number of times
Error Behavior:
if any of the assumptions do not hold, the code will not compile
Description:
This algorithm instantiates the quick sort algorithm. The data is sorted in a stable fasion
because the push_back, push_forwarad and insert functions are called at the appropriate places,
to preserve the order of equivalent elements.

Definition at line 41 of file stable_quick_sort.h.

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

---