Sắp xếp

Sắp xếp là một thao tác rất thường gặp khi lập trình, rất may, trong C#, Java, C++ ... đã cung cấp sẵn những hàm phục vụ vấn đề này, biết sử dụng thư viện này sẽ tiết kiệm dc kha khá thời gian lập trình, code lại trong sáng, dễ đọc. Bài viết này sẽ giới thiệu về cách thực hiện sắp xếp trong C#. Trừ khi yêu cầu quá đặc biệt, thì nhìn chung >95% các trường hợp, bạn ko cần phải tự viết các hàm sắp xếp cho dự án của mình.
1. Sắp xếp một danh sách hoặc mảng các đối tượng
Giả sử ta có đối tượng Person{int id; string name}. Ta muốn sau này có nhu cầu sắp xếp một danh sách/mảng các Person (List, IList hoặc Person[] và ...) tăng dần theo id, thì ta phải cho lớp Person này implement IComparable như sau :

public class Person : IComparable<Person>
{
  public int id;
  public string name;
  public Person(int inNo, string inName)
  {
      id = inNo;
      name = inName;
  }

  #region IComparable Members
  /// 

  /// Ham nay se duoc su dung khi goi ham sap xep cung cap boi .Net.
  /// Ngam dinh la sap xep tang dan, neu ham nay tra lai ket qua nhu sau :
  /// == 1 : this > other;
  /// == 0 : this == other;
  /// == -1 : this <>
  /// Neu co tinh muon sap xep giam dan thoi thi co the viet nhu sau :
  /// return -id.CompareTo(other.id);
  /// 
  /// 
  /// 
  public int CompareTo(Person other)
  {
      return id.CompareTo(other.id);
  }
  #endregion
}

Sau khi có lớp Person như trên, ta thực hiện sắp xếp như sau :
Với List, IList thì

List<Person> personList = new List<Person>();
// add them mot so doi tuong Person vao bien list noi tren
// code here

//////////////////////////////////////////////////////////////////////////
// thuc hien sap xep danh sach Person tang dan theo id cua Person
// ham Sort nay da duoc .Net cung cap san, dung QuichSort, co giao dien :
// public void Sort();
// ham Sort nay se tu dong su dung ham "public int CompareTo(Person other)"
// de thuc hien sap xep.
personList.Sort();
// done, danh sach da sap xep xong, tang dan theo id.

Với Array

//////////////////////////////////////////////////////////////////////////
Person[] personArr = new Person[5];
// add them mot so doi tuong Person vao bien array noi tren
// code here

//////////////////////////////////////////////////////////////////////////
// thuc hien sap xep mang Person tang dan theo id cua Person
// ham Sort nay da duoc .Net cung cap san, dung QuichSort, co giao dien :
// public void Sort();
// ham Sort nay se tu dong su dung ham "public int CompareTo(Person other)"
// de thuc hien sap xep.
Array.Sort(personArr);
// done, mang da sap xep xong, tang dan theo id.

Nếu muốn sắp xếp giảm dần thì như thế nào ?
Có 2 cách :
- Cách 1 : bạn sửa hàm CompareTo của Person (chỉ khi ta chỉ muốn sắp xếp giảm dần thôi), làm như thế nào thì mình đã comment trong hàm CompareTo bên trên rồi.
- Cách 2 : bạn thực hiện reverse lại, làm như sau

//////////////////////////////////////////////////////////////////////////
// neu muon lay danh sach giam dan, ta co the thuc hien theo 2 buoc
// thuc hien sap xep tang dan theo cach noi tren
personList.Sort(); // => de sap xep tang dan.
personList.Reverse(); // => de dao nguoc thu tu sap xep
// done, ta da co danh sach dc sap xep giam dan

Vậy lúc này bạn đã có thể sắp xếp theo id rồi, nhưng lúc khác bạn lại muốn có một danh sách sắp xếp theo name thì sao ?
Lúc này, bạn định nghĩa thêm một lớp để implement IComparer, lớp đó như sau :

public class PersonComparerIncreaseOnName: IComparer<Person>
{
  #region IComparer Members
  /// 

  /// Ham nay se duoc su dung khi thuc hien sap xep tang dan Person theo name.
  /// 
  /// 
  /// 
  /// 
  public int Compare(Person x, Person y)
  {
      return x.name.CompareTo(y.name);
  }
  #endregion
}

Và khi muốn gọi sắp xếp, ta gọi hàm sau :
Với List, IList thì

//////////////////////////////////////////////////////////////////////////
// thuc hien sap xep danh sach Person tang dan theo name cua Parson
// ham Sort nay da duoc .Net cung cap san, dung QuickSort, co giao dien :
// public void Sort(IComparer);
// ham Sort nay se tu dong su dung ham "public int Compare(Person x, Person y)"
// de thuc hien sap xep.
personList.Sort(new PersonComparerIncreaseOnName());
// done, danh sacg da sao xeo tang dan theo name.

Với Array thì

//////////////////////////////////////////////////////////////////////////
// thuc hien sap xep mang Person tang dan theo name cua Parson
// ham Sort nay da duoc .Net cung cap san, dung QuickSort, co giao dien :
// public void Sort(IComparer);
// ham Sort nay se tu dong su dung ham "public int Compare(Person x, Person y)"
// de thuc hien sap xep.
Array.Sort(personArr, new PersonComparerIncreaseOnName());
// done, mang da sap xep xong tang dan theo name.

Nếu tôi sử dụng một lớp có sẵn, tôi không thể khiến lớp đó implement IComparable thì sao ?
Ko vấn đề ji, bạn làm y hệt theo cách ta sắp xếp theo name, định nghĩa thêm một class implement IComparer như trên, và ta có thể sắp xếp như thường.

2. Sắp xếp một danh sách hoặc một mảng các Struct
Hoàn toàn ko có khác biệt gì với sắp xếp struct và class, vì trong C#, một struct cũng có thể implement các Interface giống hệt class, ví dụ sau là struct Person :

public struct Person : IComparable<Person>
{
  public int id;
  public string name;
  public Person(int inNo, string inName)
  {
      id = inNo;
      name = inName;
  }

  #region IComparable Members
  /// 

  /// Ham nay se duoc su dung khi goi ham sap xep cung cap boi .Net.
  /// Ngam dinh la sap xep tang dan, neu ham nay tra lai ket qua nhu sau :
  /// == 1 : this > other;
  /// == 0 : this == other;
  /// == -1 : this <>
  /// Neu co tinh muon sap xep giam dan thoi thi co the viet nhu sau :
  /// return -id.CompareTo(other.id);
  /// 
  /// 
  /// 
  public int CompareTo(Person other)
  {
      return id.CompareTo(other.id);
  }
  #endregion
}

Đối với sắp xếp trong Java hay C++ cũng có kỹ thuật tương tự.
That's all. Go Together In Development.