// Programmieren 1, Praktikum 4, Aufgabe 2
// Sven Eisenhauer
// 08.12.2004
//
// file: main.cpp
//
// purpose: Implementation of Selection Sort and Insertion Sort algorithm
//

#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setprecision;
using std::setw;

// contains function prototypes for functions srand and rand
#include <cstdlib>

#include <ctime>

void selectionSort(int[], int);
void insertionSort(int[], int);

int main ()
{
	const int arraySize=5;
	int array1[arraySize],array2[arraySize];

    srand(time(0));

	// fill the arrays with some random stuff
    for (int i=0;i<arraySize;i++)
	{
		array1[i]=rand()%1000;
		array2[i]=array1[i];
	}

	// shown the unsorted random array
	cout << "Unsorted Array:" << endl;
    for (i=0;i<arraySize;i++)
	{
		cout << setw(5) << array1[i];
	}
	cout << endl;
	
	// selectionSort
	selectionSort(array1,arraySize);

	cout << "Selection sorted Array:" << endl;
    for (i=0;i<arraySize;i++)
	{
		cout << setw(5) << array1[i];
	}
	cout << endl;

	// insertionSort
    insertionSort(array2,arraySize);

	cout << "Insertion sorted Array:" << endl;
    for (i=0;i<arraySize;i++)
	{
		cout << setw(5) << array2[i];
	}
	cout << endl;

	return 0;
}

void selectionSort(int a[],int aSize)
{
	int hold;

	for (int i=0;i<aSize;i++)
	{	
		// start from actual position...
		for (int j=i;j<aSize;j++)
		{   
			// ... search the minimum...
			if(a[j]<a[i])
			{
				//... and insert it
				hold=a[i];
				a[i]=a[j];
				a[j]=hold;
			}
		}
	}
} // end function selectionSort

void insertionSort(int a[],int aSize)
{
	int temp,i;

	for (int n=1;n<aSize;n++)
	{
		// only if we have a wrong order
		if (a[n]<a[n-1])
		{
			// save the value, we want to insert
			temp=a[n];
			// we need a second variable
			i=n-1;
			// shift all values up till we are at the right place
			// while the value, which is to be inserted, is smaller than
			// actual array value
			while (temp < a[i] && (i>= 0))
			{
				// always copy the value from the array field before
				// so the gap "walks" to the left, until a[i] is at the right place
				// and we can put temp in it.
				a[i+1]=a[i];
				i--;
			}
			// i+1 to compensate the last i--, because we want a[i] before the last i--
			a[i+1]=temp;
		}

	}
} // end function insertionSort