Sắp xếp trộn trong C# (Merge Sort)

Trong bài viết này mình sẽ hướng dẫn các bạn cách sắp xếp các phần tử trong mảng sử dụng phương pháp sắp xếp trộn (Merge Sort) trong C#. Chúng ta sẽ cùng tìm hiểu sắp xếp trộn là gì và cách triễn khai nó trong C#.

1. Giới thiệu sắp xếp trộn trong C#?

Sắp xếp trộn trong C# là một thuật toán được sắp xếp dựa trên giải thuật Divide and Conquer (chia để trị).

Thuật toán chia mảng thành hai nữa rồi sắp xếp trên từng nữa một. Sau đó kết hợp chúng lại thành một một mảng hoàn chỉnh đã được sắp xếp.

Ví dụ: Giả sử ta có một mảng gồm các phần tử như sau: {38; 27; 43; 3; 9; 82; 10}. Khi đó thuật toán sẽ hoạt động như hình dưới.

Bài viết này được đăng tại [kiso.vn]

bai23 02 png

Bước 1: Thực hiện chia nhỏ mảng thành nhiều phần khác nhau.

Như các bạn đã thấy thì lúc đầu mình đã chia mảng thành hai phần, một bên 4 số một bên 3 số. Sau đó tiếp tục chia 4 số thành hai phần mỗi bên hai số. Cứ như vậy cho đến khi được kết quả như dòng số 4.

Bước 2: Thực hiện so sánh và kết hợp thành một mảng hoàn chỉnh đã sắp xếp.

Ta thực hiện so sánh và sắp xếp các phần tử cho đúng vị trí như các bước ở dòng số 5, 6, 7.

Sau khi kết hợp ta sẽ được kết quả đã sắp xếp ở dòng số 8.

2. Ví dụ: Sắp xếp bằng Merge Sort trong C#

Trong chương trình dưới đây mình thực hiện tạo hai hàm là MergeMethod()SortMethod(). Hàm MergeMethod() dùng để chia mảng thành các phần nhỏ để so sánh. Hàm SortMethod() dùng để so sánh và sắp xếp các phần nhỏ đã chia và kết hợp chúng lại thành một mảng hoàn chỉnh sau khi đã sắp xếp.

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            //khai báo biến count để đếm số lần lặp khi sắp xếp
            int n;
            //nhập vào số lượng phần tử của mảng, nếu <= 0 thì nhập lại
            do
            {
                Console.Write("nNhap vao so luong phan tu cua mang: ");
                n = int.Parse(Console.ReadLine());
            } while (n <= 0);
            //khai báo mảng intArray
            int[] intArray = new int[n];
            Console.WriteLine("Nhap vao cac phan tu cua mang: ");
            //sử dụng vòng lặp for để nhập các phần tử cho mảng
            for (int i = 0; i < intArray.Length; i++)
            {
                intArray[i] = int.Parse(Console.ReadLine());
            }
            //gọi hàm sắp xếp SortMethod và truyền vào các tham số tương ứng
            SortMethod(intArray, 0, n - 1);
            Console.Write("Cac phan tu sau khi sap xep: ");
            //in mảng sau khi sắp xếp
            foreach (int item in intArray)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();

            Console.WriteLine("n----Chuong trinh nay duoc dang tai Kiso.vn----n");
            Console.ReadLine();
        }
        //hàm chia các phần tử trong mảng
        static public void MergeMethod(int[] numbers, int left, int mid, int right)
        {
            int[] temp = new int[25];
            int i, left_end, num_elements, tmp_pos;
            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);
            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left] <= numbers[mid])
                    temp[tmp_pos++] = numbers[left++];
                else
                    temp[tmp_pos++] = numbers[mid++];
            }
            while (left <= left_end)
                temp[tmp_pos++] = numbers[left++];
            while (mid <= right)
                temp[tmp_pos++] = numbers[mid++];
            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }
        }
        //hàm sắp xếp các phần tử sao khi chia
        static public void SortMethod(int[] numbers, int left, int right)
        {
            int mid;
            if (right > left)
            {
                mid = (right + left) / 2;
                SortMethod(numbers, left, mid);
                SortMethod(numbers, (mid + 1), right);
                MergeMethod(numbers, left, (mid + 1), right);
            }
        }
    }
}

Kết quả:

bai23 01 png

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử trong mảng bằng phương pháp sắp xếp trộn (Merge Sort) trong C#. Chúc các bạn thực hiện thành công !!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *