// Programmieren 1, Praktikum 5, Aufgabe 2
// Sven Eisenhauer
// 16.12.2004
//
// file: main.cpp
//
// purpose: QuickSort algorithm
//

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

#include <iomanip>

using std::setprecision;
using std::setw;

// contains function prototypes for functions srand and rand
#include <cstdlib>

#include <ctime> 

// constant definitions
const int arraySize=100;         // number of array elements
const int maxNum=1000;           // max. Number in Array plus 1
const int arrayStart=0;          // first array element
const int arrayEnd=arraySize-1;  // last array element

// function prototypes
void quickSort(int [],int,int);
int partition(int [], int,int,int&);
void swapRight(int [], int &,int &, int &, int &, int &);
void swapLeft(int [], int&,int &, int&, int &, int &);

int main()
{
	int array[arraySize];

	// initialize random number generator
	srand(time(0));

	// generate array with random content
	for (int i=0;i<arraySize;i++) {
		array[i]=rand()%maxNum;
	}

	// show it unsorted
	cout << "Unsorted:" << endl;
	for (i=0;i<arraySize;i++) {
		cout << setw(4) << array[i];
	}
	cout << endl;

	// sort it
	quickSort(array,arrayStart,arrayEnd);

	// show it sorted
	cout << "Sorted:" << endl;
	for (i=0;i<arraySize;i++) {
		cout << setw(4) << array[i];
	}
	cout << endl;
	// habe fertisch
	return 0;
}// end function main

void quickSort(int toSort[], int start, int end)
{
	int pos;
	// partition the array and get pos, where array is divided
	partition(toSort,start,end,pos);
	if (pos > start)
		// now sort lower part
		quickSort(toSort,start,pos-1);
	if (pos < end)
		// and higher part
		quickSort(toSort,pos+1,end);
}// end function quicksort

int partition(int array[],int start, int end, int &pos)
{
	int loop=0;
	int foundL,foundR;
	int newStart=start;
	int newEnd=end;
	int nextStart=start;
    
	pos=start;

	do {
		foundR=0;
		foundL=0;
		// decide whether to search from left or right
		// 0: right, 1: left
		if (0==(loop%2)) {
			swapRight(array,newEnd,newStart,nextStart,pos,foundR);
			// set newStart for the next call of a swap fct.
			newStart=nextStart;
			/*cout << endl << " right "<< loop << " "<< endl;
			for (int j=0;j<=end;j++)
				cout << setw(4) << array[j];		
			cout << endl;*/
		}
		else {
			swapLeft(array,newEnd,newStart,nextStart,pos,foundL);
			// set newStart for the next call of a swap fct.
			newStart=nextStart;
			/*cout << endl << " left "<< loop << " "<< endl;
			for (int j=0;j<=end;j++)
				cout << setw(4) << array[j];		
			cout << endl;*/
		}
		loop++;
	} while (((1==foundL)||(1==foundR)));

	return 0;
}// end function partition

void swapRight(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
{
	int i,temp;
	// here we start to walk through array, from RIGHT!!!
	i=end;
	// newStart is the beginning of the area to check of the array
	// when newStart==pos (which is the position of we element, which we order at the moment)
	// this means: we are done here!
	while((i>=newStart)&&(i!=pos)) {
		// if we have found a smaller value, when searching from right
		if (arr[i]<=arr[pos]) {
			// swap the values
			temp=arr[i];
			arr[i]=arr[pos];
			arr[pos]=temp;
			// now set the next Start of search from left to one field right of
			// the element, we currently searched and swapped
			nextStart=newStart+1;
			// in i is the actual position of the element which should be ordered
			// we should not forget this and tell this the place, from where we were called
			pos=i;
			// YES!!! we found a smaller value by searching from right
			found=1;
			break;
		}
		i--;
	}
}// end function swapRight

void swapLeft(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
{
	int i,temp;
	// here we start to walk through array, from LEFT!!!
	i=newStart;
	// newStart is the beginning of the area to check of the array
	// when newStart==pos (which is the position of we element, which we order at the moment)
	// this means: we are done here!
	while((i<=end)&&(i!=pos)) {
		// if we have found a bigger value, when searching from left
		if (arr[i]>arr[pos]) {
			// swap the values
			temp=arr[i];
			arr[i]=arr[pos];
			arr[pos]=temp;
			// now set the next Start of search from right to one field left of
			// the element, we currently searched and swapped
			nextStart=newStart-1;
			// in i is the actual position of the element which should be ordered
			// we should not forget this and tell this the place, from where we were called
			pos=i;
			// YES!!! we found a smaller value by searching from right
			found=1;
			break;
		}
		i++;
	}
}// end function swapLeft