//
// demonstrates a bubble sort
// Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary.
//

#include <stdlib.h>
#include <time.h>

#include <iostream>
using namespace std; 

const int numElements = 128; // number of elements to sort


//
// "In a bubble sort, several left-to-right passes are made over the array
// of records to be sorted.  In each pass, pairs of adjacent records are compared and
// exchanged if necessary.  The sort terminates following a pass in which no records 
// are exchanged." (p. 444)
//		E. Horowitz, et al.  Fundamentals of Data Structures in C++.
//		Computer Science Press, New York, 1995.
//
// This routine sorts an array of integers in ascending order.
//
void bubbleSort (int array[], int elementCount)
{
	bool swappedElements = true;
	while (swappedElements)
	{
		swappedElements = false; // set flag to false
		for (int i = 0;  i < (elementCount-1);  i ++) // elementCount-1 because we are comparing [i] with [i+1]
		{
			if (array[i+1] < array[i])
			{	// element to the right is less than current element, so swap
				int temp = array[i];
				array[i] = array[i+1];
				array[i+1] = temp;
				swappedElements = true; // signal that we performed a swap
			}
		}
	}
}


//
// program entry
//
int main()
{
	int i = 0;

	// seed the random number generator
	srand((unsigned int)time(0));

	// create an array of random integers
	int array[numElements];
	for (i = 0;  i < numElements;  i = i + 1)
	{
		array[i] = rand() % numElements; // keep numbers in the range of 0-numElements
	}

	// sort the array
	bubbleSort (array, numElements);

	// print the array
	for (i = 0;  i < numElements;  i = i + 1)
	{
		cout << array[i] << ' ';
	}
	cout << endl;

	return 0;
}