Người quan tâm đến phần mềm, sẽ tự thiết kế luôn phần cứng cho phần mềm của họ. Alan Kay
STDIO Merge Sort là một trong những thuật toán sắp xếp có độ phức tạp trung bình và đạt hiệu quả về mặt thời gian. Do đó đối với các chương trình cần tối ưu, Merge Sort là một lựa chọn tốt. Bài viết này tôi sẽ giới thiệu và hướng dẫn các bạn về Merge Sort và cách cài đặt nó trên ngôn ngữ C++.
Nội dung bài viết

Giới thiệu

Merge Sort là một trong những thuật toán sắp xếp có độ phức tạp trung bình và đạt hiệu quả về mặt thời gian. Do đó đối với các chương trình cần tối ưu, Merge Sort là một lựa chọn tốt. Bài viết này tôi sẽ giới thiệu và hướng dẫn các bạn về Merge Sort và cách cài đặt nó trên ngôn ngữ C++. Bài viết phù hợp với lập trình viên mới bắt đầu và dành cho những người muốn tìm hiểu thêm về thuật toán sắp xếp Merge Sort.

Merge Sort

Ý Tưởng

Ý tưởng chúng ta sẽ chia mảng lớn thành những mảng con nhỏ hơn bằng cách chia đôi mảng lớn và chúng ta tiếp tục chia đôi các mảng con cho tới khi mảng con nhỏ nhất chỉ còn 1 phần tử. Sau đó chúng ta sẽ tiếng hành so sánh 2 mảng con có cùng mảng cơ sở (khi chúng ta chia đôi mảng lớn thành 2 mảng con thì mảng lớn đó chúng ta gọi là mảng cơ sở của 2 mảng con đó) khi so sánh chúng sẽ vừa sắp xếp vừa ghép 2 mảng con đó lại thành mảng cơ sở, chúng ta tiếp tục so sánh và ghép các mảng con lại đến khi còn lại mảng duy nhất thì đó là mảng đã được sắp xếp.

ss_1

Code

void Merge(int a[], int left, int mid, int right)
{
	int *temp; // Khoi tao mang tam de sap xep
	int i = left; // Vi tri phan tu dau tien cua mang con ben trai
	int j = mid + 1; // Vi tri phan tu dau tien cua mang con ben phai

	temp = new int[right - left + 1]; // Khoi tao so luong phan tu cua mang tam

	for (int k = 0; k <= right - left; k++)
	{
		// Kiem phan tu cua mang con ben trai va ben phai
		if (a[i] < a[j]) 
		{
			// Neu a[i] < a[j] thi copy phan tu ben trai vao mang tam
			temp[k] = a[i]; 
			i++; // Vi tri phan tu tiep theo cua mang
		}
		else // Nguoc lai copy phan tu cua mang con ben phai vao mang tam
		{
			temp[k] = a[j];
			j++; // Vi tri phan tu tiep theo cua mang
		}

		// Kiem tra mang con ben trai con phan tu nao khong
		if (i == mid + 1) 
		{
			// Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang tam
			while (j <= right)
			{
				k++;
				temp[k] = a[j];
				j++;
			}
			break;
		}

		// Kiem tra mang con ben phai con phan tu nao khong
		if (j == right + 1) 
		{
			// Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang tam
			while (i <= mid)
			{
				k++;
				temp[k] = a[i];
				i++;
			}
			break;
		}
	}

	for (int k = 0; k <= right - left; k++) // Chep mang tam vao mang chinh
		a[left + k] = temp[k];
	delete temp;
}

// left, right la bien trai va bien phai cua mang
void MergeSort(int a[], int left, int right)
{
	if (right > left)
	{
		int mid; // Phan tu o giua
		mid = (left + right) / 2;
		MergeSort(a, left, mid); // Goi de quy mang con ben trai
		MergeSort(a, mid + 1, right); // Goi de quy mang con ben phai
		Merge(a, left, mid, right); // Goi ham so sanh hai mang con
	}
}

int main()
{
	int a[10], n = 10;
	for (int i = 0; i < n; i++)
	{
		cout << "Nhap so " << i + 1 << ": ";
		cin >> a[i];
	}
	MergeSort(a, 0, 9);
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	return 0;
}

Download mã nguồn

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

Ưu và nhược điểm

  • Ưu điểm: Sắp sếp nhanh hơn so với các thuật toán cơ bản (Insertion Sort, Selection Sort, Interchage Sort), nhanh hơn Quick Sort trong một số trường hợp.
  • Nhược điểm: thuật toán khó cài đặt, không nhận dạng được mảng đã được sắp.
  • Hiệu quả được tính bằng công thức O(n log n).

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