/***************************************************************************
 *   Copyright (C) 2006 by Alex Brandt                                     *
 *   alunduil@alunduil.com                                                 *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful.       *
 *   but WITHOUT ANY WARRANTY: without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc..                                       *
 *   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.              *
 ***************************************************************************/

#include <algorithm>

int partition(int a[], int first, int last)
{
	int	pivot = a[first],
		lastS1 = first,
		firstUnknown = first + 1;

	while (firstUnknown <= last)
	{
		if (a[firstUnknown] < pivot)
		{
			lastS1++;
			std::swap(a[firstUnknown], a[lastS1]);
		}
		firstUnknown++;
	}
	std::swap(a[first], a[lastS1]);
	return lastS1;
}

void quicksort(int a[], int first, int last)
{
	if (first < last)
	{
		int	pivotIndex = partition(a, first, last);
		quicksort(a, first, pivotIndex - 1);
		quicksort(a, pivotIndex + 1, last);
	}
	return;
}

void quicksort(int a[], int aSize)
{
	quicksort(a, 0, aSize - 1);
	return;
}

void bubblesort(int a[], int aSize)
{
	while (true)
	{
		bool	swapped = false;
		for (int i = 0, j = i + 1; i < aSize - 1; i++, j++)
		{
			if (a[i] > a[j])
			{
				std::swap(a[i], a[j]);
				swapped = true;
			}
		}
		if (!swapped)
			break;
	}
	return;
}

int newGap(int gap)
{
	gap = (gap * 10)/13;
	if (gap == 9 || gap ==10)
		gap = 11;
	if (gap < 1)
		gap = 1;
	return gap;
}

void combsort(int a[], int aSize)
{
	int	gap = aSize;
	while (true)
	{
		gap = newGap(gap);
		bool swapped = false;
		for (int i = 0; i < aSize - gap; i++)
		{
			int j = i + gap;
			if (a[i] > a[j])
			{
				std::swap(a[i], a[j]);
				swapped = true;
			}
		}
		if (gap == 1 && !swapped)
			break;
	}
}