/* Cac bai toan sap xep.............

Chao mung ban den voi nhung giai thuat sap xep hay nhat!

Mong cac ban se dong gop y kien de giai thuat duoc toi uu hon !

*/

// Nhap thu vien .........

#include"iostream.h"

#include"iomanip.h"

#include"math.h"

#include"conio.h"

#include"stdio.h"

// giai thuat selection sort (chon truc tiep)...................

/*void selection_sort(int a[100],int n)

{

int min,i;

for(i=0;i<n-1;i++)

{

min=i;

for(int j=i+1;j<n;j++)

if(a[j]<a[min])

min=j;

if(min!=j)

{

int tg=a[i];

a[i]=a[min];

a[min]=tg;

}

}

} */

/*

//Giai thuat insertionsort( chen truc tiep)

void insertion_sort(int a[100],int n)

{

int x,pos;

for(int i=1;i<n;i++)

{

x=a[i];

pos=i-1;

while((pos>=0)&&(a[pos]>x))

{ a[pos+1]=a[pos];

pos--;

}

a[pos+1]=x;

}

} */

/*

//Giai thuat interchange_sort(Doi cho truc tiep)

void interchange_sort(int a[100],int n)

{

for(int i=0;i<n-1;i++)

for(int j=i+1;j<n;j++)

if(a[j]<a[i])

{

int tg=a[i];

a[i]=a[j];

a[j]=tg;

}

} */

/*

// Giai thuat Bubble_sort(phuong phap noi bot)

void bubble_sort(int a[100],int n)

{

int i,j;

for(i=0;i<n-1;i++)

for(j=n-1;j>1;j--)

if(a[j]<a[j-1])

{

int tg=a[i];

a[i]=a[j];

a[j]=tg;

}

} */

// Giai thuat Heap_sort(sap xep cay)(chua xong)

void push(int i,int n,int a[100])

{

int j; int tg=a[i];

while(i<=(n/2-1))

{

j=2*i+1;

if(j<n-1&&a[j]<a[j+1])

j++;

if(tg<a[j])

{

a[i]=a[j];

i=j;

}

else

n=j;

a[i]=tg;

}

}

void heap_sort(int a[100],int n)

{ int i;

for(i=(n/2-1);i>=0;i--)

push(i,n,a);

for(i=n-1;i>0;i--)

{

int tg=a[i];

a[i]=a[0];

a[0]=tg;

push(0,i,a);

}

}

/*

// Giai thuatsap xep nhanh(Quick_sort)...........

void quick_sort(int a[], int n, int l, int r)

{

int i,j;

if(l<r)

{

int x=a[(l+r)/2];

i=l;

j=r;

while(i<j)

{

while(a[i]<x) i++;

while(a[j]>x) j--;

if(i<=j)

{

int tg=a[i];

a[i]=a[j];

a[j]=tg;

i++; j--;

}

}

quick_sort(a,n,l,j);

quick_sort(a,n,i,r);

}

}

*/

void main()

{ clrscr();

int n,a[100];

// int l,r;

cout<<"nhap n= "; cin>>n;

// cout<<"nhap mang a:

)";

for(int i=0;i<n;i++)

{

cout<<"a["<<i<<"]=";

cin>>a[i];

}

cout<<"mang da duoc sap

";

// selection_sort(a,n);

// insertion_sort(a,n);

// interchange_sort(a,n);

// bubble_sort(a,n);

heap_sort(a,n);

// quick_sort(a,n,0,n-1);

{ for( i=0;i<n;i++)

{// cout<<"a["<<i<<"]=";

cout<<a[i]<<" ";

}

}

// hien();

getch();

}