/*
 * C program that implements Selection Sort
 * CISC105 07.11.05
 * selectionsort.c
 */

#include<stdio.h>

#define SIZE 10

/* Eek!  A global variable!  But, until next week, we have no other
 * way of "returning" multiple values.
 */
int numComparisons = 0;

/*
 * Precondition: index1 and index2 are valid indices of a
 * Postcondition: the values a[index1] and a[index2] are swapped
 */
void swap( int a[], int index1, int index2 ) {
  int temp = a[index1];
  a[index1] = a[index2];
  a[index2] = temp;
}

/*
 * highestIndex: where to stop looking in the array. 
 * Returns the index in the array (up to highestIndex) that
 * contains the maximum value.
 */ 
int findMax( int a[], int highestIndex ) {
  int i=0;
  int max = a[highestIndex];
  int maxIndex = highestIndex;

  for( i=0; i < highestIndex; i++ ) {
    numComparisons++;
    if( max < a[i] ) {
      max = a[i];
      maxIndex = i;
    }
  }
  return maxIndex;
}

void print_array( int a[] ) {
  int i;
  for( i = 0; i < SIZE; i++ ) {
    printf("%d ", a[i] );
  }
  printf("\n");
}

int main() {
  
  int array[SIZE];
  int i, j;
  int maxUnsorted = SIZE-1;
  int numSwaps = 0;
  int maxIndex;

  /* SES: Why did I choose to test with this array? */
  /* initialize array to 10, 9, ..., 1 */
  for( i=0; i < SIZE; i++ ) {
    array[i] = SIZE-i;
  }
  
  printf("Initial array: ");
  print_array( array );
  printf("\n");
  printf("Sorting...\n");

  /* sort, starting from the back of the array
   * move the maximum value in the unsorted array
   * into the last position of the unsorted array
   */
  for( j=SIZE-1; j >= 0; j-- ) {
    
    maxIndex = findMax( array, j );
    numComparisons++;
    if( maxIndex != j ) {
      swap( array, j, maxIndex );
      numSwaps++;
    }
    print_array( array );
  }

  printf("Selection sort required %d comparisons\n", numComparisons);
  printf("Selection sort required %d swaps\n", numSwaps);

  return 0;
}