#include <iostream>

using namespace std;


/**
 * Swap element i and j in array arr.
 */
void swap(int arr[], int i, int j)
{
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

/*
 * Implemented from psuedocode at wikipedia.  
 * See: http://en.wikipedia.org/wiki/Bubble_sort
 * 
 * returns the number of comparisons performed to sort the list.
 */
int bubbleSort(int arr[], int n)
{
  int numComparisons = 0;
  
  bool swapped;
  do {
	swapped = false;
	
	for (int i=0;i<n-1;i++) {
	  numComparisons++;

	  if (arr[i] > arr[i+1]) {
		swap(arr,i,i+1);
		swapped = true;
	  }
	}
  }	while (swapped);  
  return numComparisons;
}


string toString(int arr[], int n) 
{
  string s = "{";
  for (int i=0;i<n;i++) {
	if (i != 0) {
	  s += ", ";
	}

	// Convert into to char[]
	char buf[10];  // Buffer to store string result.
	sprintf(buf, "%d",arr[i]); // converts into to char[]

	s += buf;
  }
  s += "}";
  return s;
}

void performSearch(int arr[], int N)
{
  cout << "Original Array   : " << toString(arr, N) << endl;
  
  int numComparisons = bubbleSort(arr,N);
  
  cout << "After bubble Sort: " << toString(arr, N) << endl;
  cout << "Had to perform " << numComparisons << " comparisons" << endl << endl;
}

int main()
{
  cout << endl;

  const int N = 10;
  int arr[N] = {2, 5, 3, 4, 1, 0, 9, 6, 8, 7};
  performSearch(arr,N);

  // Now try for the array {0, 1, ..., 8, 9}
  for (int i=0;i<N;i++) {
	arr[i] = i;
  }
  performSearch(arr,N);

  // Now try for the array {9, 8, ..., 1, 0}
  for (int i=0;i<N;i++) {
	arr[i] = N-i-1;
  }
  performSearch(arr,N);

  return 0;
}