/*
 * sorting.cpp
 *
 *  Created on: 23.01.2013
 *      Author: trifon
 */

#include <iostream>

static int swapCount;

template <typename T>
void swap(T& x, T& y)
{
	T tmp = x;
	x = y;
	y = tmp;
	swapCount++;
}

template <typename T>
void selectSort(T a[], int n)
{
	for(int i = 0; i < n - 1; i++)
	{
		// сортираната част е от 0 до i-1 включително
		int min = i;
		for(int j = i + 1; j < n; j++)
			if (a[j] < a[min])
				min = j;
		swap(a[i],a[min]);
		// сортираната част е от 0 до i включително
	}
}

template <typename T>
void bubbleSort(T a[], int n)
{
	for(int i = 0; i < n - 1; i++)
	{
		// сортираната част е от 0 до i-1 включително
		for(int j = n - 1; j > i; j--)
			if (a[j-1] > a[j])
				swap(a[j-1], a[j]);
		// сортираната част е от 0 до i включително
	}
}

template <typename T>
void shakeSort(T a[], int n)
{
	int left = 0, right = n - 1;
	// лявата сортирана част е от 0 до left - 1
	// дясната сортирана част е от right + 1 до n - 1
	while (left < right)
	{
		int k = right;
		for(int j = right; j > left; j--)
			if (a[j-1] > a[j])
			{
				swap(a[j-1], a[j]);
				k = j;
			}
		left = k;

		k = left;
		for(int j = left; j < right; j++)
			if (a[j] > a[j+1])
			{
				swap(a[j], a[j+1]);
				k = j;
			}
		right = k;
	}
}

template <typename T>
void insertSort(T a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		// сортираната част е от 0 до i-1
		T x = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > x)
		{
			a[j+1] = a[j];
			j--;
		}
		// j е мястото на x
		a[j + 1] = x;
		// сортираната част е от 0 до i
	}
}

template <typename T>
void shellSort(T a[], int n)
{
	int h = 0;
	while (h < n)
		h = 3*h + 1;
	h /= 3;
	// намерихме началната стъпка
	while (h > 0)
	{
		for(int i = h; i < n; i++)
		{
			T x = a[i];
			int j = i - h;
			while (j >= 0 && a[j] > x)
			{
				a[j+h] = a[j];
				j -= h;
			}
			a[j+h] = x;
		}
		h /= 3;
	}
}

template <typename T>
void quickSort(T a[], int n)
{
	if (n <= 1)
		return;
	int x = a[n/2];
	int left = 0, right = n - 1;
	while (left <= right)
	{
		while (a[left] < x) left++;
		while (a[right] > x) right--;
		// a[left] >= x, a[right] <= x
		if (left <= right)
		{
			if (left < right)
				swap(a[left], a[right]);
			left++;
			right--;
		}
	}
	// left > right
	// за всяко i от 0 до right вкл. a[i] <= x
	// за всяко i от left вкл. до n-1 a[i] >= x

	quickSort(a, right + 1);
	quickSort(a + left, n - left);
}