Chương trình Selection Sort trong C#

Selection Sort là thuật toán sắp xếp tìm giá trị nhỏ nhất trong mảng cho mỗi lần lặp. Giá trị nhỏ nhất này được hoán đổi với phần tử hiện tại. Thủ tục lặp lại cho đến khi mảng được sắp xếp.

Ví dụ

using System;

public class Example
{
    static void Main(string[] args)
    {
        int[] arr = new int[10] { 56, 1, 99, 67, 89, 23, 44, 12, 78, 34 };
        int n = 10;
        
        Console.WriteLine("Selection Sort");
        Console.Write("Mảng ban đầu: ");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
        
        int temp, smallest;
        
        for (int i = 0; i < n - 1; i++)
        {
            smallest = i;
            
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[smallest])
                    smallest = j;
            }
            
            temp = arr[smallest];
            arr[smallest] = arr[i];
            arr[i] = temp;
        }
        
        Console.WriteLine();
        Console.Write("Mảng đã sắp xếp: ");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}

Kết quả

Selection Sort
Mảng ban đầu: 56 1 99 67 89 23 44 12 78 34
Mảng đã sắp xếp: 1 12 23 34 44 56 67 78 89 99

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

• Vòng lặp ngoài (i) duyệt qua từng vị trí
• Vòng lặp trong (j) tìm chỉ số phần tử nhỏ nhất từ i+1 đến cuối
• Hoán đổi phần tử nhỏ nhất với phần tử tại vị trí i

Độ phức tạp: Luôn O(n²) mọi trường hợp. Không ổn định. In-place.

Đặc điểm: Số lần hoán đổi tối thiểu (O(n)), phù hợp khi ghi bộ nhớ đắt đỏ. Tuy nhiên số lần so sánh luôn là n(n-1)/2.