//CIS 251: Sorting
//Due: Nov 11, 99
//Comparison and Interchang in Bubble and Quick Sort

#include<iostream.h>

main()
{

	int comp=0,intr=0;
	void bubble(int x[],int n);
	void quick(int x[],int lb,int ub,int*,int*);
	void partition(int* x,int ,int,int*,int*,int*);
	int  i, a[]={4,1,110,99,39,73,8};
	cout << "\nUnSorted Array is =";
	for(i=0;i<7;i++) cout << '\n' << a[i] ;
	cout << "\n\nSorting now...";
	bubble(a,7);
	quick(a,0,6,&comp,&intr);
	
	cout << "\nSorted Array is =";
	for(i=0;i<7;i++) cout << '\n' << a[i] ;
	cout << "\nQSort Comparison=" << comp;
	cout << "\nQSortInterchanges=" << intr;
	return 0;
}


void bubble(int x[],int n)
{
	int pass,hold,j,comp=0,intr=0;
	bool s=true;
	for(pass=n-1;pass>-1 && s;pass--)
	{
		s=false;
		for(j=n-1;j>n-pass-1;j--) 
		{
			if (x[j]<x[j-1]) 
			{ 
			intr++;
			s=true;
			hold=x[j];
			x[j]=x[j-1];
			x[j-1]=hold;
			}
			comp++;
		}
	}
	cout << "\nBubble Interchange =" << intr;
	cout << "\nBubble Comparison =" << comp;
}



void partition(int x[],int lb,int ub, int * pj,int * comp,int * intr)
{
	int a, down,temp,up;
	a=x[lb];
	up=ub;
	down=lb;
	while(down<up) {
		while(x[down]<=a && down < ub) {down++;(*comp)++;}
		while (x[up]>a) {up--;(*comp)++;}
		if (down < up) { temp=x[down];x[down]=x[up];x[up]=temp;(*intr)++;}
	}
	x[lb]=x[up];
	x[up]=a;
	*pj=up;
	(*intr)++;

}


void quick(int x[],int lb, int ub,int * comp,int * intr)
{
	int  j=2;
	if (lb >=ub) return; else (*comp)++;
	partition(x,lb,ub,&j,comp,intr);
		quick(x,lb,j-1,comp,intr);
		quick(x,j+1,ub,comp,intr);
}