/*
Chuong trinh: Thuc hanh phuong phap sap xep truc tiep
*/
Code:
#include<stdio.h>
#include<conio.h>
void HoanVi(int &a,int &b);
void Shift(int a[],int left,int right);// Ham hieu chinh mang ->Dang Heap;
void CreateHeap(int a[],int n);// Ham Tao
void HeapSort(int a[],int n);// Ham chinh;
void Xuat(int a[],int n);
void main()
{
int m[]={2,5,1,6,3,8,4,9,7,0};
int spt=9;
clrscr();
CreateHeap(m,spt);//hieu chinh day ban dau thanh heap
HeapSort(m,spt);//sap xep bang heap sort
Xuat(m,spt);
getch();
}
void HoanVi(int &a,int &b)
{
int tmp;
tmp=a;
a = b;
b=tmp;
}
//hieu chinh day bat ki thanh heap
void Shift(int a[],int left,int right)
{
int x,i,j;
i=left;
j=2*i;
x=a[i];//phan tu cha
while(j<=right)
{
if(j<right)
if(a[j]<a[j+1])//xac dinh phan tu lien doi lon nhat
j++;
if(a[j]<=x)
return;//thoa quan he lien doi dung
else
{
a[i]=a[j];
i=j;//xet tiep kha nang hieu chinh lan truyen
j=2*i;//cap nhat phan tu lien doi moi
a[i]=x;//cap nhat phan tu cha moi
}
}
}
//tao mot heap
void CreateHeap(int a[],int n)
{
int left;
left=(n-1)/2;
while(left>=0)//
{
Shift(a,left,n-1);
left--;//xet tu giua ve dau mang
}
}
//sap sep bang heap sort
void HeapSort(int a[],int n)
{
int right;
CreateHeap(a,n);//tao heap truoc khi xep
right=n-1;
while(right>0)
{
HoanVi(a[0],a[right]);
right--;//lui ve truoc dua phan tu lon nhat ra sau mang
Shift(a,0,right);//hieu chinh day con lai thanh mot heap
}
}
void Xuat(int a[],int n)
{
printf("\nMang vua sap xep lai la: \n\n\n");
for(int i=0;i<n;i++)
printf(" %d\t",a[i]);
}
--------------------------------------------------------
Chú ý viết tiếng việt có dấu và đặt code vào tag