//
//Author:  SUZUKI, RICARDO

// Quick sort program
// last update on Friday, April 25

#include<iostream>
#include<cstdlib>
#include<fstream>
#include<iomanip>

using namespace std;

int Many_int();
//PRECONDITION: there must be a .txt file with int
//POSTCONDITIN: returns the amount of int in the file

void fill_up_array(int array[]);
//PRECONDITION: receives an array
//POSTCONDITIN: fill it up with the numbers from
//			the .txt file

void Quick_Sort(int array[], int, int);
//PRECONDITION: receives the array and its size
//POSTCONDITIN: sorts the array

void Print(int array[], int size);
//PRECONDITION: receives an array and its size
//POSTCONDITIN: prints the array to a file

void main()
{
	int dummy=0;
	int	many_numbers = Many_int();
	
	int *array_to_quick;
	array_to_quick = new int[many_numbers];
	
	fill_up_array(array_to_quick);
			
	// call the sort function
	Quick_Sort(array_to_quick, 0,many_numbers-1);
	
	Print(array_to_quick, many_numbers);

}

void Print(int array[], int size)
{
	ofstream outfile;
	outfile.open("output.txt");

	outfile<<"********* Quick Sort *********** "<<endl;
	for( int i=0; i< size ; i++)
	{
		outfile<< setw(10)<<array[i]<<endl;
	}
	
}

//*************** Q U I C K  S O R T*****************
void Quick_Sort(int numbers[], int left, int right)
{
	int pivot, l_hold, r_hold;
	
	l_hold = left;
	r_hold = right;
	pivot = numbers[left];
	while (left < right)
	{
		while ((numbers[right] >= pivot) && (left < right))
			right--;
		if (left != right)
		{
			numbers[left] = numbers[right];
			left++;
		}
		while ((numbers[left] <= pivot) && (left < right))
			left++;
		if (left != right)
		{
			numbers[right] = numbers[left];
			right--;
		}
	}
	numbers[left] = pivot;
	pivot = left;
	left = l_hold;
	right = r_hold;
	if (left < pivot)
		Quick_Sort(numbers, left, pivot-1);
	if (right > pivot)
		Quick_Sort(numbers, pivot+1, right);
}

// get integers from file and put in array
void fill_up_array(int array[])
{
	int dummy;
	int i=0;
	ifstream fill_array;
	fill_array.open("input.txt");
	
	while(!fill_array.eof())
	{	fill_array>>dummy;
	array[i] = dummy;
	i++;
	}
	
	fill_array.close();	
}

// counts how many numbers in the file
int Many_int()
{
	ifstream count_file;
	count_file.open("input.txt");
	if(!count_file)
	{
		cout<<"There is no file to read"<<endl;
		return EXIT_FAILURE;
	}
	
	int many_numbers=0;
	int dummy;
	
	while(!count_file.eof())
	{
		count_file>>dummy;
		many_numbers++;	
	}
	--many_numbers;
	count_file.close();
	return many_numbers;
}