BÀI TẬP C#
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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.

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 Freetuts.net----\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 !!!

Cùng chuyên mục:

Cách dùng Stack (ngắn xếp) trong C#

Cách dùng Stack (ngắn xếp) trong C#

Mình sẽ giới thiệu về các đặc điểm, thuộc tính và phương thức của Stack…

Cách dùng Queue (hàng đợi) trong C#

Cách dùng Queue (hàng đợi) trong C#

Mình sẽ giới thiệu về các đặc điểm, thuộc tính, phương thức của Queue, cũng…

Cách dùng Hashtable (bảng băm) trong C#

Cách dùng Hashtable (bảng băm) trong C#

Cụ thể sẽ tìm hiểu Hashtable là gì? các đặc điểm của nó, cùng với…

Sự kiện Enter và Leave trong C# Winforms

Sự kiện Enter và Leave trong C# Winforms

Trong bài viết này mình sẽ hướng dẫn các bạn cách ...

Sự kiện KeyPress, KeyDown, KeyUp trong C# Winforms

Sự kiện KeyPress, KeyDown, KeyUp trong C# Winforms

Một câu hỏi được đặt ra là làm cách nào để có thể phát hiện…

Sắp xếp nổi bọt trong C# (Bubble Sort)

Sắp xếp nổi bọt trong C# (Bubble Sort)

Trong bài viết này mình sẽ hướng dẫn các bạn cách sắp ...

Cách in ra hình tam giác ký tự * trong C#

Cách in ra hình tam giác ký tự * trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách ...

Cách tính tổng các số chẵn từ 1 đến N trong C#

Cách tính tổng các số chẵn từ 1 đến N trong C#

Trước khi đi vào viết chương trình, chúng ta cùng tìm hiểu qua số chẵn…

Cách tính tổng các số lẻ từ 1 đến N trong C#

Cách tính tổng các số lẻ từ 1 đến N trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách tính tổng các lẻ…

Cách đếm số chữ số của một số nguyên trong C#

Cách đếm số chữ số của một số nguyên trong C#

Chúng ta cùng xem qua một số ví dụ để hiểu rõ hơn về chương…

Cách tính chu vi và diện tích hình tam giác trong C#

Cách tính chu vi và diện tích hình tam giác trong C#

Tam giác là một loại hình cơ bản trong hình học, có ba đỉnh là…

Cách tính chu vi và diện tích hình tròn trong C#

Cách tính chu vi và diện tích hình tròn trong C#

Trước khi đi vào viết chương trình tính chu vi và diện ..

Cách tính chu vi và diện tích hình chữ nhật trong C#

Cách tính chu vi và diện tích hình chữ nhật trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn ...

Cách xóa phần tử trùng lặp khỏi mảng trong C#

Cách xóa phần tử trùng lặp khỏi mảng trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách loại bỏ các ..

Cách tìm tất cả các chuỗi con của chuỗi đã cho trong C#

Cách tìm tất cả các chuỗi con của chuỗi đã cho trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách tìm ...

Cách xóa các ký tự trùng lặp khỏi chuỗi trong C#

Cách xóa các ký tự trùng lặp khỏi chuỗi trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách xóa các ký tự…

Đếm số lần xuất hiện của ký tự trong chuỗi trong C#

Đếm số lần xuất hiện của ký tự trong chuỗi trong C#

Trong bài viết này minh sẽ hướng dẫn các bạn cách đếm ...

Cách chuyển đổi nhị phân sang thập phân trong C#

Cách chuyển đổi nhị phân sang thập phân trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn cách chuyển đổi số ...

Cách chuyển đổi thập phân sang nhị phân trong C#

Cách chuyển đổi thập phân sang nhị phân trong C#

Số nhị phân là các con số có cơ số là 2. Các số nhị…

Cách tính tổng các chữ số của một số trong C#

Cách tính tổng các chữ số của một số trong C#

Trong bài viết này mình sẽ hướng dẫn các bạn ...

Top