Sắp xếp mảng số nguyên bằng thuật toán Insertion Sort trong C#

Để viết thuật toán Insertion Sort để sắp xếp một mảng số nguyên trong C#, bạn có thể làm theo các bước sau:

1. Khởi tạo mảng: Tạo một mảng số nguyên cần được sắp xếp.
2. Thuật toán Insertion Sort: Thực hiện các bước của thuật toán Insertion Sort để sắp xếp mảng.

Thuật toán Insertion Sort

Insertion Sort là một thuật toán sắp xếp đơn giản hoạt động bằng cách xây dựng dần dần mảng đã sắp xếp. Đối với mỗi phần tử, thuật toán chèn nó vào đúng vị trí trong mảng đã sắp xếp.

Code C# cho Insertion Sort

using System;

public class InsertionSortExample
{
    // Phương thức để thực hiện Insertion Sort
    public static void InsertionSort(int[] array)
    {
        int n = array.Length;
        for (int i = 1; i < n; i++)
        {
            int key = array[i];
            int j = i - 1;

            // Di chuyển các phần tử của array[0..i-1], mà lớn hơn key, đến vị trí trước một vị trí so với vị trí hiện tại của chúng
            while (j >= 0 && array[j] > key)
            {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    // Phương thức để in mảng ra console
    public static void PrintArray(int[] array)
    {
        foreach (int item in array)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }

    public static void Main(string[] args)
    {
        // Tạo một mảng số nguyên
        int[] numbers = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("Mảng trước khi sắp xếp:");
        PrintArray(numbers);

        // Gọi phương thức InsertionSort để sắp xếp mảng
        InsertionSort(numbers);

        Console.WriteLine("Mảng sau khi sắp xếp:");
        PrintArray(numbers);
    }
}

Giải thích

1. Khởi tạo mảng:

   int[] numbers = { 64, 34, 25, 12, 22, 11, 90 };
   

2. Phương thức InsertionSort:

   • n là độ dài của mảng.
   • Vòng lặp ngoài bắt đầu từ phần tử thứ hai của mảng (chỉ số 1) và lặp qua từng phần tử.
   • key lưu giữ giá trị của phần tử hiện tại.
   • Vòng lặp trong di chuyển các phần tử của mảng từ phần đã sắp xếp (trước chỉ số i) mà lớn hơn key, đến vị trí trước một vị trí so với vị trí hiện tại của chúng.
   • Sau khi tìm được vị trí chính xác, phần tử key được chèn vào mảng.

3. Phương thức PrintArray:

   • In từng phần tử của mảng ra console.

4. Trong phương thức Main:

   • Mảng ban đầu được in ra.
   • Gọi phương thức InsertionSort để sắp xếp mảng.
   • Mảng sau khi sắp xếp được in ra.

Kết quả khi chạy chương trình

Khi chạy chương trình, bạn sẽ thấy mảng được in ra trước và sau khi sắp xếp:

Mảng trước khi sắp xếp:
64 34 25 12 22 11 90 
Mảng sau khi sắp xếp:
11 12 22 25 34 64 90