/*
Selection Sort
  Find the smallest (or largest) number in the series and swap 
  it into the first (or last) index position, find the second 
  smallest (or second largest) and swap it into the second 
  (or second to last) position, repeat until the nth smallest
  number (ie the largest number) has been placed.
*/

class SelectionSort {

  public static void main(String args[]) {
    int a[] = {41, 29, 36, 1, 45, 9, 5, 22, 86, 68};
    int b[] = {41, 29, 36, 1, 45, 9, 5, 22, 86, 68};

    System.out.println("Iterative Sorting: ");    
    System.out.println("Unsorted Array\n");
    printArray(a);
    System.out.println();
    selectionSortIterative(a);
    System.out.println("\nSelection Sorted Array Iteratively\n");
    printArray(a);
    System.out.println();
    
    System.out.println("Recursive Sorting: ");
    System.out.println("Unsorted Array\n");
    printArray(b);
    System.out.println();
    selectionSortRecursive(b);
    System.out.println("\nSelection Sorted Array Recursively\n");
    printArray(b);    
  }
  public static int findMinimumIterative(int a[], int start) {
    int i, currentMin = start;

    for (i = start + 1; i < a.length; i++) {
      if (a[currentMin] > a[i]) {
        currentMin = i;
      }
    }
    return currentMin;
  }
  public static int findMinimumRecursive(int a[]) {
     return findMinimumRecursive(a, 1, 0);
  }
  public static int findMinimumRecursive(int a[], int index, int currentMin) {
    if (index < a.length) {
      if (a[currentMin] > a[index]) {
        currentMin = index;
      }
      currentMin = findMinimumRecursive(a, (index + 1), currentMin);
    }
    return currentMin;
  }
  public static void printArray(int a[]) {
    int i;
    
    String output = "[ ";
    for (i = 0; i < a.length; i++) {
    	output += a[i] + " ";
    }
    System.out.println(output + "]");
  }
  public static void selectionSortIterative(int a[]) {
    int i;

    for (i = 0; i < a.length - 1; i++) {
      swap(a, i, findMinimumIterative(a, i));
      printArray(a);
    }
  }
  public static void selectionSortRecursive(int a[]) {
    selectionSortRecursive(a, 0);
  }
  public static void selectionSortRecursive(int a[], int start) {
    if (start < a.length - 1) {
      swap(a, start, findMinimumRecursive(a, (start + 1), start));
      System.out.println("First " + (start+1) +" elements sorted");
      printArray(a);
      System.out.println();
      selectionSortRecursive(a, start + 1);
    }
  }
  public static void swap(int a[], int index1, int index2) {
    int temp;
    System.out.println("Swapping index " + index1 + " and index "+index2);
    
    temp = a[index1];
    a[index1] = a[index2];
    a[index2] = temp;
  }
}