#include "algorithm.h"


int worst_sorterad(int *a, int n){


	int i, j;

	int sorterad = 1;

	for (i = 0;i < n - 1; ++i) {

			for (j = i + 1; j < n; ++j) {
					if (a[i] < a[j]) {


							sorterad = 0;
					}

			}
	}

	if(sorterad == 1){
		return 1;
	}
	else{
		return 0;
	}
}

int best_sorterad(int *a, int n){


	int i, j;

	int sorterad = 1;

	for (i = 0;i < n - 1; ++i) {

			for (j = i + 1; j < n; ++j) {
					if (a[i] > a[j]) {


							sorterad = 0;
					}

			}
	}

	if(sorterad == 1){
		return 1;
	}
	else{
		return 0;
	}
}


void bubble_sort(int *a, int n)
{
    int i, j;
    int flagga = 0;

    for (i = 0; !flagga && i < n - 1; ++i) {
        flagga = 1;
        for (j = i + 1; j < n; ++j) {
            if (a[i] > a[j]) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
                flagga = 0;
            }

        }
    }
}



void insertion_sort(int *a, int n) {

int i,j,key;
for(j=2;j<n;j++){
	key = a[j];
	i = j - 1;

while(i >= 0 && a[i] > key){
	a[i + 1] = a[i];
	i = i - 1;
}
	a[i + 1] = key;
}
}




void quick_sort_best(int *a, int n){
	if (n < 2)
			return;

	int pivot = a[n/2];
	int *left = a;
	int *right = a + n - 1;
	while (left <= right) {
			if (*left < pivot) {
					left++;
			}
			else if (*right > pivot) {
					right--;
			}
			else {
					int temp = *left;
					*left = *right;
					*right = temp;
					left++;
					right--;
			}
	}
 quick_sort_best(a, right - a + 1);
 quick_sort_best(left, a + n - left);


}

void quick_sort_worst(int *a, int n){

	if (n < 2)
			return;



	int pivot = a[n - 1];
	int *left = a;
	int *right = a + n - 1;
	while (left <= right) {
			if (*left < pivot) {
					left++;
			}
			else if (*right > pivot) {
					right--;
			}
			else {
					int temp = *left;
					*left = *right;
					*right = temp;
					left++;
					right--;
			}
	}
 quick_sort_worst(a, right - a + 1);
 quick_sort_worst(left, a + n - left);


}

void quick_sort_average(int *a, int n){

	if (n < 2)
			return;



	int pivot = a[n/2];
	int *left = a;
	int *right = a + n - 1;
	while (left <= right) {
			if (*left < pivot) {
					left++;
			}
			else if (*right > pivot) {
					right--;
			}
			else {
					int temp = *left;
					*left = *right;
					*right = temp;
					left++;
					right--;
			}
	}
 quick_sort_average(a, right - a + 1);
 quick_sort_average(left, a + n - left);


}


void quick_sort(int *a, int n)
{

if(worst_sorterad(a,n) == 1)
{
	quick_sort_worst(a, n);
}
else if(best_sorterad(a,n) == 1){
	quick_sort_best(a, n);
}
else
{
	quick_sort_average(a,n);
}
   //  if (n < 2)
   //      return;
	 //
   //  int pivot = a[n - 1];
   //  int *left = a;
   //  int *right = a + n - 1;
   //  while (left <= right) {
   //      if (*left < pivot) {
   //          left++;
   //      }
   //      else if (*right > pivot) {
   //          right--;
   //      }
   //      else {
   //          int temp = *left;
   //          *left = *right;
   //          *right = temp;
   //          left++;
   //          right--;
   //      }
   //  }
   // quick_sort(a, right - a + 1);
   // quick_sort(left, a + n - left);

}


bool linear_search(const int *a, int n, int v)
{
	int i;
	for(i = 0;i < n;i++){
		if(a[i] == v)
		return true;
	}
return false;
}

bool binary_search(const int *a, int n, int v){


	int low = 0;
	int high = n - 1;
	int mid;
	int found = 0;
	while (low <= high  && !found)
	{
		mid = ( high - low ) / 2;
		if(a[mid] == v){
			found = 1;
		}
		else if( a[mid] > v){
			high = mid - 1;

		}else{
			low = mid + 1;

		}
		if(found == 1){
		return true;
		}else{
		return false;
		}


	}
	return false;
}