/* sorts.cpp
   Created by Simon Cheng
   Date: 20020812(1) */

#ifndef SORTS_CPP
#define SORTS_CPP

/* note: it is possible to not have the size of what is being sorted
         in the argument, but it would facilitate the process and save
         a few lines of code */
typename <class T>
void bubble_sort (T*, int);
template <class T>
void insertion_sort (T*, int);
template <class T>
void quicksort(T* array, int left, int right);
typename <class T>
void selection_sort(T*, int);

/* for the following sorts to work one must overload the following
   operators if not working with "traditional" types:
   [], pointer dereference (*)?, pointer arithmetic?, in/decrement?
*/

typename <class T>
void bubble_sort (T* array, int size)
{
  T temp=0;
  for (int i=1; i<size; i++)
    for (int j=i; j>0; j--)
      if (array[j]<array[j-1]) {
        temp=array[j];
        array[j]=array[j-1];
        array[j-1]=temp;
      }
      else
        break;
  return;
}

template <class T>
void insertion_sort (T* array, int size)
{
  (void) array;
  (void) size;
}

template <class T>
void selection_sort(T* array, int size)
{
  int smallest, temp;
  for (int i=0; i<size-1; i++) {
    smallest=i+1;
    for (int j=i+1; j<size; j++)
      if (array[j]<array[smallest])
        smallest=j;
    if (array[smallest]<array[i]) {
      temp=array[i];
      array[i]=array[smallest];
      array[smallest]=temp;
    }
  }
  return;
}

template <class T>
void quicksort(T* array, int left, int right)
{
  // both partitioning and quicksort is here in one function
  if (right-left==0)
    return;
  T* pivot=array+left; // may want to set pivot at right to start or some median
  T* left_ptr=array+left;
  T* right_ptr=array+right;
  T temp;
  while (right_ptr-left_ptr>0) {
    while (pivot-left_ptr>0) {
      if (*left_ptr>*pivot) {
        temp=*left_ptr;
        *left_ptr=*pivot;
        *pivot=temp;
        pivot=left_ptr;
        right_ptr++;
        break;
      }
      else
        left_ptr++;
    }
    while (right_ptr-pivot>0) {
      if (*right_ptr<*pivot) {
        temp=*right_ptr;
        *right_ptr=*pivot;
        *pivot=temp;
        pivot=right_ptr;
        left_ptr++;
        break;
      }
      else
        right_ptr--;
    }
  }
  temp=pivot-array; // temp is now index of pivot
  if (temp-left>0)
    quicksort (array, left, temp-1);
  if (right-temp>0)
    quicksort (array, temp+1, right);
  return;
}


#endif