/*****************
 * sort_selection.c
 *
 *     $ gcc sort_selection.c -o sort_selection
 *     $ ./sort_selection
 *
 *     -- selection sort --
 *    
 *     test  case  : [3, 20, 5, 7, 8, 1, 10, 2, ]
 *     after sort : [1, 2, 3, 5, 7, 8, 10, 20, ]
 *    
 *                 n         seconds
 *      ------------    ------------
 *               100      0.00001600
 *               300      0.00011200
 *              1000      0.00084500
 *              3000      0.00599900
 *             10000      0.06508500
 *             30000      0.58306300
 *            100000      6.56642100
 *            300000     59.84103900
 *
 * This algorithm is a loop i from 1..n within a loop j from i..n,
 * and so is O(n**2) in time complexity. 
 *
 * The loop invariant, which verifies that the algorithm is correct,
 * is that in the outer loop, the numbers at positions 0 through i
 * will be in sorted, i.e. smaller than all the others and in their
 * correct places.
 *
 * TODO : 
 *   test each function individually, 
 *   with cases with known verifiable answers.
 *
 * Jim Mahoney | cs.bennington.college | MIT License | March 2021
 *****************/

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

int do_assertion;  // 1 => true ; 0 => false

double get_secs(){
  // return time since program launch
  clock_t ticks = clock();
  double seconds = (double)ticks / (double)CLOCKS_PER_SEC;
  //printf(" ticks since epoch = %lu ; ", ticks);        // debug
  //printf(" ticks per second = %d \n", CLOCKS_PER_SEC); // .
  //printf(" seconds = %.6f \n", seconds);               // .
  return seconds;
}

int* get_randoms(int n){
  // return array of n random numbers, randoms[0] to randoms[n-1].
  int i;
  int* randoms = malloc(n * sizeof(int));
  for (i=0; i<n; i++) randoms[i] = rand();
  return randoms;
}

void init_randoms(){
  // initialize the pseudo random number generator using the system time
  srand(time(NULL));
}

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

void swap(int* ap, int* bp){
  // give two pointers to integers, swap those integers.
  // example usage: swap(&array[10], &array[12])
  int temp = *ap;
  *ap = *bp;
  *bp = temp;
}

void assert_invariant(int i, int* numbers){
  // selection sort loop invariant :
  // Check to see numbers[0] to numbers[i] should be in order.
  int j;
  for (j=1; j<=i; j++){
    if (numbers[j-1] > numbers[j]){
      printf(" OOPS - loop invariant violated !! \n");
    }
  }
}

int find_min_index(int i, int n, int* numbers){
  // find and return the index of the smallest of numbers[i] to numbers[n-1]
  int j;
  int i_smallest = i;         // the first, at "i", is the smallest so far.
  for (j=i+1; j<n; j++){      // start search at the next one.
    if (numbers[j] < numbers[i_smallest]){    // smaller ?
      i_smallest = j;                         // yes, so remember it.
    }
  }
  return i_smallest;
}

void sort(int n, int* numbers){
  // -- selection sort --
  // for i=0,1,2,3, ... , n-1,
  //    find smallest of numbers[i] to numbers[n-1],
  //    swap that with numbers[i]
  int i, i_min;
  for (i=0; i<n; i++){
    i_min = find_min_index(i, n, numbers);  // find smallest in remaining list
    swap(&numbers[i], &numbers[i_min]);     // put that at end of sorted part
    if (do_assertion){
      // 0 up to i should now be in the right place.
      // Only check for this if the global do_assertion is non-zero.
      assert_invariant(i, numbers);
    }
  }
}

double time_sort(int n, int* numbers){
  // return time in seconds taken to sort n numbers.
  double start, stop;
  start = get_secs();
  sort(n, numbers);
  stop = get_secs();
  return stop - start;
}  

int main(){
  int ns[] = {100, 300, 1000, 3000, 10000, 30000, 100000, 300000};
  int ns_size = 8;
  int test_array[] = {3, 20, 5, 7, 8, 1, 10, 2};  // just a simple test case
  int test_size = 8;
  int i, n;
  int* randoms;
  double elapsed;
  
  init_randoms();
  printf(" -- selection sort -- \n\n");

  // first, let's test to see if it works.
  do_assertion = 1;   // turn on the validity assertion.
  printf(" test case  : ");
  print_array(test_size, test_array);
  sort(test_size, test_array);
  printf(" after sort : ");
  print_array(test_size, test_array);
  printf("\n");

  // and now get some times
  do_assertion = 0;  // turn off validity assertion - just the sort
  printf("  %12s    %12s  \n", "n", "seconds");
  printf("  %12s    %12s  \n", "------------", "------------");
  for (i=0; i<ns_size; i++){
    n = ns[i];
    randoms = get_randoms(n);
    elapsed = time_sort(n, randoms);
    printf("  %12d    %12.8f  \n", n, elapsed);
  }
  
  return 0;
}