Thuật toán Heap-Sort

+ Tư tưởng của thuật toán Heap-Sort (săp xếp vun đống)

Ta xem danh sách n phần tử a1, a2, a3, ... an  là cây nhị phân.
Cây nhị phân này được xác định như sau: tại nút thứ i tương ứng với chỉ số thứ i của mảng có con trái là nút 2*(i+1)-1 và con phải 2*(i+1) nếu 2*(i+1)-1 và 2*(i+1) nhỏ hơn n.



Thuật toán được mô tả như sau:
- Xây dựng Heap (đống) sao cho với mọi nút cha đều có giá trị lớn hơn nút con. Khi đó nút gốc là nút có giá trị lớn nhất.
- Hoán vị nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với n – 2 nút và tiếp tục hoán vị nút gốc với nút lá cuối của cây mới sau n – 2 bước ta sẽ thu được danh sách được sắp xếp theo thứ tự.

Ví dụ: xét danh sách trước khi sắp xếp

+ Cài đặt thuật toán [Code Tubor C++]

#include <iostream.h>
#include <conio.h>
#define max 100
// nhap day
void NhapMang(int A[],int n) {
for(int i=0; i<n; i++) {
cout<<"nhap Phan tu thu A["<<i<<"] =";
cin>>A[i];
}
}
// in day
void XuatMang(int A[],int n) {
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
// doi cho 2 so
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//hoan vi nut cha thu i phai lon hon nut con (vun dong)
void Heapify(int A[],int n, int i) {
int Left = 2*(i+1)-1;
int Right = 2*(i+1);
int Largest;
if(Left<n && A[Left]>A[i])
Largest = Left;
else
Largest = i;
if(Right<n && A[Right]>A[Largest])
Largest = Right;
if(i!=Largest) {
Swap(A[i],A[Largest]);
Heapify(A,n,Largest);
}
}
//xay dung Heap sao cho moi nut cha luon lon hon nut con tren cay (tao cay)
void BuildHeap(int A[], int n) {
for(int i = n/2-1; i>=0; i--)
Heapify(A,n,i);
}
// heap-sort
void HeapSort(int A[], int n) {
BuildHeap(A,n);
for(int i = n-1; i>0; i--){
Swap(A[0],A[i]);
Heapify(A,i,0);
}
}
// ham main
void main() {
int A[max], n;
clrscr();
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<<"\nMang vua nhap la:";
XuatMang(A,n);
cout<<"\nSap xep theo Heap Sort:";
HeapSort(A,n);
XuatMang(A,n);
getch();
}