Các loại Sort nâng cao

[nhoxga6895 (Trần Công Thiện)]

MERGE SORT STRAIGHT (TRỰC TIẾP)

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;
#define MAX 1000
int b[MAX], c[MAX];
int f = 1;
int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i <n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i <n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* đọc từng số trong từng dòng*/
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* đọc từng dòng, phân các số vào mảng nguyên */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;

}
void print(int a[], int n)
{
	for (int i = 0; i<n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}



void Merge(int a[], int nb, int nc, int k)
{


	int p, pb, pc, ib, ic, kb, kc;
	p = pb = pc = 0; ib = ic = 0;
	while ((0 <nb) && (0 <nc))
	{
		kb = min(k, nb); kc = min(k, nc);
		if (b[pb + ib] <= c[pc + ic])
		{
			a[p++] = b[pb + ib]; ib++;
			if (ib == kb)
			{
				for (; ic<kc; ic++)
					a[p++] = c[pc + ic];
				pb += kb; pc += kc; ib = ic = 0;
				nb -= kb; nc -= kc;
			}
		}
		else
		{
			a[p++] = c[pc + ic]; ic++;
			if (ic == kc)
			{
				for (; ib<kb; ib++)
					a[p++] = b[pb + ib];
				pb += kb; pc += kc; ib = ic = 0;
				nb -= kb; nc -= kc;
			}
		}
	}

}

void MergeSort(int a[], int n)
{
	int p, pb, pc;

	int i, k = 1;
	do
	{
		p = pb = pc = 0;
		while (p <n)
		{
			for (i = 0; (p <n) && (i < k); i++)
				b[pb++] = a[p++];
			for (i = 0; (p <n) && (i < k); i++)
				c[pc++] = a[p++];
		}
		Merge(a, pb, pc, k);
		cout << "k = " << f << ": " << endl;
		cout << "b: ";
		print(b, pb);
		cout << "c: ";
		print(c, pc);
		cout << "a: ";
		print(a, pc + pb);
		f = f * 2;
		cout << "------------------------" << endl;
		k *= 2;
	} while (k <n);
}



void main()
{
	int n;
	int *a = InitRandom(n);


	//int a[8]={12,2,8,5,1,6,4,15};
	cout << "Before: " << endl;
	print(a, n);
	cout << "---------------------" << endl;
	long start = clock();
	MergeSort(a, n);
	long end = clock();
	cout << "---------------------" << endl;
	cout << "After: " << endl;
	print(a, n);

	cout << "Merge Sort (n= " << n << ") = " << end - start << " (ms)" << endl;
	Write2TextFile(a, n, "output.txt");
	//Read2TextFile(n,"output.txt");

	system("pause");
}

[nhoxga6895 (Trần Công Thiện)]

MERGE SORT BALANCED MULTIWAY (ĐA LỐI CÂN BẰNG)

#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;

#define TRACE 0
void Swap(int** a, int** b)
{
	int* temp = *a;
	*a = *b;
	*b = temp;
}
void Swap(int&a, int&b)
{
	int temp = a;
	a = b;
	b = temp;
}
void Copy(int source[], int target[], int n)
{
	for (int i = 0; i < n; i++) target[i] = source[i];
}
void Print(char name[], int a[], int n)
{
	cout << name << ": ";
	for (int i = 0; i < n; i++)
		if (a[i] != -842150451) cout << a[i] << " ";
	cout << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* đọc từng số trong các dòng */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* đọc từng dòng, phân phối vào mảng nguyên*/
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i < n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i < n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}
void Init(int a[], int n)
{
	for (int i = 0; i <= n; i++) a[i] = -1;
}

int demduong(int a[], int duong[], int length)
{
	int dem = 1, i = 0;
	while (i < length - 1)
	{
		if (a[i] > a[i + 1])
			duong[dem++] = i;
		i++;
	}
	duong[dem] = length - 1;
	return dem;
}

int ganAvaoB(int a[], int b[], int dau, int cuoi, int vitri)
{
	for (int i = dau + 1; i <= cuoi; i++)
		b[vitri++] = a[i];
	return vitri;
}

int tronAvaoB(int b[], int nb, int duong[], int a[], int i, int n)
{
	int *temp = new int[n], ntemp = 0;
	Init(temp, n);
	int x = 0, y = duong[i - 1] + 1;
	while (x <= nb && y <= duong[i])
	{
		if (a[y] > b[x] && b[x] != -1) temp[ntemp++] = b[x++];
		else
		{
			if (a[y] != -1) temp[ntemp++] = a[y++];
			else break;
		}
	}
	while (x <= nb)
	{
		if (b[x] != -1)
			temp[ntemp++] = b[x++];
		else break;
	}
	while (y <= duong[i])
	{
		if (a[y] != -1)
			temp[ntemp++] = a[y++];
		else break;
	}
	ganAvaoB(temp, b, -1, ntemp, 0);

	return ntemp;
}


// 2k--------------------------------------------------------------------------------------------------------------


void chay2k(int a1[], int a2[], int b1[], int b2[], int maxlength, int n, int& n1, int& n2, int& nb1, int& nb2,
	int duong1[], int duong2[], int& nduong1, int& nduong2)
{
	int j = 1;
	Init(b1, n); Init(b2, n);
	while (j <= maxlength)
	{
		int *temp = new int[n], ntemp = 0;
		Init(temp, n);
		if (duong1[j] != -1 || duong2[j] != -1)
		{
			ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);

			if (j % 2 == 0) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
			else nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
		}
		j++;
	}
	n1 = 0; n2 = 0;

}

void phanphoi2k(int a[], int duong[], int a1[], int a2[], int nduong, int& n1, int& n2, int& nb1, int& nb2)
{
	n1 = 0; n2 = 0; nb1 = 0; nb2 = 0;
	for (int i = 0; i < nduong; i++)
	{
		if (i % 2 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
		else n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
	}
}

bool stop2k(int a[], int a1[], int a2[], int b1[], int b2[], int duong1[], int duong2[], int& n1, int& n2,
	int& nduong1, int& nduong2, int& temp, int& nb1, int& nb2)
{
	bool IsRedo = false;
	nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);
	if (nduong1 == 1 && nduong2 == 1 && (n1 == 0 || n2 == 0))
	{
		if (n1 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
		else ganAvaoB(a1, a, -1, n1 - 1, 0);
		return true;
	}
	else if(nduong1 == 1 && n1 == 0)
	{
		phanphoi2k(a2, duong2, b1, b2, nduong2, n1, n2, nb1, nb2);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong2 == 1 && n2 == 0)
	{
		phanphoi2k(a1, duong1, b1, b2, nduong1, nb1, nb2, n1, n2);
		temp = 1;
		IsRedo = true;
	}

	if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);
	else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2);
	return false;
}

void MergeSort2k(int a[], int n)
{
	int *a1 = new int[n], *a2 = new int[n], *b1 = new int[n], *b2 = new int[n];
	int  *duong1 = new int[n], *duong2 = new int[n];
	int n1 = 0, n2 = 0, temp = 0, nb1 = 0, nb2 = 0, lan = 0, maxlength = 0;
	Init(duong1, n);
	int nduong = demduong(a, duong1, n);
	phanphoi2k(a, duong1, a1, a2, nduong, n1, n2, nb1, nb2);

	int pass = 0; // for TRACE
	if (1)
	{
		cout << "----------------------" << endl;
		cout << "Pass " << ++pass << endl;
		Print("a1", a1, n1);
		Print("a2", a2, n2);
	}

	Init(duong1, n); Init(duong2, n);
	int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);

	while (nduong1 >= 1 || nduong2 >= 1)
	{
		if (nduong1 > nduong2) maxlength = nduong1;
		else maxlength = nduong2;
		if (temp == 0)
		{
			n1 = 0; n2 = 0;
			nb1 = 0; nb2 = 0;
		}
		else temp = 0;

		if (lan % 2 == 0)
			chay2k(a1, a2, b1, b2, maxlength, n, n1, n2, nb1, nb2, duong1, duong2, nduong1, nduong2);
		else chay2k(b1, b2, a1, a2, maxlength, n, nb1, nb2, n1, n2, duong1, duong2, nduong1, nduong2);

		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
			Print("a1", a1, n1);
			Print("a2", a2, n2);
			Print("b1", b1, nb1);
			Print("b2", b2, nb2);
		}

		if (lan % 2 == 1)
		{
			if (stop2k(a, a1, a2, b1, b2, duong1, duong2, n1, n2, nduong1, nduong2, temp, nb1, nb2)) break;
		}
		else
		{
			if (stop2k(a, b1, b2, a1, a2, duong1, duong2, nb1, nb2, nduong1, nduong2, temp, n1, n2)) break;
		}
		lan++;
	}
}
// 3k---------------------------------------------------------------------------------------------------------------
void chay3k(int a1[], int a2[], int a3[], int b1[], int b2[], int b3[], int maxlength, int n,
	int& n1, int& n2, int& n3, int& nb1, int& nb2, int&nb3,
	int duong1[], int duong2[], int duong3[], int& nduong1, int& nduong2, int& nduong3)
{
	int j = 1;
	Init(b1, n); Init(b2, n); Init(b3, n);
	while (j <= maxlength)
	{
		int *temp = new int[n], ntemp = 0;
		Init(temp, n);
		if (duong1[j] != -1 || duong2[j] != -1)
		{
			ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong3, a3, j, n);

			if (j % 3 == 1) nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
			else if(j % 3 == 2) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
			else nb3 = ganAvaoB(temp, b3, -1, ntemp, nb3) - 1;
		}
		j++;
	}
	n1 = 0; n2 = 0; n3 = 0;
}

void phanphoi3k(int a[], int duong[], int a1[], int a2[], int a3[], int nduong,
	int& n1, int& n2, int& n3, int& nb1, int& nb2, int& nb3)
{
	n1 = 0; n2 = 0; nb1 = 0; nb2 = 0;
	for (int i = 0; i < nduong; i++)
	{
		if (i % 3 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
		else if(i % 3 == 1) n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
		else n3 = ganAvaoB(a, a3, duong[i], duong[i + 1], n3);
	}
}

bool stop3k(int a[], int a1[], int a2[], int a3[], int b1[], int b2[], int b3[],
	int duong1[], int duong2[], int duong3[], int& n1, int& n2, int& n3,
	int& nduong1, int& nduong2, int& nduong3, int& temp, int& nb1, int& nb2, int& nb3)
{
	bool IsRedo = false;
	nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);
	if (nduong1 == 1 && nduong2 == 1 && nduong3 == 1 &&
		(n1 == 0 || (n2 == 0 && n3 == 0)) &&
		(n2 == 0 || (n1 == 0 && n3 == 0)) &&
		(n3 == 0 || (n1 == 0 && n2 == 0))
		)
	{
		if (n2 == 0 && n3 == 0) ganAvaoB(a1, a, -1, n1 - 1, 0);
		else if(n1 == 0 && n3 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
		else if(n1 == 0 && n2 == 0) ganAvaoB(a3, a, -1, n3 - 1, 0);
		return true;
	}
	else if(nduong1 == 1 && n1 == 0 && nduong3 == 1 && n3 == 0)
	{
		phanphoi3k(a2, duong2, b1, b2, b3, nduong2, n1, n2, n3, nb1, nb2, nb3);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0)
	{
		phanphoi3k(a1, duong1, b1, b2, b3, nduong1, nb1, nb2, nb3, n1, n2, n3);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong2 == 1 && n2 == 0 && nduong1 == 1 && n1 == 0)
	{
		phanphoi3k(a3, duong3, b1, b2, b3, nduong3, nb1, nb2, nb3, n1, n2, n3);
		temp = 1;
		IsRedo = true;
	}

	if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);
	else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2), nduong3 = demduong(b3, duong3, nb3);
	return false;
}

void MergeSort3k(int a[], int n)
{
	int *a1 = new int[n], *a2 = new int[n], *a3 = new int[n], *b1 = new int[n], *b2 = new int[n], *b3 = new int[n];
	int  *duong1 = new int[n], *duong2 = new int[n], *duong3 = new int[n];
	int n1 = 0, n2 = 0, n3 = 0, temp = 0, nb1 = 0, nb2 = 0, nb3 = 0, lan = 0, maxlength = 0;
	Init(duong1, n);
	int nduong = demduong(a, duong1, n);
	phanphoi3k(a, duong1, a1, a2, a3, nduong, n1, n2, n3, nb1, nb2, nb3);

	int pass = 0; // for TRACE
	if (1)
	{
		cout << "----------------------" << endl;
		cout << "Pass " << ++pass << endl;
		Print("a1", a1, n1);
		Print("a2", a2, n2);
		Print("a3", a3, n3);
	}

	Init(duong1, n); Init(duong2, n); Init(duong3, n);
	int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);

	while (nduong1 >= 1 || nduong2 >= 1 || nduong3 >= 1)
	{
		if (nduong1 > nduong2) maxlength = nduong1;
		else maxlength = nduong2;
		if (maxlength < nduong3) maxlength = nduong3;
		if (temp == 0)
		{
			n1 = 0; n2 = 0; n3 = 0;
			nb1 = 0; nb2 = 0; nb3 = 0;
		}
		else temp = 0;

		if (lan % 2 == 0)
			chay3k(a1, a2, a3, b1, b2, b3, maxlength, n, n1, n2, n3, nb1, nb2, nb3, duong1, duong2, duong3, nduong1, nduong2, nduong3);
		else chay3k(b1, b2, b3, a1, a2, a3, maxlength, n, nb1, nb2, nb3, n1, n2, n3, duong1, duong2, duong3, nduong1, nduong2, nduong3);

		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
			Print("a1", a1, n1);
			Print("a2", a2, n2);
			Print("a3", a3, n3);
			Print("b1", b1, nb1);
			Print("b2", b2, nb2);
			Print("b3", b3, nb3);
		}

		if (lan % 2 == 1)
		{
			if (stop3k(a, a1, a2, a3, b1, b2, b3, duong1, duong2, duong3, n1, n2, n3, nduong1, nduong2, nduong3, temp, nb1, nb2, nb3)) break;
		}
		else
		{
			if (stop3k(a, b1, b2, b3, a1, a2, a3, duong1, duong2, duong3, nb1, nb2, nb3, nduong1, nduong2, nduong3, temp, n1, n2, n3)) break;
		}
		lan++;
	}
}
// 4k-----------------------------------------------------------------------------------------------------------------------------
void chay4k(int a1[], int a2[], int a3[], int a4[], int b1[], int b2[], int b3[], int b4[], int maxlength, int n,
	int& n1, int& n2, int& n3, int& n4, int& nb1, int& nb2, int& nb3, int& nb4,
	int duong1[], int duong2[], int duong3[], int duong4[], int& nduong1, int& nduong2, int& nduong3, int& nduong4)
{
	int j = 1;
	Init(b1, n); Init(b2, n); Init(b3, n); Init(b4, n);
	while (j <= maxlength)
	{
		int *temp = new int[n], ntemp = 0;
		Init(temp, n);
		if (duong1[j] != -1 || duong2[j] != -1 || duong3[j] != -1 || duong4[j] != -1)
		{
			ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong3, a3, j, n);
			ntemp = tronAvaoB(temp, ntemp, duong4, a4, j, n);

			if (j % 4 == 1) nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
			else if(j % 4 == 2) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
			else if(j % 4 == 3) nb3 = ganAvaoB(temp, b3, -1, ntemp, nb3) - 1;
			else nb4 = ganAvaoB(temp, b4, -1, ntemp, nb4) - 1;
		}
		j++;
	}
	n1 = 0; n2 = 0; n3 = 0; n4 = 0;

}

void phanphoi4k(int a[], int duong[], int a1[], int a2[], int a3[], int a4[], int nduong,
	int& n1, int& n2, int& n3, int& n4, int& nb1, int& nb2, int& nb3, int& nb4)
{
	n1 = 0; n2 = 0; n3 = 0; n4 = 0; nb1 = 0; nb2 = 0; nb3 = 0; nb4 = 0;
	for (int i = 0; i < nduong; i++)
	{
		if (i % 4 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
		else if(i % 4 == 1) n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
		else if(i % 4 == 2) n3 = ganAvaoB(a, a3, duong[i], duong[i + 1], n3);
		else n4 = ganAvaoB(a, a4, duong[i], duong[i + 1], n4);
	}
}

bool stop4k(int a[], int a1[], int a2[], int a3[], int a4[], int b1[], int b2[], int b3[], int b4[],
	int duong1[], int duong2[], int duong3[], int duong4[], int& n1, int& n2, int& n3, int& n4,
	int& nduong1, int& nduong2, int& nduong3, int& nduong4, int& temp, int& nb1, int& nb2, int& nb3, int& nb4)
{
	bool IsRedo = false;
	nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2); nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);
	if (nduong1 == 1 && nduong2 == 1 && nduong3 == 1 && nduong4 == 1 &&
		(n1 == 0 || (n2 == 0 && n3 == 0 && n4 == 0)) &&
		(n2 == 0 || (n1 == 0 && n3 == 0 && n4 == 0)) &&
		(n3 == 0 || (n1 == 0 && n2 == 0 && n4 == 0)) &&
		(n4 == 0 || (n1 == 0 && n2 == 0 && n3 == 0))
		)
	{
		if (n2 == 0 && n3 == 0 && n4 == 0) ganAvaoB(a1, a, -1, n1 - 1, 0);
		else if(n1 == 0 && n3 == 0 && n4 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
		else if(n1 == 0 && n2 == 0 && n4 == 0) ganAvaoB(a3, a, -1, n3 - 1, 0);
		else if(n1 == 0 && n2 == 0 && n3 == 0) ganAvaoB(a4, a, -1, n4 - 1, 0);
		return true;
	}
	else if(nduong1 == 1 && n1 == 0 && nduong3 == 1 && n3 == 0 && nduong4 == 1 && n4 == 0)
	{
		phanphoi4k(a2, duong2, b1, b2, b3, b4, nduong2, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0 && nduong4 == 1 && n4 == 0)
	{
		phanphoi4k(a1, duong1, b1, b2, b3, b4, nduong1, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong2 == 1 && n2 == 0 && nduong1 == 1 && n1 == 0 && nduong4 == 1 && n4 == 0)
	{
		phanphoi4k(a3, duong3, b1, b2, b3, b4, nduong3, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
		temp = 1;
		IsRedo = true;
	}
	else if(nduong1 == 1 && n1 == 0 && nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0)
	{
		phanphoi4k(a4, duong4, b1, b2, b3, b4, nduong3, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
		temp = 1;
		IsRedo = true;
	}

	if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);
	else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2), nduong3 = demduong(b3, duong3, nb3), nduong4 = demduong(b4, duong4, nb4);
	return false;
}

void MergeSort4k(int a[], int n)
{
	int *a1 = new int[n], *a2 = new int[n], *a3 = new int[n], *a4 = new int[n], *b1 = new int[n], *b2 = new int[n], *b3 = new int[n], *b4 = new int[n];
	int  *duong1 = new int[n], *duong2 = new int[n], *duong3 = new int[n], *duong4 = new int[n];
	int n1 = 0, n2 = 0, n3 = 0, n4 = 0, temp = 0, nb1 = 0, nb2 = 0, nb3 = 0, nb4 = 0, lan = 0, maxlength = 0;
	Init(duong1, n);
	int nduong = demduong(a, duong1, n);
	phanphoi4k(a, duong1, a1, a2, a3, a4, nduong, n1, n2, n3, n4, nb1, nb2, nb3, nb4);

	int pass = 0; // for TRACE
	if (1)
	{
		cout << "----------------------" << endl;
		cout << "Pass " << ++pass << endl;
		Print("a1", a1, n1);
		Print("a2", a2, n2);
		Print("a3", a3, n3);
		Print("a3", a4, n4);
	}

	Init(duong1, n); Init(duong2, n); Init(duong3, n); Init(duong4, n);
	int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);

	while (nduong1 >= 1 || nduong2 >= 1 || nduong3 >= 1 || nduong4 >= 1)
	{
		if (nduong1 > nduong2) maxlength = nduong1;
		else maxlength = nduong2;
		if (nduong3 > maxlength) maxlength = nduong3;
		if (nduong4 > maxlength) maxlength = nduong4;

		if (temp == 0)
		{
			n1 = 0; n2 = 0; n3 = 0; n4 = 0;
			nb1 = 0; nb2 = 0; nb3 = 0; nb4 = 0;
		}
		else temp = 0;

		if (lan % 2 == 0)
			chay4k(a1, a2, a3, a4, b1, b2, b3, b4, maxlength, n, n1, n2, n3, n4, nb1, nb2, nb3, nb4, duong1, duong2, duong3, duong4, nduong1, nduong2, nduong3, nduong4);
		else chay4k(b1, b2, b3, b4, a1, a2, a3, a4, maxlength, n, nb1, nb2, nb3, nb4, n1, n2, n3, n4, duong1, duong2, duong3, duong4, nduong1, nduong2, nduong3, nduong4);

		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
			Print("a1", a1, n1);
			Print("a2", a2, n2);
			Print("a3", a3, n3);
			Print("a4", a4, n4);
			Print("b1", b1, nb1);
			Print("b2", b2, nb2);
			Print("b3", b3, nb3);
			Print("b4", b4, nb4);
		}

		if (lan % 2 == 1)
		{
			if (stop4k(a, a1, a2, a3, a4, b1, b2, b3, b4, duong1, duong2, duong3, duong4, n1, n2, n3, n4, nduong1, nduong2, nduong3, nduong4, temp, nb1, nb2, nb3, nb4)) break;
		}
		else
		{
			if (stop4k(a, b1, b2, b3, b4, a1, a2, a3, a4, duong1, duong2, duong3, duong4, nb1, nb2, nb3, nb4, nduong1, nduong2, nduong3, nduong4, temp, n1, n2, n3, n4)) break;
		}
		lan++;
	}
}
void main()
{
	if (TRACE)
	{
		//int a[] = {3,5,2,7,12,8,4,15,20,1,2,8,23,7,21,27};
		//int a[] = {5,1,2,8,4,17,10,12,4,3,24,1,4};
		int a[] = { 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		int n = sizeof(a) / sizeof(*a);

		cout << "------- BEFORE -------" << endl;
		Print("a", a, n);

		MergeSort2k(a, n);
		//MergeSort3k(a, n);
		//MergeSort4k(a, n);

		cout << "------- AFTER -------" << endl;
		Print("a", a, n);
		_getch();
	}
	else
	{
		// read init data from textfile
		int n;
		int* a = InitRandom(n);
		if (!a) return; // a == NULL

		// sort data
		long start = clock();
		MergeSort2k(a, n);
		//MergeSort3k(a, n);
		//MergeSort4k(a, n);
		long end = clock();
		cout << "10.MergeSort.BalancedMultiway is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;

		// write sorted data to textfile
		Write2TextFile(a, n, "output.txt");
		_getch();
	}
}

[nhoxga6895 (Trần Công Thiện)]

MERGE SORT POLYPHASE (ĐA PHA)

#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;

#define TRACE 0
void Swap(int** a, int** b)
{
	int* temp = *a;
	*a = *b;
	*b = temp;
}
void Swap(int&a, int&b)
{
	int temp = a;
	a = b;
	b = temp;
}
void Copy(int source[], int target[], int n)
{
	for (int i = 0; i < n; i++) target[i] = source[i];
}
void Print(char name[], int a[], int n)
{
	cout << name << ": ";
	for (int i = 0; i < n; i++)
		if (a[i] != -842150451) cout << a[i] << " ";
	cout << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i < n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i < n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}
int CountRuns(int Arr[], const int&numOfElemes)
{
	int counter = 0, i = 0;
	while (i<numOfElemes)
	{
		while (Arr[i] <= Arr[i + 1] && i<numOfElemes - 1)
			i++;
		i++;
		counter++;
	}
	return counter;
}
void Merge(int A[], int B[], int Target[], int&nA, int&nB, int&nTarget)
{
	int i = 0, j = 0;
	while (i<nA && j<nB)
	{
		int tempIndexA = i;
		int tempIndexB = j;
		while (A[i] <= A[i + 1] && i + 1<nA)
			i++;
		while (B[j] <= B[j + 1] && j + 1<nB)
			j++;
		while (tempIndexA <= i && tempIndexB <= j)
		{
			if (A[tempIndexA] <= B[tempIndexB])
				Target[nTarget++] = A[tempIndexA++];
			else
				Target[nTarget++] = B[tempIndexB++];
		}
		while (tempIndexA <= i)
			Target[nTarget++] = A[tempIndexA++];
		while (tempIndexB <= j)
			Target[nTarget++] = B[tempIndexB++];
		i++;
		j++;
	}
	nA -= i;
	nB -= j;
	for (int k = 0; k<nA; k++)
		A[k] = A[k + i];
	for (int k = 0; k <= nB; k++)
		B[k] = B[k + j];
}
void Distribute(int Arr[], int fixBasket[], int DynamicBasket[], const int&nArr, int&nfixBasket, int&nDyncBasket)
{
	int i = 0;
	int counter = 0;
	while (i<nArr)
	{
		int indexKeeper = i;
		while (Arr[i] <= Arr[i + 1] && i<nArr - 1)
			i++;
		if (counter % 2 == 0)
			for (int j = indexKeeper; j <= i; j++)
				fixBasket[nfixBasket++] = Arr[j];
		else
			for (int j = indexKeeper; j <= i; j++)
				DynamicBasket[nDyncBasket++] = Arr[j];
		counter++;
		i++;
	}
}

void MergeSort(int Arr[], const int&n)
{
	if (CountRuns(Arr, n) == 1) return;

	int * A = new int[n];
	int * B = new int[n];
	int * C = new int[n];
	int nA = 0, nB = 0, nC = 0;
	Distribute(Arr, A, B, n, nA, nB);

	int pass = 0; // for TRACE
	if (1)
	{
		cout << "----------------------" << endl;
		cout << "Pass " << ++pass << endl;
		Print("A", A, nA);
		Print("B", B, nB);
	}
	do
	{
		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
		}
		if (nA == 0)
		{
			Merge(B, C, A, nB, nC, nA);
			if (1) Print("A", A, nA);
			if (nC != 0)
			{
				if (1) Print("C", C, nC);
			}
			else if(nB != 0)
			{
				if (1) Print("B", B, nB);
			}
			if (CountRuns(A, nA) == 1 && nB == 0 && nC == 0)
			{
				Copy(A, Arr, n);
				break;
			}
			if (CountRuns(A, nA) != 1 && nB == 0 && nC == 0)
			{
				Distribute(A, B, C, nA, nB, nC);
				nA = 0;
				if (1)
				{
					cout << "----------------------" << endl;
					cout << "Pass " << ++pass << endl;
					Print("B", B, nB);
					Print("C", C, nC);
				}
			}
		}
		else if(nB == 0)
		{
			Merge(A, C, B, nA, nC, nB);
			if (1) Print("B", B, nB);
			if (nC != 0)
			{
				if (1) Print("C", C, nC);
			}
			else if(nA != 0)
			{
				if (1) Print("A", A, nA);
			}
			if (CountRuns(B, nB) == 1 && nA == 0 && nC == 0)
			{
				Copy(B, Arr, n);
				break;
			}
			if (nA == 0 && nB == 0 && CountRuns(B, nB) != 1)
			{
				Distribute(B, A, C, nB, nA, nC);
				nB = 0;
				if (1)
				{
					cout << "----------------------" << endl;
					cout << "Pass " << ++pass << endl;
					Print("A", A, nA);
					Print("C", C, nC);
				}
			}
		}
		else
		{
			Merge(A, B, C, nA, nB, nC);
			if (1) Print("C", C, nC);
			if (nA != 0)
			{
				if (1) Print("A", A, nA);
			}
			else if(nB != 0)
			{
				if (1)Print("B", B, nB);
			}
			if (CountRuns(C, nC) == 1 && nA == 0 && nB == 0)
			{
				Copy(C, Arr, n);
				break;
			}
			if (CountRuns(C, nC) != 1 && nA == 0 && nB == 0)
			{
				Distribute(C, A, B, nC, nA, nB);
				nC = 0;
				if (1)
				{
					cout << "----------------------" << endl;
					cout << "Pass " << ++pass << endl;
					Print("A", A, nA);
					Print("B", B, nB);
				}
			}
		}
	} while (true);
}

void MergeSort_2(int Arr[], const int&n)
{
	if (CountRuns(Arr, n) == 1) return;

	int * NonKeeper1 = new int[n];
	int * NonKeeper2 = new int[n];
	int * Keeper = new int[n];
	int nNonKeeper1 = 0, nNonKeeper2 = 0, nKeeper = 0;
	Distribute(Arr, NonKeeper1, NonKeeper2, n, nNonKeeper1, nNonKeeper2);

	int pass = 0; // for TRACE
	if (1)
	{
		cout << "----------------------" << endl;
		cout << "Pass " << ++pass << endl;
		Print("NonKeeper1", NonKeeper1, nNonKeeper1);
		Print("NonKeeper2", NonKeeper2, nNonKeeper2);
	}
	do
	{
		Merge(NonKeeper1, NonKeeper2, Keeper, nNonKeeper1, nNonKeeper2, nKeeper);
		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
			Print("Keeper", Keeper, nKeeper);
			Print("NonKeeper1", NonKeeper1, nNonKeeper1);
			Print("NonKeeper2", NonKeeper2, nNonKeeper2);
		}
		if (nNonKeeper1 == 0 && nNonKeeper2 == 0)
		{
			if (CountRuns(Keeper, nKeeper) == 1)
			{
				Copy(Keeper, Arr, n);
				break;
			}
			else
			{
				Distribute(Keeper, NonKeeper1, NonKeeper2, nKeeper, nNonKeeper1, nNonKeeper2);
				nKeeper = 0;

				if (1)
				{
					cout << "----------------------" << endl;
					cout << "Pass " << ++pass << endl;
					Print("NonKeeper1", NonKeeper1, nNonKeeper1);
					Print("NonKeeper2", NonKeeper2, nNonKeeper2);
				}
			}
		}
		if (nNonKeeper1 == 0)
		{
			Swap(&NonKeeper1, &Keeper);
			Swap(nKeeper, nNonKeeper1);
		}
		else if(nNonKeeper2 == 0)
		{
			Swap(&NonKeeper2, &Keeper);
			Swap(nKeeper, nNonKeeper2);
		}
	} while (true);
}

void main()
{
	if (TRACE)
	{
		int a[] = { 5, 11, 8, 13, 9, 7, 10, 12, 4, 2, 1, 6, 3 };
		//int a[] = {2,12,17,16,14,30,17,2,50,65,20,32,48,58,16,20,15,10,30,45,16};
		//int a[] = {2,5,3,60,34,22,45,56,43,54,23,32,5,8,6,9,44};
		int n = sizeof(a) / sizeof(*a);

		cout << "------- BEFORE -------" << endl;
		Print("BEFORE", a, n);

		MergeSort(a, n);
		//MergeSort_2(a, n);

		cout << "------- AFTER -------" << endl;
		Print("AFTER", a, n);
		_getch();
	}
	else
	{
		// read init data from textfile
		int n;
		int* a = InitRandom(n);
		if (!a) return; // a == NULL

		// sort data
		long start = clock();
		MergeSort(a, n);
		//MergeSort_2(a, n);
		long end = clock();
		cout << "MergeSort.Polyphase is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;

		// write sorted data to textfile
		Write2TextFile(a, n, "output.txt");
		_getch();
	}
}

MERGE SORT ĐỆ QUY

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i <n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i <n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;

}
void Merge(int A[], int left, int mid, int right)
{
	int i = left, j = mid + 1, n = mid, m = right;
	int *temp = new int[right - left + 1];
	int pos = 0;
	while ((i <= n) && (j <= m))
	{
		if (A[i] <A[j])
		{
			temp[pos] = A[i];
			++i; ++pos;
		}
		else
		{
			temp[pos] = A[j];
			++j; ++pos;
		}
	}
	while (i <= n)
	{
		temp[pos] = A[i];
		++i; ++pos;
	}
	while (j <= m)
	{
		temp[pos] = A[j];
		++j; ++pos;
	}

	for (i = 0; i < pos; ++i)
		A[left + i] = temp[i];
	delete temp;
}

void MergeSort(int A[], int left, int right)
{
	if (left<right)
	{
		int mid = (left + right) / 2;
		MergeSort(A, left, mid);
		MergeSort(A, mid + 1, right);

		Merge(A, left, mid, right);
	}
}


void print(int a[], int n)
{
	for (int i = 0; i<n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

void main()
{
	int n;
	int *a = InitRandom(n);


	//int a[8]={5,9,8,1,7,3,4,6};
	cout << "Before: " << endl;
	print(a, n);
	cout << "---------------------" << endl;
	long start = clock();
	MergeSort(a, 0, n - 1);
	long end = clock();
	cout << "---------------------" << endl;
	cout << "After: " << endl;
	print(a, n);

	cout << "Merge Sort (n= " << n << ") = " << end - start << " (ms)" << endl;
	Write2TextFile(a, n, "output.txt");
	Read2TextFile(n,"output.txt");

	system("pause");
}

MERGE SORT NATURAL (TỰ NHIÊN)

#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;

#define TRACE 0
int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i < n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i < n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}
void Print(char name[], int a[], int n)
{
	cout << name << ": ";
	for (int i = 0; i < n; i++)
		if (a[i] != -842150451) cout << a[i] << " ";
	cout << endl;
}
/* ref: [email protected] (HSU.K10) */
int CountRuns(int Arr[], const int&numOfElemes)
{
	int counter = 0, i = 0;
	while (i<numOfElemes)
	{
		while (Arr[i] <= Arr[i + 1] && i<numOfElemes - 1)
			i++;
		i++;
		counter++;
	}
	return counter;
}
void Merge(int A[], int B[], int Target[], int&nA, int&nB, int&nTarget)
{
	int i = 0, j = 0;
	while (i<nA && j<nB)
	{
		int tempIndexA = i;
		int tempIndexB = j;
		while (A[i] <= A[i + 1] && i + 1<nA)
			i++;
		while (B[j] <= B[j + 1] && j + 1<nB)
			j++;
		while (tempIndexA <= i && tempIndexB <= j)
		{
			if (A[tempIndexA] <= B[tempIndexB])
				Target[nTarget++] = A[tempIndexA++];
			else
				Target[nTarget++] = B[tempIndexB++];
		}
		while (tempIndexA <= i)
			Target[nTarget++] = A[tempIndexA++];
		while (tempIndexB <= j)
			Target[nTarget++] = B[tempIndexB++];
		i++;
		j++;
	}
	while (i<nA)
		Target[nTarget++] = A[i++];
	while (j<nB)
		Target[nTarget++] = B[j++];
	nA = nB = 0; //reset to 0
}
void Distribute(int Arr[], int fixBasket[], int DynamicBasket[], int&nArr, int&nfixBasket, int&nDyncBasket)
{
	int i = 0;
	int counter = 0;
	while (i<nArr)
	{
		int indexKeeper = i;
		while (Arr[i] <= Arr[i + 1] && i<nArr - 1)
			i++;
		if (counter % 2 == 0)
			for (int j = indexKeeper; j <= i; j++)
				fixBasket[nfixBasket++] = Arr[j];
		else
			for (int j = indexKeeper; j <= i; j++)
				DynamicBasket[nDyncBasket++] = Arr[j];
		counter++;
		i++;
	}
	nArr = 0;
}
void MergeSort(int a[], int n)
{
	int pass = 0; // for TRACE

	int* b = new int[n];
	int* c = new int[n];
	while (CountRuns(a, n) > 1)
	{
		int nb = 0, nc = 0;
		Distribute(a, b, c, n, nb, nc);
		if (1)
		{
			cout << "----------------------" << endl;
			cout << "Pass " << ++pass << endl;
			Print("b", b, nb);
			Print("c", c, nc);
		}
		Merge(b, c, a, nb, nc, n);
		if (1)Print("a", a, n);
	}
}


void main()
{
	if (TRACE)
	{
		//int a[] = {12,2,8,5,1,6,4,15};
		//int a[] = {5,1,2,8,4,17,10,12,4,3,24,1,4};
		int a[] = { 2, 5, 3, 60, 34, 22, 45, 56, 43, 54, 23, 32, 5, 8, 6, 9, 44 };
		int n = sizeof(a) / sizeof(*a);

		cout << "------- BEFORE -------" << endl;
		Print("a", a, n);

		MergeSort(a, n);

		cout << "------- AFTER -------" << endl;
		Print("a", a, n);
		_getch();
	}
	else
	{
		// read init data from textfile
		int n;
		int* a = InitRandom(n);
		if (!a) return; // a == NULL

		// sort data
		long start = clock();
		MergeSort(a, n);
		long end = clock();
		cout << "MergeSort.Natural is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;

		// write sorted data to textfile
		Write2TextFile(a, n, "ouput.txt");
		_getch();
	}
}

HEAP SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i <n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i <n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;

}
void print(int *a, int n)
{
	for (int i = 0; i<n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
void Swap(int&a, int&b) // Hoan vi
{

	int c = a;
	a = b;
	b = c;
}
void Shift(int a[], int left, int right){
	int x, curr, joint;
	curr = left; joint = 2 * curr + 1;
	x = a[curr];
	while (joint <= right){
		if (joint <right){
			if (a[joint] <a[joint + 1]){
				joint = joint + 1;
			}
		}
		if (a[joint]<x){
			break;
		}
		a[curr] = a[joint];
		curr = joint;
		joint = 2 * curr + 1;
	}
	a[curr] = x;
}
void CreateHeap(int a[], int n)
{
	int l;
	l = n / 2;
	while (l >= 0)
	{
		Shift(a, l, n);
		l = l - 1;
	}
}
void HeapSort(int *a, int&n)
{
	int dem = 1;
	int r;
	CreateHeap(a, n);
	r = n - 1;
	while (r > 0)
	{
		Swap(a[0], a[r]);
		r = r - 1;
		Shift(a, 0, r);
		cout << "Lan " << dem << " :" << endl;
		print(a, n);
		dem++;
	}
}
void main()
{

	int n = 8;
	int *a=InitRandom(n);
	Write2TextFile(a,n,"input.txt");
	a=Read2TextFile(n,"input.txt");
	//int a[8] = { 11, 3, 5, 4, 9, 15, 19, 7 };
	cout << "Before: ";
	print(a, n);
	cout << "-----------------------" << endl;
	HeapSort(a, n);
	cout << "-----------------------" << endl;
	cout << "After: ";
	print(a, n);
	Write2TextFile(a,n,"output.txt");
	system("pause");
}

RADIX SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
#include"stdio.h"
using namespace std;
#define MAX 10000
#define SHOWPASS

int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i <n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % (n * 10) + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i <n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;

}


void Write_sorted(int *a, int n, char* fileName)
{
	long start = clock();
	int dem = 1;
	ofstream fout(fileName);
	fout << "lan  " << dem << " ";
	dem++;
	for (int i = 0; i <n; i++)
		fout << a[i] << " ";

	fout.close();

	long end = clock();

}

void print(int *a, int n)
{
	int i;
	for (i = 0; i <n; i++)
		cout << a[i] << " ";

}

void radixsort(int *a, int n, char *fileName)
{
	int dem = 1;

	ofstream fout(fileName);
	int i, b[MAX], m = a[0], exp = 1;
	for (i = 1; i <n; i++)
	{
		if (a[i] > m)
			m = a[i];
	}

	while (m / exp > 0)
	{
		int bucket[10] =
		{ 0 };
		for (i = 0; i <n; i++)
			bucket[(a[i] / exp) % 10]++;
		for (i = 1; i < 10; i++)
			bucket[i] += bucket[i - 1];
		for (i = n - 1; i >= 0; i--)
			b[--bucket[(a[i] / exp) % 10]] = a[i];
		for (i = 0; i <n; i++)
			a[i] = b[i];
		exp *= 10;

		#ifdef SHOWPASS

		cout << "\nPASS " << dem++ << " :";
		print(a, n);

		fout << "lan  " << dem << " : ";

		for (int i = 0; i <n; i++)
			fout << a[i] << " ";


		fout << endl;


#endif

	}
	fout.close();

}

void main()
{

	int n;
	int *a = InitRandom(n);
	Write2TextFile(a, n, "input.txt");
	a = Read2TextFile(n, "input.txt");
	//int a[100]={170, 45, 75, 90, 802, 2,24, 66};
	radixsort(a, n, "sorted.txt");
	cout << endl;
	Write2TextFile(a, n, "output.txt");
	system("pause");
}

SHELL SORT

#include"time.h"
#include"algorithm"
#include"fstream"
#include"string"
#include"iostream"
using namespace std;

int* InitRandom(int&n)
{
	cout << "Enter n = "; cin >> n;
	int* a = new int[n];
	srand((unsigned int)time(0));
	for (int i = 0; i <n; i++)
	{
		//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
		a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
	}
	return a;
}

void Write2TextFile(int a[], int n, char* fileName)
{
	long start = clock();

	ofstream fout(fileName);
	for (int i = 0; i <n; i++)
		fout << a[i] << endl;
	fout.close();

	long end = clock();
	cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}

int* Read2TextFile(int&n, char* fileName)
{
	long start = clock();

	/* reading number of lines */
	ifstream fin1(fileName);
	if (!fin1) // fin1 == NULL
	{
		cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
		return NULL;
	}
	n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');

	/* reading each line, and assign to int array */
	int* a = new int[n];
	ifstream fin2(fileName);
	int i = 0;
	while (fin2 >> a[i++]);
	fin2.close();

	long end = clock();
	cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
	return a;

}

void print(int a[], int n)
{
	for (int i = 0; i<n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

void sort(int a[], int n)
{
	cout << "Before: ";
	print(a, n);
	cout << "-----------------------------------" << endl;
	long start = clock();
	int i, j, gap[8] = { 701, 301, 132, 57, 23, 10, 4, 1 };
	int temp;

	for (int k = 0; k<8; k++)
	{
		for (i = gap[k]; i <n; i += 1)
		{
			temp = a[i];
			for (j = i; j >= gap[k] && a[j - gap[k]] > temp; j -= gap[k])
			{
				a[j] = a[j - gap[k]];
			}
			a[j] = temp;
		}

		cout << "gap =" << gap[k] << endl;
		print(a, n);
	}
	cout << "-----------------------------------" << endl;
	cout << "After: ";
	print(a, n);
	long end = clock();
	cout << "Sort time: " << end - start << endl;

}

void main()
{

	int n;
	int *a = InitRandom(n);
	Write2TextFile(a, n, "input.txt");
	a = Read2TextFile(n, "input.txt");
	sort(a, n);
	Write2TextFile(a, n, "output.txt");
	system("pause");
}

[qtd (Đỗ Trung Quân)]

Like!

     sout("Người nông dân phải làm sao khi DC bắt reply >= " +  20'char')

[ltd (Lê Trần Đạt)]

Thiện làm vài cái đơn giản giải thích cho mọi người tại sao lại có mấy cái giải thuật này đi… Hoặc giải thích giải thuật sort ấy. Làm cái này dễ copy mà khó nhai quá hè hè.

[nhoxga6895 (Trần Công Thiện)]

làm giống như mấy cái clip thuật toán a post lên á hả a? @ltd

[ltd (Lê Trần Đạt)]

Ừ, anh thấy làm 1 cái đơn giản trước. Hiểu được rồi thì hiểu một cái cũng là tốt. Còn nhiều cái mà bây giờ mình nhớ, sau này quên thì phí. Ngày trước anh học nhiều thuật toán, nhiều cây lắm. Mà giờ chỉ nhớ được mỗi tìm kiếm tuyến tính(cái này không cần học cũng biết) và tìm kiếm nhị phân.

[nhoxga6895 (Trần Công Thiện)]

dạ, v để e xem, e chưa làm clip bao h

[ltd (Lê Trần Đạt)]

Làm clip là rất tốt, em có thể liên lạc @jimidark bạn ấy làm videos rất đẹp và chuẩn. Không như videos của anh.

Hoặc để nhanh hơn, em có thể viết. Khi viết để giải thích một vấn đề em sẽ thấy rất khó, vì nó yêu cầu em phải tìm hiểu nhiều thứ hơn. Đó cũng là một cách học, bổ sung kiến thức. Dạy và chia sẻ kiến thức với người khác là cách học hiệu quả nhất

Em xem ví dụ bài này do bạn @ddhuy137 viết để chia sẻ kiến thức, rất đầy đủ và công phu. Chắc chắn là tốn không ít thời gian. Phải không Huy?

[Chia sẻ] Data structure alignment & padding

Mình có bài toán nhỏ như sau đố các bạn cho vui: typedef struct { char c; int i; } mstruct; Đố các bạn sizeof(mstruct) là bao nhiêu byte. Chú ý: các expert không được trả lời nhé! Mình dám cá là size của mstruct không phải là 5 bytes. Vì sao như vậy? Theo đúng lý thuyết ta học thì size của struct phải là tổng size của các thành phần bên trong nó mà. Vậy tại sao không phải là 5 bytes, có gì huyền bí ở đây? Để hiểu rõ về việc này, chúng ta hãy cùng tìm hiểu sơ qua Da…