Monthly Archives: August 2012

[C#] Sử dụng IComparable và IComparer để sắp xếp dữ liệu

Trong C#, khi bạn làm việc với một nhóm các đối tượng trong một mảng, một danh sách v.v. thì có một yêu cầu thường gặp là sắp xếp danh sách đó. Bạn có thể dễ dàng sắp xếp các phần tử với các kiểu cơ bản như int, float, string v.v. nhờ sử dụng phương thức Sort() có sẵn trong hầu hết các lớp liên quan đến Collection. Nhưng đối với những kiểu dữ liệu do người dùng tự định nghĩa thì bạn cần phải chỉ định rõ cách các đối tượng này được so sánh với nhau như thế nào, đơn giản là bởi vì muốn sắp xếp được thì trước tiên ta phải so sánh được.

Để cho các bạn dễ hiểu thì chúng ta sẽ xét một ví dụ sau: Tạo một danh sách các số nguyên và sắp xếp danh sách đó theo thứ tự tăng dần. Yêu cầu sử dụng List<> để chứa các số nguyên đó và sử dụng phương thức Sort() có sẵn trong List<>. Đoạn code theo yêu cầu này có thể là như sau:

using System.Collections.Generics;
public class ListDemo {
  public static void Main(){
    List&lt;int&gt; intList = new List&lt;int&gt;();
    //Thêm ngẫu nhiên một vài số vào danh sách
    intList.Add(42); 
    intList.Add(10);
    intList. Add(25); 
    //Sắp xếp danh sách này bằng phương thức Sort()
    intList.Sort();
    foreach(int number in intList)
       Console.WriteLine(number);
  }
}

Như các bạn thấy, chúng ta đã tận dụng phương thức Sort() có sẵn trong List<> để sắp xếp các số nguyên này. Bởi vì int là một kiểu dữ liệu cơ bản nên trình thực thi hoàn toàn biết cách sắp xếp thứ tự các phần tử từ bé đến lớn.

Ví dụ tiếp theo có phần phức tạp hơn, đó là thay vì danh sách các số nguyên thì chúng ta sẽ làm việc với danh sách các đối tượng của lớp Person như sau:

public class Person
{
   public int Age{get;set;}
   public string Name{get;set;}
}

Việc tạo và thêm phần tử cho danh sách các đối tượng kiểu Person này cũng không có gì là khó khăn.

using System.Collections.Generics;
public class ListDemo {
  public static void Main(){
    List&lt;Person&gt; personList = new List&lt;Person&gt;();
    personList.Add(new Person{Age=10, Name=&quot;John&quot;});
    personList.Add(new Person{Age=15, Name=&quot;Ann&quot;});
    personList.Add(new Person{Age=8, Name=&quot;Kevin&quot;});
    personList.Sort(); //Lỗi runtime ở đây
    foreach (var item in personList){
      Console.WriteLine(item.Name + &quot;:&quot; + item.Age);
    }
    Console.ReadKey(true);
  }
}

Khi chúng ta chạy chương trình thì sẽ nhận được thông báo lỗi “Failed to compare two elements in the array” tại phương thức Sort(), đơn giản là bởi vì trình thực thi sẽ không biết cách làm thế nào để so sánh các đối tượng kiểu Person này với nhau (cho 2 đối tượng kiểu Person là A và B, sẽ sắp xếp A trước B hay B trước A?).

Phương thức Sort() của List<> sẽ chỉ có thể hoạt động được đối với những class có cài đặt interface IComparable hoặc nếu không thì phải có một lớp khác đảm nhận công việc so sánh bằng cách cài đặt interface IComparer. Nói cách khác, các class này phải có một phương thức để chỉ rõ cách so sánh hai đối tượng của class đó là như thế nào.

IComparable có một phương thức duy nhất là CompareTo(). Tham số nhận vào là một kiểu object hoặc trong trường hợp bạn sử dụng interface IComparable<> thì tham số truyền vào là kiểu dữ liệu của lớp cài đặt interface đó. Như vậy, lớp Person của chúng ta lúc này sẽ là:

public class Person : IComparable&lt;Person&gt;
{
   public int Age {get;set;}
   public string Name{get;set;}
   public int CompareTo(Person other){
      return this.Age.CompareTo(other.Age);
   }
}

Phương thức CompareTo() sẽ dựa vào giá trị trả về để biết được kết quả của phép so sánh. Giá trị trả về nhỏ hơn 0 nghĩa là đối tượng hiện tại sẽ nhỏ hơn đối tượng other, giá trị trả về là 0 thì hai đối tượng bằng nhau, còn nếu giá trị trả về lớn hơn 0 thì đối tượng hiện tại lớn hơn đối tượng other. Ở trên, thay vì phải dùng các câu lệnh if…else để trả về giá trị theo quy định thì chúng ta đã tận dụng lại phương thức CompareTo() có sẵn trong các kiểu dữ liệu cơ bản (thuộc tính Age thuộc kiểu Integer). Hiện tại, chúng ta đang cài đặt cho lớp Person này sẽ sắp xếp các đối tượng theo thuộc tính Age. Đối với cách so sánh phức tạp hơn, chúng ta cũng chỉ cần cài đặt nó trong phương thức CompareTo(), miễn sao giá trị trả về phản ánh đúng thứ tự mà chúng ta mong muốn.

Sau khi đã chỉnh sửa lớp Person như trên thì ta đã có thể sử dụng được phương thức Sort() của List<> để sắp xếp các đối tượng kiểu Person. Kết quả xuất ra của chúng ta là như sau:


Tuy nhiên, việc cài đặt IComparable có một hạn chế đó là chúng ta chỉ có thể quy định cho lớp Person này 1 cách sắp xếp duy nhất. Giả sử chúng ta muốn cùng lúc vừa có thể sắp xếp danh sách personList theo tên, vừa có thể sắp xếp theo tuổi thì phải làm sao? Khi đó chúng ta cần đến sự trợ giúp của một interface khác: IComparer.

Khác với IComparable được cài đặt ngay trong lớp của đối tượng mà bạn muốn sắp xếp, Icomparer sẽ được cài đặt ở một lớp riêng, lớp này đóng vai trò là một Bộ so sánh, khi cần sắp xếp với tiêu chí nào thì ta chỉ cần chọn một Bộ so sánh phù hợp là được (Hãy tưởng tượng bạn đang có 10 thùng hàng và có 2 loại máy sắp xếp, nếu cho 10 thùng hàng này qua máy 1 thì các thùng hàng sẽ được sắp xếp theo kích thước, còn nếu cho 10 thùng hàng này qua máy 2 thì các thùng hàng sẽ được sắp xếp theo khối lượng. Máy 1 và 2 ở đây đóng vai tròng giống như các Comparer, mỗi máy sẽ có cách sắp xếp riêng mà khi cần sử dụng thì gọi tới nó).

Chúng ta sẽ bắt đầu với việc cài đặt một Bộ so sánh cho phép so sánh hai đối tượng kiểu Person theo thuộc tính Age và một Bộ so sánh theo thuộc tính Name

public class PersonAgeComparer : IComparer&lt;Person&gt;
{
   public int Compare(Person x, Person y){
     return x.Age.CompareTo(y.Age);
   }
}

public class PersonNameComparer : IComparer&lt;Person&gt;
{
   public int Compare(Person x, Person y){
     return x.Name.CompareTo(y.Name);
   }
}

Tương tự như phương thức CompareTo() của interface IComparable, phương thức Compare() trong interface IComparer cũng dựa vào kết quả trả về để biết thứ tự của hai đối tượng. Lưu ý rằng interface IComparable được cài đặt trực tiếp ngay trên lớp các đối tượng trong danh sách, còn IComparer thì được cài đặt trên một lớp riêng (Vì thế nó sẽ có hai tham số trong phương thức Compare()).

Đã có hai lớp Comparer như trên, khi chúng ta muốn sử dụng bộ so sánh nào khi sắp xếp với phương thức Sort() thì chỉ việc tạo ra một đối tượng của lớp Comparer đó. Ví dụ như với danh sách personList đã tạo ra, chúng ta sẽ sắp xếp danh sách này theo tuổi như sau:

using System.Collections.Generics;
public class ListDemo {
  public static void Main(){
    List&lt;Person&gt; personList = new List&lt;Person&gt;();
    personList.Add(new Person{Age=10, Name=&quot;John&quot;});
    personList.Add(new Person{Age=15, Name=&quot;Ann&quot;});
    personList.Add(new Person{Age=8, Name=&quot;Kevin&quot;});
    personList.Sort(new PersonAgeComparer());
    foreach (var item in personList){
      Console.WriteLine(item.Name + &quot;:&quot; + item.Age);
    }
    Console.ReadKey(true);
  }
}

Còn nếu bạn muốn sắp xếp theo tên thì sao? Rất dễ dàng, chỉ cần thay đối tượng tương ứng trong tham số của phương thức Sort()

personList.Sort(new PersonNameComparer());

Làm theo cách này, bạn có thể cài đặt nhiều cách sắp xếp khác nhau trên một kiểu dữ liệu. Khi nào cần cách sắp xếp nào, ta chỉ việc gọi cách sắp xếp đó.

lovelytigon