/*
 * C program that implements Bubble Sort
 * CISC105 07.11.05
 * bubblesort.c
 */

#include<stdio.h>


#define SIZE 10

/*
 * 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;
}

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 numComparisons = 0;
  int numSwaps = 0;

  /* 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");

  /* make all numbers bubble into place.
   * (Can skip position 0 because it gets there by default if the rest
   * are in place.) 
   */
  for( j=1; j < SIZE; j++ ) {
    // bubble a number up
    for( i=0; i < SIZE-1; i++ ) {
      numComparisons++;
      if( array[i] > array[i+1] ) {
	swap( array, i, i+1 );
	numSwaps++;
      }
    }
    print_array( array );
  }

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

  return 0;
}