//-------------------------
//HELPER FUNCTIONS

void swap(int &x, int &y)
{
	int temp;
	temp=x;
	x=y;
	y=temp;
}

static void sift(int a[], int k, int n)
{
	int i=k, j;
	int x=a[i];
	while((j=2*i+1)<n)
	{
		if(j<n-1 && a[j]<a[j+1]) j++;
		if(x>=a[j]) break;
		a[i]=a[j]; i=j;
	}
	a[i]=x;
}

//-------------------------
//BUBBLE SORT

void bubbleSort(int a[], int n)
{
	for(int i=0; i<n-1; i++)
	{
		for(int j=0; j<n-i-1; j++)
		{
			if(a[j] > a[j+1]) swap(a[j],a[j+1]);
		}
	}
}

//-------------------------
//SELECTION SORT

void selectionSort(int a[], int n)
{
	int loc,minIndex,min;
	for(int i=0; i<n-1; i++)
	{
		min=a[i];
		for(loc=i+1; loc<n; loc++)
		{
			if(a[loc]<min) {minIndex=loc; min=a[loc];}
		}
		swap(a[i],a[minIndex]);
	}
}

//-------------------------
//INSERTION SORT

void insertionSort(int a[], int n)
{
	int first,temp,loc;
	for(first=1; first<n; first++)
	{
		if(a[first]<a[first-1])
		{
			temp=a[first];
			loc=first;
			do
			{
				a[loc]=a[loc-1];
				loc--;
			}while (loc>0 && a[loc-1]>temp);
			a[loc]=temp;
		}
	}
}

//-------------------------
//HEAP SORT

void heapSort(int a[], int n)
{
	for(int k=n/2-1; k>=0; k--) sift(a, k, n);
	while(--n>0)
	{
		swap(a[0],a[n]);
		sift(a,0,n);
	}
}

//-------------------------
//QUICK SORT

void quickSort(int a[], int n)
{
	int i=0, j=n-1;
	int temp=a[j/2];
	do
	{
		while(a[i]<temp) i++;
		while(a[j]>temp) j--;
		if(i<j) swap(a[i],a[j]);
		else
		{
			if(i==j) {i++; j--}
			break;
		}
	}while(++i<=--j);
	if(j>0) quickSort(a,j+1);
	if(i<n-1) quickSort(a+i,n-i);
}