#include <stdio.h>

#define SIZE 10
#define DEBUG 1

void insert(int [], int, int);
void insertion_sort(int [], int);
void swap(int *, int *);
void bubble_sort(int [], int);
void selection_sort(int [], int);
void print_array(int [], int);

int main()
{
  int arr1[SIZE] = {9, 23, 32, 1, -4, 37, 43, 22, 4, 0};
  int arr2[SIZE] = {9, 23, 32, 1, -4, 37, 43, 22, 4, 0};
  int arr3[SIZE] = {9, 23, 32, 1, -4, 37, 43, 22, 4, 0};

  printf("Beginning insertion sort\n");
  insertion_sort(arr1, SIZE);
  print_array(arr1, SIZE);
  printf("\n");

  printf("Beginning bubble sort\n");
  bubble_sort(arr2, SIZE);
  print_array(arr2, SIZE);
  printf("\n");

  printf("Beginning selection sort\n");
  selection_sort(arr3, SIZE);
  print_array(arr3, SIZE);
  printf("\n");

  return 0;
}

void print_array(int arr[], int size)
{
  int i;

  for(i = 0; i < size; i++)
    printf("%3d ", arr[i]);
  printf("\n");
}

void insert(int arr[], int length, int value)
{
  int i = length-1;
  while(i >= 0 && arr[i] > value)
  {
    arr[i+1] = arr[i];
    i--;
  }
  arr[i+1] = value;
}

void insertion_sort(int arr[], int length)
{
  int i ;
  for(i = 1; i < length; i++)
  {
    insert(arr, i, arr[i]);

    if(DEBUG)
      print_array(arr, length);
  }
}

void swap(int * a, int * b)
{
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

void bubble_sort(int arr[], int size)
{
  int swapped, i;

  do
  {
    swapped = 0;
    for(i = 0; i < size-1; i++)
    {
      if(arr[i] > arr[i+1])
      {
        swap(&arr[i], &arr[i+1]);
        swapped = 1;
      }
    }

    if(DEBUG)
      print_array(arr, size);

  } while(swapped);
}

void selection_sort(int arr[], int size)
{
  int i, j;
  int min;

  for(i = 0; i < size-1; i++)
  {
    min = i;
    for(j = i+1; j < size; j++)
      if(arr[j] < arr[min])
        min = j;

    if(i != min)
      swap(&arr[i], &arr[min]);

    if(DEBUG)
      print_array(arr, size);

  }
}