//
// sort.hpp
//
// Template functions for sorting arrays.  These should work
// for any type that has defined the =, <, and >= operators.
//
// Because we're using templates, we define the functions in
// this header file so that the compiler won't complain.
//
// Computer Science S-111, Harvard University
//

#ifndef SORT_H
#define SORT_H

//
// prints an array
//
void printArray(int * array, int n)
{
	cout << "{ ";
	for (int i = 0; i < n; i++) {
		cout << array[i] << " ";
	}
	cout << "}" << endl;
}


//
// swap - swap the values of two variables.
// Used by several of the sorting algorithms below.
//
template <class elt>
void swap(elt& a, elt& b)
{
    elt temp;
    temp = a;
    a = b;
    b = temp;
}

//
// InsertSort - perform insertion sort on the specified array
//
template <class elt>
void InsertSort(elt arr[], int num_objects)
{
    for (int i = 2; i <= num_objects; i++) {
		
		if (arr[i] < arr[i-1]) {
			
	    	// Temporarily store element in arr[0].
	    	arr[0] = arr[i];
	    
	    	// Shift right to make room for element.
	    	int j = i;
	    	while (arr[0] < arr[j - 1]) {
				arr[j] = arr[j - 1];
				j = j - 1;
	    	}
			
	    	arr[j] = arr[0];
		}
    }
}

//
// BinInsertSort - perform binary insertion sort on the specified array
//
template <class elt>
void BinInsertSort(elt arr[], int num_objects)
{
    for (int i = 2; i <= num_objects; i++) {
		if (arr[i] < arr[i - 1]) {
	    	arr[0] = arr[i];

	    	// Use binary search to find insertion point.
	    	int L = 1;
	    	int R = i - 1;

	    	while (L < R) {
				int m = (L + R) / 2;
				if (arr[0] < arr[m]) {
		    		R = m;
				} else {
		    		L = m + 1;
				}
	    	}

	    	// Shift right to make room for element.
	    	for (int j = i; j >= R + 1; j--) {
				arr[j] = arr[j-1];
			}

	    	arr[R] = arr[0];
		}
    }
}

//
// ShellSort - perform Shell sort on the specified array
//
template <class elt>
void ShellSort(elt arr[], int num_objects)
{
    //
    // Find initial increment: one less than the largest
    // power of 2 that is <= num_objects.
    //
    int incr = 1;
    while (2 * incr <= num_objects) {
			   incr = 2 * incr;
	}
    incr = incr - 1;

    // Do insertion sort for each increment.
    while (incr >= 1) {
		
		for (int i = incr + 1; i <= num_objects; i++) {
	    	if (arr[i] < arr[i-incr]) {
				arr[0] = arr[i];

				int j = i;
				while (j > incr  && arr[0] < arr[j-incr]) {
		    		arr[j] = arr[j - incr];
		    		j = j - incr;
				}

				arr[j] = arr[0];
	    	}
		}

	// Calculate increment for next pass.
	incr = incr / 2;
    }
}

//
// minimum - return the index of the smallest element in
// the subarray arr[lower]..arr[upper]
//
template <class elt>
int minimum(elt arr[], int lower, int upper)
{
    int bestpos = lower;

    for (int i = lower + 1; i <= upper; i++) {
		if (arr[i] < arr[bestpos]) {
	    	bestpos = i;
		}
	}

    return bestpos;
}

//
// SelectSort - perform selection sort on the specified array
//
template <class elt>
void SelectSort(elt arr[], int num_objects)
{
    for (int index = 1; index <= num_objects - 1; index++) {
		int min = minimum(arr, index, num_objects);
		swap(arr[min], arr[index]);
    }
}

//
// BubbleSort - perform bubble sort on the specified array
//
template <class elt>
void BubbleSort(elt arr[], int num_objects)
{
    for (int i = 2; i <= num_objects; i++) {
		for (int j = num_objects; j >= i; j--) {
	    	if (arr[j ] < arr[j-1]) {
				swap(arr[j - 1], arr[j]);
			}
		}
	}
}

//
// sift - sift the element in arr[start] down into its correct
// position in a max-at-top heap
//
template <class elt>
void sift(elt arr[], int start, int end)
{
    int parent = start;
    int child = 2 * start;

    // Store the element being sifted in arr[0].
    arr[0] = arr[start];

    // Find where the sifted element belongs.
    while (child <= end) {

		// Compare with the right child if it's bigger.
		if (child < end) {
	    	if (arr[child] < arr[child + 1]) {
				child = child + 1;
			}
		}

		// Check if we're done.
		if (arr[0] >= arr[child]) {
		    break;
		}

		//
		// If not, move child up and move down
		// one level in the tree.
		//
		arr[parent] = arr[child];
		parent = child;
		child = 2 * child;
    }
    
    arr[parent] = arr[0];
}

//
// HeapSort - perform heap sort on the specified array.
//
template <class elt>
void HeapSort(elt arr[], int num_objects)
{
    // Construct a heap from the unsorted array.
    for (int left = num_objects/2; left >= 1; left--) {
		sift(arr, left, num_objects);
	}

    // Repeatedly put elements in their correct positions.
    for (int right = num_objects; right >= 2; right--) {
		//
		// Put the top element (the largest element in
		// the unsorted portion of the array) in its
		// correct position, swapping it with the element
		// currently at that spot.
		//
		swap(arr[1], arr[right]);

		//
		// Rebuild a heap out of the unsorted portion
		// of the array.
		//
		sift(arr, 1, right - 1);
    }
}

//
// QSort - recursively perform quick sort on the subarray
// from arr[L] to arr[R]
//
template <class elt>
void QSort(elt arr[], int L, int R)
{
    int i = L;      // index moving from L to R
    int j = R;      // index moving from R to L

    // Select middle element as the pivot.
    arr[0] = arr[(L + R) / 2];

    // Partition the array.
    do {
		// Find two elements to swap.
		while (arr[i] < arr[0]) {
	    	i = i + 1;
		}
		while (arr[0] < arr[j]) {
	    	j = j - 1;
		}

		if (i <= j) {
	    	swap(arr[i], arr[j]);
	    	i = i + 1;
	    	j = j - 1;
		}
    } while (i <= j);

    // Recursively sort the left and right subarrays.
    if (L < j) {
		QSort(arr, L, j);
	}
    if (j+1 < R) {
		QSort(arr, i, R);
	}
}

//
// QuickSort - perform quicksort on the specified array.
//
template <class elt>
void QuickSort(elt arr[], int num_objects)
{
    QSort(arr, 1, num_objects); 
}

#endif
