// QuickSort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

int* quicksort(int *Array);

int _tmain(int argc, _TCHAR* argv[])
{
	int  Start[500]  = {0};
	bool Random[500] = {0};
	int  *Final      = new int(500);
	int  Counted     = 0;
	int  Rand;

	srand(time(NULL));

	for (int i = 0; i < 500; i ++)
	{
		Start[i] = i;
		Final[i] = 0;
	}

	while (Counted++ < 500)
	{
		Rand = rand() % 500;

		while (Random[Rand] == true)
		{
			if (++Rand > 499)
			{
				Rand = 0;
			}
		}

		Random[Rand] = true;

		Final[Counted] = Start[Rand];
	}

	Final = quicksort(Final);

	for (int i = 0; i < 500; i ++)
	{
		cout << Final[i] << "\n";
	}

	system("PAUSE");

	return 0;
}


int* quicksort(int *Array)
{
	int Size = sizeof Array / sizeof Array[0];

	if (Size > 1)
	{
		int *Upper = new int[Size];
		int Upct = 0;
		int *Lower = new int[Size];
		int Lwct = 0;

		int PivotLocation = rand() % Size;

		int Pivot = Array[PivotLocation];

		for (int i = 0; i < Size; i ++)
		{
			int Current = Array[i];

			if (Current >= Pivot)
			{
				Upper[Upct++] = Current;
			}
			else if (Current < Pivot)
			{
				Lower[Lwct++] = Current;
			}
		}

		int *RUpper = new int[Upct];
		int *RLower = new int[Lwct];

		for (int i = 0; i < Upct; i ++)
		{
			RUpper[i] = Upper[i];
		}

		for (int i = 0; i < Lwct; i ++)
		{
			RLower[i] = Lower[i];
		}

		RUpper = quicksort(RUpper);
		RLower = quicksort(RLower);

		int *Final = new int[Size];

		for (int i = 0; i < Lwct; i ++)
		{
			Final[i] = RLower[i];
		}

		for (int i = Lwct; i < Upct; i ++)
		{
			Final[i] = RUpper[i];
		}

		delete[] Upper;
		delete[] RUpper;
		delete[] Lower;
		delete[] RLower;

		return Final;
	}
	else
	{
		return Array;
	}
}