Các loại Sort nâng cao

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>(), '
');

	/* đọ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");
}