#include <stdio.h>
int g=0;

int tab11[30];
int tab12[30];
int tab21[30];
int tab22[30];
int tab31[30];
int tab32[30];
int tab41[30];
int tab42[30];

int qpor=0;
int qpods=0;
void druk(int a[], int n)
{
	int i=0;
	for(i;i<n;i++)
	{
		printf("%i ",a[i]);
	}
	printf("\n");
}
void losu(int a[], int n)
{
	srand(time(NULL));
	int i=0;
	for(i;i<n;i++)
	{
		a[i]=rand()%n;
	}
}
void kopiuj(int a[],int b[],int n)
{
	int i=0;
	for(i;i<n;i++)
	{
		b[i]=a[i];
	}
}
void wstawianie(int a[],int n)
{
	unsigned long long int por=0;
	unsigned long long int pods=0;
	int i,j,x;
	for(i=1;i<n;i++)
	{
		por++;
		if(a[i]<a[0])
		{
			pods=pods+2;
			x=a[0];
			a[0]=a[i];
		}
		else
		{
			pods++;
			x=a[i];
		}

		for(j=i-1;x<a[j];j--)
		{
			por++;
			a[j+1]=a[j];
			pods++;
		}
		pods++;
		a[j+1]=x;
	}
	tab21[g]=por;
	tab22[g]=pods;
	//printf("Sortowanie przez wstawianie porownania - %i , podstawienia - %i\n",pods,pods);
}
void babelkowe(int a[],int n)
{
	unsigned int por=0;
	unsigned int pods=0;
	int i,j,x;
	for(i=1;i<n;i++)
	{
		for(j=n-1;j>=i;j--)
		{
			por++;
			if(a[j-1]>a[j])
			{
				//SPRAWDŹ CAŁY PROGRAM TAK OOOO
				pods+=3;
				x=a[j-1];
				a[j-1]=a[j];
				a[j]=x;
			}
		}
	}
	tab11[g]=por;
	tab12[g]=pods;
	//printf("Sortowanie babelkowe porownania - %i , podstawienia - %i\n",por,pods);
}

int Partition(int a[],int p, int r)
{
	int _r=rand()%(r-p+1)+p,x,i,j;
	qpods=qpods+5;
	x=a[p];
	a[p]=a[_r];
	a[_r]=x;
	x=a[p];
	i=p-1;
	j=r+1;

	do
	{
		do
		{
			j--;
			qpor++;
		}while(a[j]>x);
		do
		{
			qpor++;
			i++;
		}while(a[i]<x);
		if(i<j)
		{
			qpods=qpods+3;
			int y;
			y=a[i];
			a[i]=a[j];
			a[j]=y;
		}
	}while(i<j);
	return j;
}
void QSort(int a[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=Partition(a,p,r);
		QSort(a,p,q);
		QSort(a,q+1,r);
	}
}
void shell(int d[],int n)
{
	int por=0;
	int pods=0;
	int h,j,x,i;
	for(h=1;h<n;h=3*h+1);
  	h/=9;
	while(h)
	{
    	for(j=n-h-1;j>=0;j--)
    	{
    		pods++;
    		x = d[j];
      		i = j + h;
      		while((i<n) && (x>d[i]))
      		{
      			por=por+2;
      			pods++;
        		d[i-h] = d[i];
        		i+=h;
      		}
    	pods++;
      	d[i-h]=x;
    	}
    	h/=3;
  	}
  	tab41[g]=por;
	tab42[g]=pods;
	//printf("Sortowanie metoda Shella porownania - %i , podstawienia - %i\n",por,pods);
}
int main()
{
	int n;
	for(n=100;n<1000000;)
	{
	int i=0;
	int tab[n];
	int tab1[n];
	int tab2[n];
	int tab3[n];
	for(i=0;i<30;i++)
	{
		losu(tab,n);
		kopiuj(tab,tab1,n);
		kopiuj(tab,tab2,n);
		kopiuj(tab,tab3,n);
		babelkowe(tab,n);
		wstawianie(tab1,n);
		QSort(tab2,n/2,n);

		tab31[i]=qpor;
		tab32[i]=qpods;
		//printf("Szybkie sortowanie porownania - %i , podstawienia - %i\n",qpor,qpods);
		qpor=0;
		qpods=0;
		shell(tab3,n);
		g++;
	}
	i=0;
	unsigned long long int sumapor1=0;
	unsigned long long int sumapod1=0;
	unsigned long long int sumapor2=0;
	unsigned long long int sumapod2=0;
	unsigned long long int sumapor3=0;
	unsigned long long int sumapod3=0;
	unsigned long long int sumapor4=0;
	unsigned long long int sumapod4=0;
	for(i=0;i<30;i++)
	{
		sumapor1+=tab11[i];
		sumapod1+=tab12[i];
		sumapor2+=tab21[i];
		sumapod2+=tab22[i];
		sumapor3+=tab31[i];
		sumapod3+=tab32[i];
		sumapor4+=tab41[i];
		sumapod4+=tab42[i];
	}
	sumapor1=sumapor1/30;
	sumapod1=sumapod1/30;
	sumapor2=sumapor2/30;
	sumapod2=sumapod2/30;
	sumapor3=sumapor3/30;
	sumapod3=sumapod3/30;
	sumapor4=sumapor4/30;
	sumapod4=sumapod4/30;
	printf("Sposoby kolejno: babelkowe, wstawianie, QSort, Shell\nPorownania - podstawienia - n\n");
	printf("%d - %d - %d\n",sumapor1,sumapod1,n);
	printf("%d - %d - %d\n",sumapor2,sumapod2,n);
	printf("%d - %d - %d\n",sumapor3,sumapod3,n);
	printf("%d - %d - %d\n",sumapor4,sumapod4,n);
	/*
	losu(tab1,n);
	kopiuj(tab1,tab2,n);
	kopiuj(tab1,tab3,n);
	kopiuj(tab1,tab4,n);

	//druk(tab1,n);
	babelkowe(tab1,n);
	//druk(tab1,n);

	//druk(tab2,n);
	wstawianie(tab2,n);
	//druk(tab2,n);

	//druk(tab3,n);
	QSort(tab3,n/2,n);
	//druk(tab3,n);

	//druk(tab4,n);
	shell(tab4,n);
	//druk(tab4,n);


	*/
	if(n<1000) n=n+100;
	else
	{
		if(n<10000) n=n+10000;
		else
		{
			if(n<100000)
			n=n+10000;
			else n=n+100000;
		}
	}
	g=0;
	}
	return 0;
}