#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define N 20

typedef struct element {
	int valoare;
}element;

typedef element elemente[20];
elemente el;

typedef enum{fals, tru} boolean;

void insertie(elemente el)
{
	int i,j;
	element aux;
	for(i=1;i<N;i++)
	{
		aux=el[i];
		j=i-1;
		while(j>=0&&el[j].valoare>aux.valoare)
		{
			el[j+1]=el[j];
			j--;
		}
		el[j+1]=aux;
	}
}


void insertieBinara(elemente el)
{
	int i,j,s,d,m;
	element aux;
	for(i=1;i<N;i++)
	{
		aux=el[i];
		s=0; d=i-1;
		while(s<=d)
		{
			m=(s+d)/2;
			if(el[m].valoare>aux.valoare)
				d=m-1;
			else s=m+1;
		}
		for(j=i-1;j>=s;j--)
		{
			el[j+1]=el[j];
		}
		el[s]=aux;
	}
}


void selectie(elemente el)
{
	int i,j,k_min;
	element aux_min,aux;
	for(i=0;i<N-1;i++)
	{
		aux_min=el[i];
		k_min=i;
		for(j=i;j<N;j++)
			if(aux_min.valoare>el[j].valoare)
				{
					aux_min=el[j];
					k_min=j;
				}
		aux=el[i];
		el[i]=el[k_min];
		el[k_min]=aux;
	}
}

void selectiePerf(elemente el)
{
	int i,j,k_min;
	element aux_min,aux;
	for(i=0;i<N-1;i++)
	{
		k_min=i;
		for(j=i;j<N;j++)
			if(el[k_min].valoare>el[j].valoare)
				{
					k_min=j;
				}
		aux=el[i];
		el[i]=el[k_min];
		el[k_min]=aux;
	}
}


void bubble(elemente el)
{
	int i,j;
	element aux;

	for(i=1;i<N-1;i++)
	{
		for(j=N-1;j>=i;j--)
			if(el[j-1].valoare>el[j].valoare)
			{
				aux=el[j-1];
				el[j-1]=el[j];
				el[j]=aux;
			}
	}
}


void shakesort(elemente el)
{
	int j,k,st,dr;
	element aux;
	st=1;
	dr=N-1;
	k=N-1;

	do{
		for(j=dr;j>=st;j--)
			if(el[j-1].valoare>el[j].valoare)
			{
				aux=el[j-1];
				el[j-1]=el[j];
				el[j]=aux;
				k=j;
			}
		st=k+1;
		for(j=st;j<=dr;j++)
			if(el[j-1].valoare>el[j].valoare)
			{
				aux=el[j-1];
				el[j-1]=el[j];
				el[j]=aux;
				k=j;
			}
		dr=k-1;
	}while(st<=dr);
}


void shellsort(elemente el)
{
	int h[3]={3,2,1};
	int i,j,k,w,t=3;
	element aux;
	for(w=0;w<t;w++)
	{
		k=h[w];
		for(i=k;i<N;i=i+k)
		{
			aux=el[i];
			j=i-k;
			while(j>=0&&el[j].valoare>aux.valoare)
			{
				el[j+k]=el[j];
				j=j-k;
			}
			el[j+k]=aux;
		}

	}
}


void quicksort(int st, int dr)
{
	int i,j;
	element x,aux;
	i=st;
	j=dr;
	x=el[(st+dr)/2];
	do{
		while(el[i].valoare<x.valoare)
			i++;
		while(el[j].valoare>x.valoare)
			j--;
		if(i<=j)
		{
			aux=el[i];
			el[i]=el[j];
			el[j]=aux;
			i++;
			j--;
		}
	}while(i<=j);

	if(st<j)
		quicksort(st,j);
	if(dr>i)
		quicksort(i,dr);
}



void deplasare(int s, int d)
{
	int i,j;
	element x;
	boolean bul;
	//while(el[s].valoare>el[2*s].valoare&&el[s].valoare>el[2*s+1].valoare)
	i=s;
	j=2*i;
	x=el[i];
	bul=fals;

	while(j<=d&&bul==fals)
	{
		if(j<d)
		{
			if(el[j].valoare<el[j+1].valoare)
				j++;
		}
	if(x.valoare<el[j].valoare)
	{
		el[i]=el[j];
		i=j;
		j=2*i;
	}
	else
		bul=tru;

	}
	el[i]=x;
}


void heapsort(elemente el)
{
	int s,d;
	element auxx;

	s=N/2+1;
	d=N;

	while(s>1)
	{
		s--;
		deplasare(s,N-1);
	}

	while(d>1)
	{
		auxx=el[1];
		el[1]=el[d];
		el[d]=auxx;
		d--;
		deplasare(1,d);
	}
}


int main()
{
	int i;
	for(i=0;i<N;i++)
		el[i].valoare=rand();


	for(i=0;i<N;i++)
		printf("%d\n", el[i].valoare);

	printf("\n\n");

	heapsort(el);

	printf("\n");
	for(i=0;i<N;i++)
		printf("%d\n", el[i].valoare);
	getch();
	return 0;
}