STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ

    Merge Sort

    Giới thiệu và hướng dẫn giải thuật Merge Sort và code Merge Sort với C/C++.
    22/08/2015
    17/08/2020
    3 phút đọc
    Merge Sort

    Merge Sort hay còn gọi là thuật toán sắp xếp trộn 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. Đố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.

    Thuật toán Merge Sort

    Ý tưởng

    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à tiếp tục chia đôi các mảng con cho đến khi mảng con nhỏ nhất chỉ còn 1 phần tử.

    So sánh 2 mảng con có cùng mảng cơ sở (khi chia đôi mảng lớn thành 2 mảng con thì mảng lớn đó gọi là mảng cơ sở của 2 mảng con đó).

    Khi so sánh chúng vừa sắp xếp vừa ghép 2 mảng con đó lại thành mảng cơ sở, 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, đó là mảng đã được sắp xếp.

    Thuật toán Merge Sort.

    Code mẫu Merge Sort

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

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

    Ưu điểm

    Nhược điểm

    • Thuật toán khó cài đặt, không nhận dạng được mảng đã được xếp.
    • Hiệu quả được tính bằng công thức O(n log n).
    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021