Ta xem danh sách n phần tử a0, a1, …,an-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
Klik untuk melihat kode: