Các vấn đề sắp xếp trong C#....

Từ rất lâu rồi, các thuật toán sắp xếp trong Tin đã trở thành kinh điển .....
Từ khi còn học C, chúng ta đã quen với các Merge Sort, Bubble Sort, Quick Sort v.v... Và mỗi lần sắp xếp trên mảng lại phải 2 vòng for quen thuộc:

for (int i=0; i< ...; i++)
   for (int j=0; j< ...; j++)
   { 
        ...your Algorithm ...
   }

Theo thời gian, ngôn ngữ lập trình được tiến hóa, nhiều ngôn ngữ mới ra đời, hỗ trợ cho programmer nhiều hơn, đến với C#:

ArrayList arrList = new ArrayList();
arrList.Sort()

Method Sort trên được thực hiện bằng thuật toán QuickSort. Với một dãy các số nguyên { 4, -9, 7, 10, 0, -3, 100 } thì với method Sort, ta sẽ dễ dàng sắp xếp ra được kết quả { -9, -3, 0, 4, 7, 10, 100 }. Vấn đề xem ra chẳng có gì để bàn .... Tuy nhiên, ví dụ trên là một mảng các số nguyên ( kiểu int ), trên thực tế, ta lại thường phải sắp xếp (hoặc tìm kiếm) trên một mảng các đối tượng phức hợp khác ( chẳng hạn như một tập hợp các đối tượng là học sinh, một danh sách các cuốn sách ...etc...), thì sao ??? Một cách giải quyết đơn giản nhất mà chúng ta thường làm là theo cách truyền thống, cứ 2 vòng for và so sánh từng đối tượng theo thuật toán tuần tự .... ( không phụ thuộc ngôn ngữ lập trình ) ! Tuy nhiên, ta hãy biết tận dụng method Sort() của C#.... Ở đây, tôi muốn sử dụng đặc thù hướng đối tượng và sức mạnh của lập trình gốc giao diện của ngôn ngữ C# để giải quyết vấn đề .... Trước tiên, ta hãy tìm hiểu cụ thể phương thức Sort()... Phương thức này được C# cài đặt để sắp xếp các phần tử trong một mảng (ArrayList, SortedList, v.v...). Vậy làm sao method Sort() biết sắp xếp các phần tử như thế nào? Để có thể sắp xếp được bằng Sort() thì mỗi phần tử trong mảng phải là một đối tượng... "có thể so sánh được", hay nói cách khác là chúng ta phải chỉ ra cách so sánh chúng như thế nào? Vậy làm sao để đối tượng trong mảng của chúng ta "có thể so sánh" được? Rất mạnh, C# cung cấp một giao diện (interface) có tên là IComparable. Giao diện này cung cấp một method abstract chung có đặc tả như sau:

public int CompareTo(object obj);

Phương thức Sort() của ArrayList sẽ duyệt qua tất cả các phần tử của nó(có kiểu IComparable), dựa vào method CompareTo() ở trên của từng phần tử để tự so sánh và sắp xếp lại theo đặc tả sẽ được chúng ta chỉ ra cụ thể trong khi override lại method CompareTo()........ Vậy, để đối tượng của chúng ta ...."có thể so sánh được" (comparable), chúng ta hãy cho chúng kế thừa lại interface IComparable !

class MyClass : IComparable  //kế thừa interface
{
}

Thực hiện Compare

class MyClass : IComparable  //kế thừa interface
{
    //cài đặt đè method Compare
    public int CompareTo(object obj)
    {
    }
}

Một ví dụ để minh hoạ cụ thể : Giả sử, chúng ta có một danh sách các nhân viên, mỗi nhân viên có các thuộc tính cơ bản là : Số CMND, Tên, và Tuổi. Hãy sắp xếp danh sách đó lại theo thứ tự Tuổi tăng dần xem sao..... Chúng ta sẽ tạo class nhân viên:

class People : IComparable    //kế thừa interface
{
   //private
   private string _CMND;
   private string _Name;
   private int _Age;

   //constructor
   public People() : this ("0", "noname", 0)
   {
   }

   public People(string CMND, string Name, int Age) 
   {
     this._CMND = CMND;
     this._Name = Name;
     this._Age = Age;
   }

   //Property
   public string Name
   {
      get { return this._Name; }
   }


   //IComparable: chỉ ra cách so sánh đối tượng People
   public int CompareTo(object obj)
   {
      if (obj is People)
      {
 People peo = (People)obj;
 return this._Age.CompareTo(peo._Age); //so sánh theo tuổi
      }
      throw new InvalidCastException("Khong the so sanh People");
   }

}

Tạo danh sách các nhân viên để sắp xếp:

//tạo 4 people
ArrayList arrList = new ArrayList();
People[] arr = new People[4] {
                new People("0123456789", "Trân Hồng", 22),
 new People("1234567890", "Minh Nhã", 23),
 new People("2345678901", "Văn Nguyễn", 19),
 new People("3456789012", "Minh Nguyệt", 15) 
 };
   

//lưu vào ArrayList
//lưu vào ArrayList
for (int i=0; i
Vậy, trước khi sắp xếp, ta có thứ tự danh sách là: 
{"Trân Hồng", "Minh Nhã", "Văn Nguyễn", "Minh Nguyệt" }
Và thực hiện sắp xếp:
//sắp xếp theo tuổi
arrList.Sort();

Xuất kết quả sau khi sắp xếp (theo tuổi)
string result = "";
for (int i=0; i
Kết quả mà ta nhận được sau khi sắp xếp là: 



{"Minh Nguyệt", "Văn Nguyễn", "Trân Hồng", "Minh Nhã" }



Tương tự, rất hay, ta áp dụng cho các thuật toán tìm kiếm trên mảng bằng phương thức ArrayList.BinarySearch() .....

Archive