#include <stdio.h>
#include <stdlib.h>
#define R 100
#define RAND(R) rand()%R
#define N 10
#define CNT_PRN printf ("\ncnt_cnp=%lld cnt_cpy=%lld\n",cnt_cmp, cnt_cpy)

long long cnt_cmp, cnt_cpy;

int best_array(int a[],int n);
int awg_array(int a[],int n,int k);
int worst_array(int a[],int n);
int printf_array(int a[],int n);
int selection_sort(int a[], int n);
int bubble_sort(int a[], int n);
int max_heapify(int a[], int i, int n);
int build_max_heap(int a[], int n);
int heapsort(int a[], int n);
int countingsort(int a[], int n);

int main()
{
  int array[N];
  best_array(array,N);
  printf_array(array,N);
  awg_array(array,N,10);
  worst_array(array,N);
  printf_array(array,N);
  bubble_sort(array,N);
  heapsort(array, N);
  countingsort(array, N);
  CNT_PRN;
  printf_array(array,N);
  return 0;
}

int best_array(int a[],int n)
{
  int i;
  for(i=0;i<n;i++) a[i]=i;
  return i;
}

int worst_array(int a[],int n)
{
  int i;
  for(i=0;i<n;i++) a[i]=n-1-i;
  return i;
}

int awg_array(int a[],int n,int k)
{
  int i,j;
  for(j=1;j<=k;j++)
  {
      srand(j);
    for(i=0;i<n;i++) a[i]=RAND(R);
    printf_array(a,n);
  }
  return j;
}

int printf_array(int *a,int n)
{
  int i;
  for(i=0;i<n;i++) printf("%d\t",a[i]);
  printf("\n\n");
  return i;
}

int selection_sort(int a[], int n)
{
	int i, S, j, min;
	for(S=0; S<=n-1; S++)
	{
	min=a[S];
	j=S;
		for(i=S+1; i<=n-1; i++)
		{
			if(min>a[i])
			{
				min=a[i];
				j=i;
			}
		}
		a[j]=a[S];
		a[S]=min;
	}
	return min;
}

int bubble_sort(int a[], int n)
{
//
	int k, i, temp;
	for(k=n-2; k>=0; k--)
	{
		for(i=0; i<=k; i++)
		{
			cnt_cmp++;
			if(a[i]>a[i+1])
			{
				temp=a[i];
				a[i]=a[i+1];
				a[i+1]=temp;
				cnt_cpy+=3;
			}
		}
	}
//
}

int max_heapify(int a[], int i, int n)
{
	int left, right, largest, temp;
	left=2*(i+1)-1;
	right=2*(i+1);
	if ((left<n)&&(a[left]<a[i]))
	{
		largest=left;
	}
	else
	{
		largest=i;
	}
	if((right<n)&&(a[right]>a[largest]))
	{
		largest=right;
	}
	if (largest!=i)
	{
		temp=a[i];
		a[i]=a[largest];
		a[largest]=temp;
		max_heapify(a, largest, n);
	}
	return i;
}

int build_max_heap(int a[], int n)
{
	int i;
	i=n/2;
	for(i=n/2; i>=0; i--)
	{
		max_heapify(a, i, n);
	}
	return 1;
}

int heapsort(int a[], int n)
{
	int temp, i, heap_size;
	build_max_heap(a, n);
	heap_size=n;
	i=n-1;
	while (i>0)
	{
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		heap_size=heap_size-1;
		max_heapify(a, 0, heap_size);
		i--;
	}
	return a[i];
}


int countingsort(int a[], int n)
{
	int b[N], c[N];
	int i, j, k;
	k=10;
	for(i=0; i<k; i++)
	{
		c[i]=0;
	}
	for(j=0; j<n; j++)
	{
		c[a[j]]++;
	}
	for(i=1; i<k; i++)
	{
		c[i]=c[i]+c[i-1];
	}
	for(j=n-1; j>=0; j--)
	{
		b[c[a[j]]]=a[j];
		c[a[j]]--;
	}
	return b[c[a[j]]];
}