#include <iostream>
using namespace std;

void ausgabe(int sortArr[], int length, int matrix[][4], int zweidimensional = 0){

	if (zweidimensional) {
		for (int i = 0; i < length; i++)
		{
			for (int j = 0; j < zweidimensional; j++)
			{
				cout << matrix[i][j] << ' ';
			}
			cout << endl;
		}
	}
	else {
		for (int i = 0; i < length; i++)
		{
			cout << sortArr[i] << ' ';
		}
		cout << endl;
	}
}

int getMinIndex(int sortArr[], int length, int start){
	int temp = start;

	for (int i = start; i < length; i++) {
		if (sortArr[temp] >= sortArr[i]) {
			temp = i;
		}
	}

	return temp;
}

void auswahlSort(int sortArr[], int length){
	for (int i = 0; i < length; i++)
	{
		int temp = sortArr[i];
		sortArr[i] = sortArr[getMinIndex(sortArr, length, i)];
		sortArr[getMinIndex(sortArr, length, i)] = temp;
	//	cout << sortArr[i] << ' ';
	}
}

void tauschen(int sortArr[], int index){
	int temp = sortArr[index];
	sortArr[index] = sortArr[index + 1];
	sortArr[index + 1] = temp;
}

void bubbleSort(int sortArr[], int length){
	bool status = false;
	for (int i = 0; i < length; i++)
	{
		if (sortArr[i + 1] > sortArr[i])
		{
			tauschen(sortArr, i);
			status = true;
		}

		if (status)
		{
			bubbleSort(sortArr, length);
		}
	}
}

void matrixSort(int matrix[][4], const int x, const int y, int type) {
	int temp[16];
	int index = 0;
	for (int i = 0; i < x; i++)
	{
		for (int j = 0; j < y; j++)
		{
			temp[index++] = matrix[i][j];
		}
	}

	bubbleSort(temp, y * x);
	//ausgabe(temp, y*x, matrix);

	if (type != 3) {
		for (int i = 0; i < x; i++)
		{
			for (int j = 0; j < y; j++)
			{
				if (type == 1){
					matrix[j][i] = temp[--index];
				}
				else if (type == 2) {
					matrix[i][j] = temp[--index];
				}
			}
		}
	}
	else
	{
		for (int i = 0; i > x; i++)
		{
			int n = 4;
			for (int j = 0; j < n; j++)
			{
				matrix[i + n][j] = temp[--index];
				n--;

			}


		}
	}
}

int getNext(int feld[], int length){

	for (int i = 0;  i < length;  i++)
	{
		if (feld[i] > feld[length])
		{
			return i;
		}
	}
	return -1;
}

int getNext2(int feld[], int start, int length){

	for (int i = start; i > length; i--)
	{
		if (feld[i] < feld[length])
		{
			return i;
		}
	}
	return -1;
}
void tauschen(int feld[], int i, int j){
	int temp = feld[i];
	feld[i] = feld[j];
	feld[j] = temp;
}

bool test(int feld[], int anfang, int ende){
	for (size_t i = anfang + 1; i < ende; i++)
	{
		int temp = feld[anfang];
		if (feld[i] < temp)
		{
			return false;
		}
		else {
			temp = feld[i];
		}
	}
	return true;
}

void quicksort(int feld[], int anfang, int ende) {

	int pivotelement = ((ende - anfang) / 2) + anfang;
	int tempI = -1, tempJ = -1;
	int j = ende;

	for (int i = anfang; i < pivotelement; i++)
	{
		tempI = getNext(feld, pivotelement);
		tempJ = getNext2(feld, ende, pivotelement);
//		cout << feld[tempI] << ' ' << feld[tempJ] << endl;

		if (tempI == -1 && tempJ == -1)
		{
			quicksort(feld, anfang, pivotelement - 1);
			quicksort(feld, pivotelement + 1, ende);
		}

		if (tempI != -1 && tempJ != -1)
		{
			tauschen(feld,tempI, tempJ);

		}
		else if (tempI != -1 && tempJ == -1)
		{
			tauschen(feld, tempI, pivotelement);
		}
		else if (tempJ != -1 && tempI == -1)
		{
			tauschen(feld, tempJ, pivotelement);
		}
		j--;





	}
}

int main(){

	const int COUNT = 13;
	const int X = 4;
	const int Y = 4;

	int sortArr[COUNT] = { 3, 68, 7, 34, 35, 13, 16, 36, 99, 7, 6, 6, 4 };
	int feld[COUNT] = { 2, 5, 88, 8, 3, 19, 17, -4, 22, 105, 33, 1, 2001 };
	int matrix[4][4] = { 54, 80, 11, 91, 17, 23, 58, 28, 14, 56, 78, 34, 32, 26, 89, 78 };

	//auswahlSort(sortArr, COUNT);
	//bubbleSort(sortArr, COUNT);
	//ausgabe(sortArr, COUNT, matrix);
	//matrixSort(matrix, X, Y, 1);
	//matrixSort(matrix, X, Y, 2);
	//matrixSort(matrix, X, Y, 3);
	//ausgabe(sortArr, X, matrix, Y);

	quicksort(feld, 0, 12);
	ausgabe(feld, COUNT, matrix);

	return 0;
}