#include <iostream>

using namespace std;

void Display(int *a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

void Swap(int *x, int *y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void BubbleSort1(int *a, int n)
{
	// Judge.
	if (n < 2)
	{
		return;
	}

	int tmp = 0;

	for (int i = n - 1; i > 0; --i)
	{
		bool isSwap = false;
		for (int j = 0; j < n - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				isSwap = true;
			}
		}
		if (isSwap == false)
		{
			return;
		}
	}
}

void BubbleSort2(int *a, int n)
{
	if (n < 2)
	{
		return;
	}

	bool isSwap = false;

	int tmp = 0;
	for (int j = 0; j < n - 1; ++j)
	{
		if (a[j] > a[j + 1])
		{
			tmp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = tmp;
			isSwap = true;
		}
	}

	if (isSwap == false)
	{
		return;
	}

	BubbleSort2(a, --n);
}

void SelectionSort1(int *a,int n)
{
	if (n < 2)
	{
		return;
	}

	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int minpos = left;
		int maxpos = left;

		for (int i = left + 1; i <= right; ++i)
		{
			if (a[i] < a[minpos])
			{
				minpos = i;
			}
			else if (a[i] > a[maxpos])
			{
				maxpos = i;
			}
		}

		if (minpos != left)
		{
			Swap(&a[minpos], &a[left]);
		}

		if (maxpos == left)
		{
			maxpos = minpos;
		}

		if (maxpos != right)
		{
			Swap(&a[maxpos], &a[right]);
		}

		++left;
		--right;
	}
}

void SelectionSort2(int *a, int n)
{
	if (n < 2)
	{
		return;
	}

	int minpos = 0;
	int maxpos = 0;
	for (int j = 1; j < n; ++j)
	{
		if (a[j] < a[minpos])
		{
			minpos = j;
		}
		else if (a[j] > a[maxpos])
		{
			maxpos = j;
		}
	}

	if (minpos != 0)
	{
		Swap(&a[minpos], &a[0]);
	}

	if (maxpos == 0)
	{
		maxpos = minpos;
	}

	if (maxpos != n - 1)
	{
		Swap(&a[maxpos], &a[n - 1]);
	}

	SelectionSort2(a + 1, n - 2);
}

void InsertionSort(int *a, int n)
{
	if (n < 2)
	{
		return;
	}
	
	for (int i = 1; i < n; ++i)
	{
		int pos = i;
		for (int j = i - 1; j >= 0; --j)
		{
			if (a[j] > a[i])
			{
				pos = j;
			}
		}

		if (pos != i)
		{
			int tmp = a[i];
			for (int j = i - 1; j >= pos; --j)
			{
				a[j + 1] = a[j];
			}
			a[pos] = tmp;
		}

	}
}

int main()
{
	int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	int len = sizeof(arr) / sizeof(int);

	Display(arr, len);

	// BubbleSort1(arr, len);
	// BubbleSort2(arr, len);
	// SelectionSort1(arr, len);
	// SelectionSort2(arr, len);
	InsertionSort(arr, len);

	Display(arr, len);

	return 0;
}