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

Bubble Sort là thuật toán sắp xếp đơn giản dựa trên so sánh: lặp qua mảng, so sánh cặp phần tử liền kề, hoán đổi nếu sai thứ tự. Phần tử lớn nhất "nổi" lên cuối sau mỗi pass.

Độ phức tạp

Mã nguồn (có tối ưu dừng sớm)

using System;

namespace BubbleSort {
    class MySort {
        static void Main(string[] args) {
            int[] arr = { 78, 55, 45, 98, 13 };
            
            Console.WriteLine("Mảng gốc: " + string.Join(", ", arr));
            
            BubbleSort(arr);
            
            Console.WriteLine("Mảng sau sắp xếp: " + string.Join(", ", arr));
            Console.Read();
        }
        
        static void BubbleSort(int[] arr) {
            int n = arr.Length;
            bool swapped;
            
            for (int i = 0; i < n - 1; i++) {
                swapped = false;
                
                // Pass i: đẩy phần tử lớn nhất về cuối phần chưa sắp xếp
                for (int j = 0; j < n - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        // Hoán đổi
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        swapped = true;
                    }
                }
                
                // Nếu không có hoán đổi nào → đã sắp xếp xong
                if (!swapped) break;
            }
        }
    }
}

Kết quả

Mảng gốc: 78, 55, 45, 98, 13
Mảng sau sắp xếp: 13, 45, 55, 78, 98

Minh họa từng pass (arr = [78, 55, 45, 98, 13])

Pass 1: [55, 45, 78, 13, 98]  (98 nổi lên cuối)
Pass 2: [45, 55, 13, 78, 98]  (78 nổi lên vị trí倒数第二)
Pass 3: [45, 13, 55, 78, 98]  (55)
Pass 4: [13, 45, 55, 78, 98]  (45) - done

Cách dùng built-in (khuyên dùng production)

// In-place sort
Array.Sort(arr);           // QuickSort (introspective sort)
List list = new List(arr);
list.Sort();               // QuickSort

// LINQ (trả về mảng mới)
var sorted = arr.OrderBy(x => x).ToArray();

Lưu ý

• Bubble Sort chỉ dùng cho giáo dục hoặc mảng rất nhỏ (n < 50) gần đã sắp xếp.
• Production: luôn dùng Array.Sort / List.Sort / LINQ — introspective sort (QuickSort + HeapSort + InsertionSort hybrid), ổn định, nhanh.
• Stable sort (giữ thứ tự phần tử bằng nhau): OrderBy (LINQ) stable, Array.Sort không stable.