/***************************************************************************/
// PLEASE REPORT ANY ERRORS OR OMISSIONS IN THIS CODE TO:
// adawson@coquitlamcollege.com
// Last updated:  Sunday 9th March, 2003 A.H.D.
// bubblesort.cpp
// http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BSort.html

/***************************************************************************/
/*

The bubblesort algorithm sorts elements by comparing neighbours, and if they
are out of order, swaps them. After the first pass of the sequence, the
highest valued element is in position.  After the second pass, the last two
elements are in position. The sequence is sorted by completing n such passes.
Because at each pass (i) , one element is in the correct position (sorted), then
each subsequent pass need only process n - i + 1 elements of the sequence.
That is, the running time of the ith pass is n - i + 1, and the overall running
time is big O of the summation: (for every i from i = 1 to i = n) n - i + 1

  n
  _
 \
 /  (n - i + 1)
 -

 i = 1


This can be rewritten as:

O(n + (n-1) +  (n-2) + (n-3) ... + 2 + 1)


which is Big O of


  n
  _
 \
 /  i         or  (n(n+1))/2   i.e. n^2 + n/2    which is O(n^2)
 -

 i = 1


 Hence the bubblesort is a quadratic sort - too slow for large values of n

 The bubble sort has a nested for loop with limits of n, and hence O(n^2) is
 a good estimate.

 Other quadratic sorts are the selection sort and the insertion sort.

*/


#include <iostream.h>
#include <conio.h>

void bubblesort( int x[ ], int size );
void swap(int & x1, int & x2);
void display(int x[ ], int size );

/***************************************************************************/

int main( )
{
	 const int SIZE =6;
	 cout << "Bubblesort Demo\n\n";
	 int array[SIZE] = {5,7,2,6,9,3};

    cout << "Original array:\n\n";
    display(array,SIZE);
    cout << "\n\nStarting the sort: \n\n";
    bubblesort(array, SIZE);
    cout << "Press any key to end this program";
    getch();

}

/***************************************************************************/

void bubblesort(int x[], int size)
{
  int n = size;
  for (int i = 0; i < n; i++)
  {
      for (int j = 1; j < n-i; j++ )
         if( x[j-1] > x[j] )
            swap(x[j-1], x[j]);
      display(x, size);
      cout << endl;
  }
}

/***************************************************************************/

void swap(int & x1, int & x2)
{
    int temp;
    temp = x1;
    x1 = x2;
    x2 = temp;
}

/***************************************************************************/

void display(int x[ ], int size )
{
  int i;
  for( i = 0; i < size; i++ )
     cout << x[i] << ' ';
  cout << endl;
}

/***************************************************************************/