my code stock.com

Snippet options

Download: Download snippet as heap-sort.cpp.
Copy snippet: For this you need a free my code stock.com account.
Embed code : You will find the embed code for this snippet at the end of the page, if you want to embed it into a website or a blog!

// ***************************
// Email: [email protected]
// Project: HeapSort
//*******************

#include <iostream>
using namespace std;

#define MAXSL 100 + 5

void NhapMang(int A[], int &N);
void XuatMang(int A[], int N);
void Swap(int &X, int &Y);

void Heap(int A[], int SL);
void HeapSort(int A[], int N);

void main()
{
	int A[MAXSL] = {};
	int N = 0;
	NhapMang(A, N);
	HeapSort(A, N);
	cout << "Mang da sap xep: " << endl;
	XuatMang(A, N);

	system("pause");
}

void NhapMang(int A[], int &N)
{
	cout << "So luong phan tu N = ";
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cout << "A[" << i << "] = ";
		cin >> A[i];
	}
}

void XuatMang(int A[], int N)
{
	for (int i = 0; i < N; i++)
		cout << A[i] << " ";
	cout << endl;
}
void Swap(int &X, int &Y)
	// *** Đây là 1 hàm hoán đổi
{
	int Tam = X;
	X = Y;
	Y = Tam;
}

void HeapSort(int A[], int N)
	// *** Săp xếp mảng A, gồm N phần tử bằng giải thuật HeapSort
	// *** Ý tưởng: ta xem mảng A, n phần tử là 1 cây nhị phân gồm n nút, có đỉnh là vị trí 0 
	// với nút cha i bất kỳ thì có 2 nút con là  (i * 2 + 1) và (i * 2 + 2),
	// với 0 <= (i * 2 + 1), (i * 2 + 2) < N
	// sử dụng giải thuật Heap (Vun Đống) để để lấy ra phần tử max trong cây nhị phân,
	// cây nhị phân sau khi lấy phần tử Max sẽ bị thu nhỏ bớt 1 phần tử
{
	for (int i = N - 1; i >= 0; i--)
	{
	    // Vun Đống Cây để tìm giá trị lớn nhất của cây nhị phân có i nút
		Heap(A, i); 
		// hoán đổi đỉnh cây nhị phân (đang là giá trị lớn nhât), cho nút cuối của cây
		Swap(A[0], A[i]); 
	}
}

void Heap(int A[], int SL)// còn được gọi là "Vun Đống Cây"
	// *** SL chỉ số lượng cần vun đống
	// *** Ý tưởng: duyệt cây nhị phân, nếu tồn tại nút cha bất kỳ nhỏ hơn nút con,
	// thì hoán đổi nút cha và nút con đó
	// *** Lưu ý: với 1 cây nhị phân có SL nút số, thì thứ tự của nút cha nhỏ nhất sẽ là (SL - 1) / 2,
	// với nút cha là nút có nút con
{
	for (int i = (SL - 1) / 2; i >= 0; i--)
		// Ta se duyệt từ nút cha nhỏ nhất về nút đỉnh
	{
		if ((i * 2 + 1 <= SL) && (A[i * 2 + 1] > A[i])) 
		// Ý nghĩa: (i * 2 + 1) phải nằm trong cây SL nút đang xét, nút con > nút cha
			Swap(A[i * 2 + 1], A[i]);
		if ((i * 2 + 2 <= SL) && (A[i * 2 + 2] > A[i])) 
		// Ý nghĩa: (i * 2 + 2) phải nằm trong cây SL nút đang xét, nút con > nút cha
			Swap(A[i * 2 + 2], A[i]);
	}
}

Create a free my code stock.com account now.

my code stok.com is a free service, which allows you to save and manage code snippes of any kind and programming language. We provide many advantages for your daily work with code-snippets, also for your teamwork. Give it a try!

Find out more and register now

You can customize the height of iFrame-Codes as needed! You can find more infos in our API Reference for iframe Embeds.