/* Peter Cline -- August 1
   Sorting an array of integers
*/

#include <stdio.h>
#include <stdlib.h>

void selectionSort_recursive(int array[], int numElements);
void selectionSort_iterative(int array[], int numElements);
void swap(int array[], int index1, int index2);
int findMinIndex(int array[], int start, int end);
void printArray(int array[], int numElements);

int main() {
  // 9 elements
  int numbers[] = {12, 12, 19, 2, 21, 14, 8, 30, 7};

  selectionSort_recursive(numbers, 9);
  printArray(numbers, 9);

  return 0;
}

void selectionSort_recursive(int array[], int numElements) {
  int minIndex;

  if (numElements == 1)
    return;

  printArray(array, numElements);

  minIndex = findMinIndex(array, 0, numElements);
  swap(array, minIndex, 0);

  printArray(array, numElements);

  selectionSort_recursive( &array[1], numElements-1 );

}

void selectionSort_iterative(int array[], int numElements) {
  int leftIndex, i;
  int minIndex;
  int temp;

  for (leftIndex = 0; leftIndex < numElements - 1; leftIndex++) {
    // find the index of smallest array element (after leftIndex)
    minIndex = findMinIndex(array, leftIndex, numElements);

    // swap leftIndex element with the smallest element
    swap(array, leftIndex, minIndex);

    // print array to convince ourselves that it works
    printArray(array, numElements);

  }
}

// swap array elements index1 and index2 in array[]
void swap(int array[], int index1, int index2) {
  int temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

// return the minimum value index between start and end in array[]
int findMinIndex(int array[], int start, int end) {
  int i, minIndex = start;
  for (i = start + 1; i < end; i++) {
    if (array[minIndex] > array[i])
      minIndex = i;
  }
  return minIndex;
}

void printArray(int array[], int numElements) {
  int i;
  for (i = 0; i < numElements; i++) 
    printf("%d ", array[i]);
  printf("\n");
}