//Natalie Zarate                     CSC5                  Chapter 8, P. 488, #9
#include <iostream>
#include <iomanip>
using namespace std;

//Prototype for BubbleSort
int BubbleSort(int numbers[], int elements);

// Prototype for SelectionSort
int SelectionSort(int numbers[], int elements);

int main() 
{
	int size = 20;
	int array1[size] = {7, 14, 11, 20, 15, 12, 13, 6, 5, 4, 17, 8, 1, 19, 2, 9,
	                3, 10, 14, 16, 18};
	int array2[size] = {7, 14, 11, 20, 15, 12, 13, 6, 5, 4, 17, 8, 1, 19, 2, 9,
	                3, 10, 14, 16, 18};
	int BubbleCount;
	int SelectCount;
	
	//Call BubbleSort
	BubbleCount = BubbleSort(array1, size);
	
	//Call SelectionSort
	SelectCount = SelectionSort(array2, size);
	
	cout << BubbleCount << endl;
	
	for (int i = 0; i < size; i++)
	{
		cout << array1[i] << " ";
	}
	
	cout << "\n" << SelectCount << endl;
	
	for (int i = 0; i < size; i++)
	{
		cout << array2[i] << " ";
	}
	return 0;
}
/******************************************************************************/
int BubbleSort(int numbers[], int elements)
{
	bool swap;
	int hold;
	int swapCount = 0;
	
	do
	{
		// intialize flag
		swap = false;
		
		//search elements
		for (int i = 0; i < (elements - 1); i++)
		{
			if(numbers[i] > numbers[i+1])
			{
				hold = numbers[i];
				numbers[i] = numbers[i+1];
				numbers[i+1] = hold;
				swap = true; 
				
				//increment swap counter
				swapCount++;
			}
		}
	}
	// while false 
	while (swap);
	
return swapCount;
}	
/******************************************************************************/
int SelectionSort(int numbers[], int elements)
{
	int start;
	int minIndex;
	int minValue;
	int sortCount;
	
	for(start = 0; start < (elements-1); start++)
	{
		minIndex = start;
		minValue = numbers[start];
		
		for(int i = start + 1; i < elements; i++)
		{
			if (numbers[i] < minValue)
			{
				minValue = numbers[i];
				minIndex = i;

			}
		}
		numbers[minIndex] = numbers[start];
		numbers[start] = minValue;
		
		sortCount++;
	}
return sortCount;
}