#include <iostream>
#include <iomanip>

using namespace std;

// Delcaration

void QuickSort(double A[], int s, int t);
int Partitionierung(double A[], int s, int t);
void Zeige(double A[],double B[], int anz);
void Tausche(double& a, double& b);

// Implementation

void Zeige(double A[],double B[],int anz)
{
	cout << setw(5) << "#" << setw(20) << "Unsortiert" << setw(20) << "Sortiert" << endl;
	for(int i=0;i<anz;i++)
	{
		cout << setw(5) << i << setw(20) << A[i] << setw(20) << B[i] << endl;
	}
}

void QuickSort(double A[], int s, int t)
{
	if((t-s) >= 1)
	{
		int grenze = Partitionierung(A,s,t);
		//cout << "Partitionierung " << s << " bis "<<t << " Ergebnis: " << grenze<< endl;
		QuickSort(A,s,grenze-1);
		QuickSort(A,grenze+1,t);
	}
}

int Partitionierung(double A[], int s, int t)
{
	int l=s;
	double pivot = A[s];
	for(int i = s+1; i<= t;i++)
	{
		if(A[i] < pivot)
		{
			l++;
			Tausche(A[l], A[i]);
		}
	}
	Tausche(A[l],A[s]);
	return(l);
}

void Tausche(double& a, double& b)
{
	double temp;
	temp = a;
	a = b;
	b = temp;
}

int main()
{
	// Zufallsgenerator initialisieren
	srand((unsigned int)time(0));
	
	// Feld initialisieren
	const int anz = 100;
	double A[anz];
	double B[anz];
	for(int i=0; i < anz;i++)
	{
		A[i] = double(rand())/RAND_MAX*100.0 ;
		B[i] = A[i];
	}
	
	QuickSort(B,0,anz-1);
	Zeige(A,B,anz);
	return(0);
}