my code stock.com

Snippet options

Download: Download snippet as merge-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: MergeSort
//*******************

#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 MergeSort(int A[], int L, int R);
void Merge(int A[], int L ,int R);

void main()
{
	int A[MAXSL] = {};
	int N = 0;
	NhapMang(A, N);
	MergeSort(A, 0, N - 1);
	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 MergeSort(int A[], int L, int R)
	// *** Săp xếp mảng A, gồm N phần tử bằng giải thuật Merge Sort
	// *** Ý tưởng: Ta chia dãy số thành 2 dãy, sau trộn hai dãy này thành 1 dãy, dãy này là kết quả,
	//	hai dãy được chia phải được sắp xếp, để đảm bảo điều này, 
	//	ta xem mỗi dãy là 1 dãy mới và cũng chia nhỏ như dãy ban đầu, đến khi dãy chia nhỏ đã sắp xếp
{
	if (L < R) // Nếu L == R, xem như dãy đầu vào có 1 phần tử, và dãy này đã được sắp xếp.
	{
		int K = (L + R) / 2;
		// Chia dãy đầu vào thành 2 dãy mới
		MergeSort(A, L, K);
		MergeSort(A, K + 1, R);
		// Trộn hai dãy trên thành 1 dãy, trong đó trong đó vị trí phân cách giữ hai dãy ngầm định là K = (L + R) / 2
		Merge(A, L, R);
	}
}

void Merge(int A[], int L ,int R)
	// *** Trộn hai dãy nằm kề nhau và được phân cách ngầm định là K = (L + R) / 2
	// *** Ý tưởng: Ta lần lượt duyệt các phần tử của cả hai dãy, ở mỗi lượt duyệt ta duyệt hai phần tử 1 của dãy I, 1 của dãy II
	//		so sánh 2 phần tử và lấy ra phần tử nhỏ hơn bỏ vào dãy Kết Quả, cứ như vậy 2 dãy được trộn với nhau
{
	// Vì trộn dãy không mang tính tự đổi chỗ, nên ta phải dùng một mảng trung gian, ở đây ta dùng mảng B là mảng chứa dãy cần trộn
	//		A là mảng lưu dãy đã được trộn
	int B[MAXSL] = {};
	for (int u = L; u <= R; u++)
		B[u] = A[u];
	
	int K = (L + R) / 2;
	int i = L;
	int j = K + 1;
	int t = L - 1;
	// Trộn hai dãy
	while (t < R)
	{
		if ((B[i] <= B[j] || j == R + 1) && i != K + 1)
		{
			t++;
			A[t] = B[i];
			i++;
		}
		if ((B[i] > B[j] || i == K + 1) && j != R + 1)
		{
			t++;
			A[t] = B[j];
			j++;
		}
	}
}

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.