Code C/C++: Thuật toán sắp xếp vun đống (Heap Sort)

Ý tưởng thuật toán:
Ta xem danh sách n phần tử a_0, a_{1, …,}a_n-1  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 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:

#include<math.h>

#include<iostream>

#include<conio.h>

#define max 100

using namespace std;

//Nhập mảng

void NhapMang(int A[],int n){

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

cout<<"nhap Phan tu thu A["<<i<<"] =";

cin>>A[i];

}

}

//Xuất mảng

void XuatMang(int A[],int n){

cout<<endl;

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

cout<<A[i]<<"\t";

} 

//Hoán vị 2 phần tử

void Swap(int &a,int &b){

int temp = a;

a = b;

b =  temp;

}

//Hoán vị nút cha thứ i phải lớn hơn nút con

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);

}

}

//Xây dựng Heap sao cho mọi nút cha luôn lớn hơn nút con trên cây

void BuildHeap(int A[], int n) {

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

Heapify(A,n,i);

}

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);

}

}

//Chương trình chính

int main(){

int A[max], n;

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();

return 0;

}

Kết quả chạy chương trình:

Từ khóa: Sắp xếp, thuật toán, chèn, insert, insertion sort, sắp xếp chèn, giải thuật, cấu trúc dữ liệu và giải thuật, sắp xếp nhanh, quick sort, sắp xếp vun đống, heap sort