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

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

Radix sort click

Couting sort click

Shell Sort click

Ý 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:

nguồn: internet