Merge Sort

Thuật toán Merge sort

Thuật toán Merge Sort là loại thuật toán sắp xếp theo phương pháp trộn có độ phức tạp trung bình O(n.logn).

Mảng cần sắp xếp sẽ có những đoạn mảng con đã có thứ tự tăng dần hoặc giảm dần. Làm giảm dần các mảng con, chỉ còn một mảng con duy nhất có chiều tăng giảm đúng với yêu cầu bằng cách chia mảng ban đầu ra 2 mảng phụ theo nguyên tắc luân phiên, cứ một phần tử vào mảng thứ nhất thì phần tử tiếp sau vào mảng thứ hai và ngược lại.

Trộn từng cặp mảng con trong hai mảng phụ vào mảng ban đầu sẽ được mảng mới có các phần tử tương tự mảng ban đầu nhưng có trật tự thay đổi, số đoạn mảng con giảm dần, ít nhất là giảm đi một nửa theo hướng sắp xếp.

Tuần tự tăng dần độ lớn của mảng con và thực hiện tương tự các bước trên cho đến khi độ lớn của mảng con vượt quá số phần tử của mảng ban đầu.

Code mẫu thuật toán Merge Sort

#include <stdio.h>

// trả về số nhỏ hơn
int min(int a, int b)													
{
	if (a < b)
		return a;
	return b;
}

// trộn 2 dãy phụ tạo dãy mới
void merge(int arr[], int temp1[], int n1, int temp2[], int n2, int k)
{
	int i1, i2, i;
	int k1, k2;
	int j1, j2;
	i = i1 = i2 = 0;
	j1 = j2 = 0;

	while (n2 > 0 && n2 > 0)
	{
        	// xác định độ dài từng dãy con 2 dãy phụ
		k1 = min(k, n1);
		k2 = min(k, n2);
        
        	// xét và trộn dãy con vào dãy
		if (temp1[i1 + j1] < temp2[i2 + j2])
		{
			arr[i++] = temp1[i1 + j1];
			j1++;
            
            	// trộn dãy con còn lại vào dãy
			if (j1 == k1)
			{
				for (; j2 < k2; j2++)
					arr[i++] = temp2[i2 + j2];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
		else
		{
			arr[i++] = temp2[i2 + j2];
			j2++;
            
            		// trộn dãy con còn lại vào dãy
			if (j2 == k2)												
			{
				for (; j1 < k1; j1++)
					arr[i++] = temp1[i1 + j1];
				i1 += k1; i2 += k2;
				j1 = j2 = 0;
				n1 -= k1; n2 -= k2;
			}
		}
	}
}

void mergeSort(int arr[], int n)
{
	int n1, n2;
	int i;
	int k;					
	int ik;															
	int *temp1 = new int[n];
	int *temp2 = new int[n];
	k = 1;

	do
	{
		i = n1 = n2 = 0;

		// chia mảng ra 2 mảng phụ
		while (i < n)													 
		{
			ik = 0;

			while (ik < k && i < n)
			{
				temp1[n1++] = arr[i++];
				ik++;
			}

			ik = 0;

			while (ik < k && i < n)
			{
				temp2[n2++] = arr[i++];
				ik++;
			}
		}

		merge(arr, temp1, n1, temp2, n2, k);

        	// tăng độ lớn tối đa dãy con
		k *= 2;															
	} while (k < n);
	
	delete[] temp1;
	delete[] temp2;
}

void main()
{
	int i, n;
	int *Array;

	printf("How many elements do you want to sort? ");
	scanf("%d", &n);

	Array = new int[n];

	for (i = 0; i < n; i++)
	{
		printf("Array[%d] = ", i);
		scanf("%d", &Array[i]);
	}

	mergeSort(Array, n);

	for (i = 0; i < n; i++)
	{
		printf("%d ", Array[i]);
	}

	delete[] Array;
}