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

#include "stdafx.h"
#include <iostream>

int size = 6;
int *randomArray(int size);
void quickSort(int *array, int l , int r);
int getPivot(int *array, int l, int r);
void exchange(int *array, int l, int r);
int binarySearch(int *array, int size, int value, int *compares);



int main(int argc, char* argv[])
{
	int value = 3166;
	int compares = 0;
	int *reihung = randomArray(size);
	
	for (int i = 0; i< size; i++){
		std::cout << "Unsortiert: " <<reihung[i]<<std::endl;

	}

	

	
	
	quickSort(reihung, 0,size-1);

	for (int i = 0; i< size; i++){
	std::cout << "Sortiert: " <<reihung[i]<<std::endl;
	}
	

	int peter =binarySearch(reihung, size, value, &compares);

	std::cout << peter << " Vergleiche: " << compares << std::endl;


	system("Pause");

	
}

int *randomArray(int size){
	
   
	int* reihung = new int [size];

	int zufall;

	for (int i=0; i < size; i++){

		zufall = (int)((float)rand() / (float)RAND_MAX * 16383.0f);
		reihung[i] = zufall;
	}

	return reihung;

}

void quickSort(int *array,int l, int r){

	int i = l;
	int j = r-1;
	
	if (l >= r){
		return;
	}
	int pivot = getPivot(array, l, r-1);
	std::cout << "Pivot: " << pivot<<" "<<array[pivot]<< std::endl;

	
	exchange(array, pivot, r);

	while (array[i] < array[pivot]){
		i++;
	}
	while (j >= 1 && array[pivot] >= array[r]){
		j--;
	}

	while (i < j){

		exchange(array, i ,j);

		while (array[i] < array[r]){
			i++;
		}
		while (array[j] >= array[r]){
			j--;
		}
					
	}
	exchange(array, i ,r);
    quickSort(array,l, i-1);
	quickSort(array,i+1, r);

	


}


int getPivot(int *array, int l, int r){
				
		int mitte = r/2;

		if ((array[l] <= array[r] && array[l] >= array[mitte]) || (array[l] >= array[r] && array[l] <= array[mitte])){
			return l;
		}
		else if((array[r] <= array[l] && array[r] >= array[mitte]) || (array[r] >= array[l] && array[r] <= array[mitte])){
			return r;
		}
		return mitte;
}

void exchange(int *array, int r, int l){

	int temp = array[r];
	array[r] = array[l];
	array[l] = temp;
	return;
}

int binarySearch(int *array, int size, int value, int *compares){
	
	int mitte = size/2;


	*compares ++;
	if (array [mitte] == value){
		return 1;
	}
	if(size == 0){
		return 0;
	}

	
	*compares ++;
	if (array[mitte] > value){

		size = mitte;
		binarySearch(array, mitte, value, compares);
		
	}
	
	else{
				
		binarySearch(&array[mitte], size - mitte, value, compares);
	}
	


}