Sắp xếp trong .NET

Hai bài trước tự viết thuật toán sắp xếp để hiểu bên trong. Khi đi làm, bạn gần như luôn dùng method có sẵn của .NET vì nhanh, đã được kiểm kỹ và gọn. Điều cần biết là nên chọn method nào, và method nào đổi luôn list gốc.

Khái niệm

⚖️ Sắp xếp ổn định (stable sort): các phần tử bằng nhau theo tiêu chí sắp xếp vẫn giữ đúng thứ tự ban đầu của chúng.

Cả hai đều O(n log n). OrderBy đã gặp ở bài LINQ cơ bản của khoá C# Core. Nếu đã học khoá SQL, nó giống ORDER BY trong câu truy vấn.

Ví dụ

var products = new List<Product>
{
    new Product("Vở", 12000m),
    new Product("Bút bi", 5000m),
    new Product("Thước", 7000m)
};

products.Sort((a, b) => a.Price.CompareTo(b.Price));
foreach (Product p in products)
{
    Console.WriteLine($"{p.Name}: {p.Price}");
}

class Product
{
    public string Name { get; }
    public decimal Price { get; }

    public Product(string name, decimal price)
    {
        Name = name;
        Price = price;
    }
}

• Sort nhận lambda so hai phần tử a, b. Kết quả âm nghĩa là a đứng trước, dương là b đứng trước, 0 là bằng nhau.
• a.Price.CompareTo(b.Price) trả về đúng số âm, 0 hoặc dương như vậy.
• Muốn giảm dần thì đổi chỗ: b.Price.CompareTo(a.Price).
• Sort đổi thứ tự ngay trong products, in ra Bút bi, Thước, Vở.

Thử ngay

Hai món cùng giá 5000. Dùng OrderBy và xem món nào đứng trước:

var items = new List<Product>
{
    new Product("Vở", 12000m),
    new Product("Bút chì", 5000m),
    new Product("Thước", 7000m),
    new Product("Bút bi", 5000m)
};

var byPrice = items.OrderBy(p => p.Price);
foreach (Product p in byPrice)
{
    Console.WriteLine($"{p.Name}: {p.Price}");
}

Đoán trước khi chạy: "Bút chì" và "Bút bi" cùng giá. Món nào in ra trước?

Bút chì: 5000
Bút bi: 5000
Thước: 7000
Vở: 12000

Lỗi hay gặp

Gọi OrderBy rồi tưởng list đã đổi. OrderBy trả về dãy mới, list gốc giữ nguyên. Không dùng dãy trả về thì coi như chưa sắp xếp.

// SAI — items vẫn giữ thứ tự cũ
items.OrderBy(p => p.Price);
Console.WriteLine(items[0].Name);   // Vở

// ĐÚNG — dùng dãy mà OrderBy trả về
var sorted = items.OrderBy(p => p.Price).ToList();
Console.WriteLine(sorted[0].Name);   // Bút chì

Tóm tắt

• list.Sort và Array.Sort sắp xếp tại chỗ, O(n log n), không ổn định.
• OrderBy, ThenBy trả về dãy mới và ổn định.
• Lambda so sánh trả số âm, 0 hoặc dương. CompareTo làm sẵn việc đó.
• Sort của .NET kết hợp nhiều thuật toán, dùng sắp xếp chèn cho đoạn ngắn.