Lab #4, Friday 9/21

On the calendar page is a PDF file about recursive bubblesort. In this lab you are to write a recursive implementation of selection sort. You can follow this link, https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm, to review how selection sort works, and also see selection sort in animated action at http://sorting.at. We also went over a non-recursive version in class.

Briefly, in selection sort we find the smallest value in the array and then move it all the way to the left, at index 0. Then we repeat by finding the smallest value in the array starting at index 1, and then move it all the way to index 1. By repeating this we end up sorting the array. In a recursive formulation, the idea is as follows:

1. Start with an unsorted array. Let startIndex be the index of the first element in the array, and endIndex be the index of the last element in the array.
   
   
2. Search from startIndex to endIndex for the smallest value in the array. Let's say that it is found at position indexOfMin.
   
   
3. Swap the values in the array at startIndex and indexOfMin. This means that the smallest value in the array is now at startIndex.
   
   
4. Repeat the process, but pretend that the leftmost element isn't there. You can do this by making a recursive call to the selectionSort routine, except increase the value in startIndex by 1 to bypass the leftmost value:
   
   
5. When steps 2-3 are repeated on this new portion of the array we end up with the second smallest value next to the smallest value:
   
   
6. By repeating this process until we reach endIndex, we will sort the entire array.

TO DO: Start with the template for recursive selection sort below. Fill it in with the recursive selectionSort function, a swap function, and a main function that tests the selectionSort function with a test array and outputs the contents to ensure the sort is working correctly.

#include <iostream>
using namespace std;

// Function prototypes
void swap(int &x, int &y);
void selectionSort(int a[], int startIndex, int endIndex);


// Recursively sort array a.
// startIndex: The index of the starting element in array a where we want sorting to begin.
//             For example, startIndex would be 0 to start at the first element.
// endIndex:   The index of the last element in array a where we want sorting to end.
//             For example, in an array of length 5, this would be 4 to specify the last element.
void selectionSort(int a[], int startIndex, int endIndex)
{
  // Base case or termination condition: quit if start and end are the same.
  // This would specify to sort only a single element, which is already sorted.
  if (startIndex == endIndex)
	return;

  int indexOfMin = startIndex;
  // Write code below that finds the index of the smallest value in the array from
  // startIndex +1   to  endIndex,  inclusive.
  // The variable indexOfMin should contain the index of this position.  For example, if
  // startIndex=3, endIndex=7, then if the smallest value in the array from a[4],a[5],a[6], and a[7]
  // is at index 5, then indexOfMin should get set to 5




  // Once indexOfMin is found, swap the values in the array at indexOfMin and startIndex
  swap(a[indexOfMin], a[startIndex]);  // You have to write the swap function

  // Complete the recursive call below so it only searches the array from startIndex+1 to endIndex
  selectionSort(/* fill in here */);
}



// Write the swap function so it swaps integers x and y by reference


// Write the main function with a test case of selectionSort