#include<iostream>
#include<stdio.h>
using namespace std;

int bubbleSort(int *array,int n);
void printElements(int *array,int n);
int swap(int &x, int &y);
void heapify(int a[], int lower, int upper);
int heapsort(int a[], int numelts);
int quicksort(int a[], int numelts);
int partition(int a[],int lower, int upper);

int main()
{
    //int a[]={9,6,5,23,2,6,2,7,1,8,99,98};                   // BUBBBLE SORT
    //int b[]={7,10,5,209,7,8,-2,0,100,45,9,5,2,10,6};        // HEAP SORT
    //int c[] = {3,8,-9,56,10,8,22,7,100,45,-9,5,-2,10,6};    // QUICK SORT
    int a[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
    int b[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
    int c[]={0,2,5,3,6,8,1,21,23,22,32,54,57,59,61,67,69,89,90,101,100,60,167,180,199,198,254,280,299,0};//30 elements
	int n =30;
	int main_count=0;
	int count=0;
    
    
    cout<<"*******BUBBLE SORT**************"<<endl<<endl;
	cout<<"Original Array: "<<endl;
	printElements(a,n);
    cout<<endl<<endl;
    cout<<"Sorted Array: "<<endl; 
    main_count = bubbleSort(a,n);                 //call to bubble sort  
	printElements(a,n);
    cout<<endl;
    cout<<"Number of comparisons: "<<main_count<<endl;  
    cout<<endl<<endl;

    
    cout<<"*******HEAP SORT**************"<<endl<<endl;
    cout<<"Original Array: "<<endl;
	printElements(b,n);
    cout<<endl<<endl;
    cout<<"Sorted Array: "<<endl; 
    main_count = heapsort(b,n);                //call to heap sort  
	printElements(b,n); 
	cout<<endl;
    cout<<"Number of comparisons: "<<main_count<<endl;
    cout<<endl<<endl;



    cout<<"*******QUICK SORT**************"<<endl<<endl;
	cout<<"Original Array: "<<endl;
	printElements(c,n);
    cout<<endl<<endl;
    cout<<"Sorted Array: "<<endl; 
    main_count = quicksort(c,n);                //call to heap sort  
	printElements(c,n);
    cout<<endl;
    cout<<"Number of comparisons: "<<main_count<<endl; 
    cout<<endl<<endl;
	
    
    
    system("pause");
	return 0;
}
/***************************************************************************************************************
 ***************************************************************************************************************
 ***********************************************END OF MAIN()***************************************************
 ***************************************************************************************************************
 ***************************************************************************************************************/



/*This function will print the elements of the
  arrays which were sorted by different sorting
  methods. It will receive an array and # of 
  elemnents as a parameter.
*/
void printElements(int *array,int n) //print array elements
{
	int i=0;
	for(i=0;i<n;i++)
		cout<<array[i]<<" ";
		cout<<endl;
}





/*BUBBLE SORT
  This sorting algorithm is considered inefficient or 
  stupid, because if given data in reverse order, it
  will do a horrible job. It will make n^2(O(n^2)) comparisons.
  Bubble Sort works by comparing two adjacent items,
  and moves them if there is a need. Bubble Sort will
  work best on almost sorted order. It will have about n-1
  comparisons. This function will receive an array and a # of
  elements to process, as a parameter. This function will only return 
  count of comparisons made.
*/
int bubbleSort(int *array,int n)//Bubble sort function 
{
	int i,j;
	int count=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
            count++;//count # of comparisons
			
            if(array[i]<array[j])
			{                 
				int temp=array[i]; //swap 
				array[i]=array[j];
				array[j]=temp;
			}

		}

	}
  return count;
}






/*This function will be used by both HEAP SORT and
  QUICK SORT. It will be used for interchenging
  items when required by algorithm. It will receive 
  two reference parameters x and y, and will not 
  return an answer.
*/
int swap(int &x, int &y)
{
     int temp;

	temp = x;
	x = y;
	y = temp;
	

	return count;
}



/*This function will be used by HEAP SORT algorithm.
  It will be used keep the tree that is being sorted
  balanced - that is the major advantage of max heap
  over other sorts. It will receive an array to be sorted,
  and two integers lower and upper. This function will be
  called by heapsort().
*/
void heapify(int a[], int lower, int upper)
{
	int parent = lower, child;

	while (parent <= (upper+1)/2 - 1) {
	     child = 2 * parent + 1;
		if (child < upper && a[child] < a[child+1]){
		    child++;
		  
           }
		if (a[child] > a[parent]) {
 		    swap(a[parent],a[child]);
		    parent = child;
		   
		}
		else
	         return;
	}
     return;
}



/*HEAP SORT
  This function will construct a heap and then reads
  of values. This functions will be called ny MAIN(),
  after which this function will call heapify().  
*/
int heapsort(int a[], int numelts)
{
    int count=0;
    
	for (int i = numelts/2 - 1; i >= 0; i--){
	     heapify(a,i,numelts - 1);
	   
    }

	for (int i = numelts - 1; i > 0; i--) {
	     swap(a[0],a[i]);
	     count++;
		heapify(a,0,i-1);
     }
     return count;
}


/*This function will be used/called by quicksort().
  This function will select a position (xpos) to send
  partition and then will move array elements to the
  left or right side of position
*/
int partition(int a[],int lower, int upper)
{
	  int lo = lower, hi = upper, xpos = lower;
	  int x = a[lower];

	  while(lo <= hi) {
			while (hi >= lo && x <= a[hi]){
				 hi--;
				
              }
			if (hi >= lo) {
				  a[lo] = a[hi];
				  xpos = hi;
				  lo++;
				  
			}
			while (lo <= hi && x >= a[lo]){
				  lo++;
				 
              }
			if (lo <= hi)  {
				 a[hi] = a[lo];
				 xpos = lo;
				 hi--;
				 
			}
	}

	if (xpos != lower)
	    a[xpos] = x;
	  

	return xpos;
}


/*This function will be used/called by quicksort().
  This function will use a value xpos, returned
  by partition(), in order to continue the process.
*/
void qsort(int a[], int lower, int upper)
{
	  int pos;
	  

	  if (lower >= upper)
	 
		return;
	  pos = partition(a,lower,upper);
	 
	  qsort(a,lower,pos-1);
	
	  qsort(a,pos+1,upper);
	  
	  return;
  
}

/*QUICK SORT
  This function will be responsible for sorting an
  array using Quick Sort method. It will work by 
  picking a certain element(pivot), then it wil move all
  elements smaller to the left, and all larger to the right. The
  process wil be repeated untill the array is sorted. The function
  will operate recursively. Function receives array as a parameter
  and # of elements. It will be called by MAIN()
*/ 
int quicksort(int a[], int numelts)
{
     int count=0;
	 qsort(a,0,numelts-1);
	 count++;
	 return count;
}

void BubbleSort(int a[], int n) {
	for (int i = n-1; i > 0; --i) {
		for (int j = 0; j < i; ++j) {
			if (a[j + 1] < a[j])
				std::swap(a[j], a[j + 1]);
		}
	}
}