Lập trình như tự đá vào mặt mình, sớm hay muộn mũi bạn cũng sẽ chảy máu. Jim McCarthy
STDIO Thuật toán Merge Sort là thuật toán có độ phức tạp trung bình nhưng đạt hiệu quả trong nhiều trường hợp. Bài viết sẽ hướng dẫn chi tiết về hiện thực giải thuật này. Nhằm đảm bảo bạn có thể hiểu tốt và thực thi được, bài viết sẽ sử dụng ngôn ngữ và các khái niệm cơ bản nhất của lập trình C/C++.
Nội dung bài viết

Giới thiệu

Trong các thuật toán sắp xếp, Merge sort là thuật toán không quá khó nhưng đạt hiệu quả cao trong nhiều trường hợp. Nhận thấy được hiệu quả mà nó mang lại, tác giả xin được sử dụng vốn kiến thức mà mình tìm hiểu được để hiện thực lại thuật toán này.

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)).

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

Trộn từng cặp dãy con trong hai dãy phụ vào dãy ban đầu ta sẽ được dãy mới có các phần tử tương tự dãy ban đầu nhưng có trật tự thay đổi, số đoạn dãy con giảm dần, ít nhất là giảm đi một nửa theo hướng sắp xếp của người viết. Tuần tự tăng dần độ lớn của dãy con và thực hiện tương tự các bước trên cho đến khi độ lớn của dãy con vượt quá số phần tử của dãy ban đầu.

Nếu bạn chưa hiểu tư tưởng của Merge sort. Đừng lo lắng, chúng ta sẽ đi đến ví dụ hình ảnh sau.

Minh hoạ Merge sort

Hiện thực thuật toán Merge sort theo phân tích trên.

#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;
}

Download mã nguồn

Bạn có thể download mã nguồn tại đây.

Bạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG