#include<stdio.h>
#include<conio.h>

#define MAX_ARRAY 30

void quicksort(int a[],int l,int r);
void partition(int a[],int l, int r,int *p1,int*pj);
void mergesort(int a[],int l,int r);
void merge(int a[],int l,int q,int r);
void heapsort(int a[],int n);
void heapify(int a[],int p,int u);
void buildheap(int a[],int n);

int b[MAX_ARRAY];
void main(void)
{
	int i,n,l=0,r=10,a[MAX_ARRAY],scelta;
	n=11;
	a[0]= 5;
	a[1]= 7;
	a[2]= 2;
	a[3]= 5;
	a[4]= 9;
	a[5]= 6;
	a[6]= 1;
	a[7]= 8;
	a[8]= 3;
	a[9]= 0;
	a[10]= 4;
	scanf("%d",&scelta);
	switch(scelta)
	{
	case 1: quicksort(a,l,r);
	case 2: mergesort(a,l,r);
	case 3: heapsort(a,n);
	}
	for(i=0;i<n;i++)
		printf("%d ",a[i]);
}

void quicksort(int a[],int l,int r)
{
	int i,j;
	if(l<r)
	{
		partition(a,l,r,&i,&j);
		quicksort(a,l,j);
		quicksort(a,i,r);
	}
}

void partition(int a[],int l, int r,int *pi,int*pj)
{
	int x,t;
	*pi=l;
	*pj=r;
	x=a[(l+r)/2];
	do{
		while(a[*pi]<x) (*pi)++;
		while(a[*pj]>x) (*pj)--;
		if(*pj>=*pi)
		{
			t=a[*pi];
         a[*pi]=a[*pj];
			a[*pj]=t;
			(*pi)++;
			(*pj)--;
		}
	}while(*pj>=*pi);
}

void mergesort(int a[],int l,int r)
{
	int q;
	if(l<r)
	{
		q=(l+r)/2;
		mergesort(a,l,q);
		mergesort(a,q+1,r);
	}
}

void merge(int a[],int l,int q,int r)
{
	int i,j,k;
	for(i=l;i<=r;i++)
		b[i]=a[i];
	i=l;
	j=q+1;
	for(k=1;i<=q && j<=r; k++)
		a[k]=((b[i]<b[j])?b[i++]:b[j++]);
	while(i<=q)
		a[k++]=b[i++];
	while(i<=r)
		a[k++]=b[j++];
}

void heapsort(int a[],int n)
{
	int i,t;
	buildheap(a,n);
	for(i=n-1;i>0;i--)
	{
		t=a[0];
		a[0]=a[i];
		a[i]=t;
		heapify(a,0,i-1);
	}
}

void heapify(int a[],int p,int u)
{
	int s,d,max,t;
	s=2*p+1;
	d=2*p+2;
	max=((s<=u && a[s]>a[p])?s:p);
	max=((d<=u && a[d]>a[max])?d:max);
	if(max!=p)
	{
		t=a[max];
		a[max]=a[p];
		a[p]=t;
		heapify(a,max,u);
	}
}

void buildheap(int a[],int n)
{
	int i;
	for(i=(n/2)-1;i>=0;i--)
		heapify(a,i,n-1);
}