Insertion Sort trong C#

Insertion Sort là thuật toán sắp xếp lấy từng phần tử và chèn nó vào vị trí đúng trong mảng. Quá trình tiếp tục cho đến khi mảng được sắp xếp.

Ví dụ

using System;

namespace InsertionSortDemo
{
    class Example
    {
        static void Main(string[] args)
        {
            int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
            int n = 10, i, j, val, flag;
            
            Console.WriteLine("Insertion Sort");
            Console.Write("Mảng ban đầu: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            for (i = 1; i < n; i++)
            {
                val = arr[i];
                flag = 0;
                
                for (j = i - 1; j >= 0 && flag != 1; )
                {
                    if (val < arr[j])
                    {
                        arr[j + 1] = arr[j];
                        j--;
                        arr[j + 1] = val;
                    }
                    else
                        flag = 1;
                }
            }
            
            Console.Write("\nMảng đã sắp xếp: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Kết quả

Insertion Sort
Mảng ban đầu: 23 9 85 12 99 34 60 15 100 1
Mảng đã sắp xếp: 1 9 12 15 23 34 60 85 99 100

Giải thích thuật toán

• Bắt đầu từ phần tử thứ 2 (i=1), coi phần tử đầu tiên đã sắp xếp
• Lưu giá trị hiện tại (val), dịch các phần tử lớn hơn sang phải
• Chèn val vào vị trí trống
• Biến flag dùng để dừng sớm khi đã tìm thấy vị trí đúng

Độ phức tạp: Tốt nhất O(n) (đã sắp xếp), Trung bình/Tệ nhất O(n²). Ổn định (stable). In-place.

Ưu điểm: Hiệu quả cho mảng nhỏ hoặc gần như đã sắp xếp. Đơn giản, ít ghi bộ nhớ.