// Course:            CS 14

// Lecture Section:   Enter your lecture section number here (1, 2, etc)
// Lab Section:       Enter your lab section number here (21, 22, etc)
// Assignment #:      Enter the assignment number here (1, 2, etc)

// First Name:        Enter your FIRST name here (eg, John)
// Last Name:         Enter your LAST name here (eg, Doe)
// ID Number:         Enter your ID number here (eg, 12-345-678)
// Email address:     Enter your UCR email address here (eg, jdoe@cs.ucr.edu)

// ===============================================================

#ifndef _CS14_SORTING
#define _CS14_SORTING


// Just include the interface so we can sort *any*
// implementation of ADT Array...
#include "array.h"

namespace cs14 {

// ******************* SORTING ALGORITHMS *******************
// Helper to swap the value of two variables.
template <class T>
void swap( T &a, T &b )
{
  T t = a; a = b; b = t;
}

// Plain bubble sort; always runs all passes, even when
//   not necessary. O(n^2) for any input.
template <class T>
void bubbleSort( Array<T> &a )
{
  for (int i = a.length()-1; i > 0; i--)
  {
    for (int j = 0; j < i; j++)
    {
      if (a[j] > a[j+1])
      {
        swap( a[j], a[j+1] );
      }
    }
  }
}

// Smarter bubble sort; stops as soon as nothing needs to be done
//   anymore. O(n) if input is sorted already, O(n^2) otherwise.
template <class T>
void bubbleSmart( Array<T> &a )
{
  bool sorted = false;
  for (int i = a.length()-1; (i > 0) and !sorted; i--)
  {
    sorted = true; // assume sorted until proven otherwise
    for (int j = 0; j < i; j++)
    {
      if (a[j] > a[j+1])
      {
        sorted = false; // if we had to swap once, it wasn't sorted
        swap( a[j], a[j+1] );
      }
    }
  }
}

// Plain selection sort; put maximum element at end until sorted.
//   O(n^2).
template <class T>
void selection( Array<T> &a )
{
  for (int i = a.length()-1; i > 0; i--)
  {
    int max = 0;
    for (int j = 1; j <= i; j++)
    {
      if (a[j] > a[max]) { max = j; }
    }
    if (i != max)
    {
      swap( a[i], a[max] );
    }
  }
}

// Plain insertion sort; insert from upper (unsorted) into lower
//   (sorted) part; thanks to Klaus Koehler. O(n^2).
template <class T>
void insertion( Array<T> &a )
{

	// >>>> WRITE YOUR CODE FOR INSERTION SORT HERE <<<<<
	for (int unsorted = 1; unsorted < a.length(); ++ unsorted)
	{
		int nextItem = a[unsorted];
		int loc = unsorted;
		for (; (loc > 0) && (a[loc-1] > nextItem); --loc)
			a[loc] = a[loc-1];

		a[loc] = nextItem;
	}
}


} // namespace cs14

#endif /* _CS14_SORTING */