#include <iostream>
#include <stdlib.h>

void print(int a[], int size);
void selection_sort(int a[], int size);

const int ARRAY_SIZE = 50000;

int main() {

  int numbers[ARRAY_SIZE];

  int i;
  for (i=0; i < ARRAY_SIZE; i++)
    numbers[i] = rand();
  
  //int numbers[10] = {2, 36, 18, 1, 13, 7, 11, 8, 4, 79};
  //print(numbers, ARRAY_SIZE);

  selection_sort(numbers, ARRAY_SIZE);

  //print(numbers, ARRAY_SIZE);

}

void print(int a[], int size)
{
  int i;
  for (i=0; i < size; i++)
    cout << a[i] << " ";
  cout << endl;
}  

void selection_sort(int a[], int size)
{
  int pos;
  // Last card is automatically sorted,
  // Move smallest card left to position "pos"
  for (pos = 0; pos < size-1; pos++)
  {
    // Look for smallest card left
    int smallest_num = a[pos];
    int smallest_loc = pos;
    
    for (int j=pos+1; j < size; j++)
    {
      if (a[j] < smallest_num)
      {
        smallest_num = a[j];
	smallest_loc = j;
      }
    }
      
    // smallest_num and smallest_loc now correspond to smallest card
    
    // Swap to current position if smaller
    if (smallest_num < a[pos])
    {
      int swap = a[pos];
      a[pos] = smallest_num;
      a[smallest_loc]  = swap;
    } // if smallest_num < a[pos]
  } // for pos
    
} // selection sort