Thuật toán sắp xếp: Selection Sort (chọn trực tiếp)

Selection Sort là một thuật toán sắp xếp tương đối dễ hiểu. Ý tưởng chính vẫn là đổi chỗ những cặp nghịch thế, tuy nhiên cái hay là ở chỗ Selection Sort tìm vị trí chứa phần tử nhỏ nhất để đổi chỗ với phần tử đang xét chứ không đổi tất cả các cặp nghịch thế như Bubble Sort hay Interchange Sort.

Ý tưởng
Xét phần tử đầu tiên của dãy. Tìm phần tử nhỏ nhất trong các phần tử còn lại. Hoán đổi phần tử đầu tiên với phần tử nhỏ nhất này, ta được phần tử đầu tiên có vị trí đúng. Bỏ qua phần tử vừa được xét, tiếp tục xét đến phần tử kế tiếp và thực hiện đến hết dãy.

Cài đặt trong C++

int min, i, j; //min là chỉ số phần tử nhỏ nhất
for(i = 0; i < n-1; i++)
{
   min = i;
   for(j = i+1; j < n; j++)
      if(a[j] < a[min])
         min = j; //tìm min trong các phần tử còn lại
   if(min != i)
     swap(a[i], a[min]); //đổi chỗ nếu tìm thấy min
}

Minh họa
Nguồn: Wikipedia

Đánh giá
Về số phép so sánh, ở lượt xét thứ i luôn có (n-i) phép so sánh để tìm min và không phụ thuộc tình trạng ban đầu của dãy nên số phép so sánh ước lượng là: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số lần hoán vị ở trường hợp tốt nhất là 0.
Trường hợp xấu nhất là: 3n(n-1)/2.

Độ phức tạp là: O(n²)

Thuật toán sắp xếp: Bubble Sort (sắp xếp nổi bọt)

Bubble Sort là một thuật toán sắp xếp kiểu so sánh rất đơn giản và dễ hiểu. Ý tưởng chính của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Ý tưởng
Đối với Bubble Sort, ta chọn cặp bằng cách xét hai phần tử kế cận nhau.
Có 2 dạng sắp xếp của Bubble Sort

Dạng 1: Sắp từ đầu đến cuối
Xuất phát từ đầu dãy, ta so sánh và đổi chỗ các cặp nghịch thế đến cuối dãy để đưa phần tử lớn nhất về cuối dãy. Khi đó chỉ việc xét các phần tử còn lại trong dãy và lặp lại các bước để sắp xếp.

Dạng 2: Sắp từ cuối lên đầu
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử nghịch thế để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

Cài đặt theo ngôn ngữ C++
Dạng 1: Sắp từ đầu đến cuối

int i, j;
for (i = n-1 ; i > 0; i--)
   for (j = 0; j < i; j++)
      if (a[j] > a[j+1]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chổ

Dạng 2: Sắp từ cuối lên đầu

int i, j;
for (i = 0; i < n-1; i++)
   for (j = n-1; j > i; j--)
      if (a[j-1] > a[j]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chỗ

Minh họa
Dưới đây là minh hoạ cho thuật toán Bubble Sort theo dạng 1 (nguồn: Wikipedia)

Đánh giá
Số phép so sánh không phụ thuộc vào tình trạng ban đầu của dãy. Có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số phép hoán vị (3 phép gán) phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)

Thuật toán sắp xếp: Interchange Sort (đổi chỗ trực tiếp)

Để sắp xếp một dãy, có nhiều cách làm khác nhau. Trong bài viết này mình sẽ nói về Interchange Sort, hay còn gọi là thuật toán sắp xếp đổi chỗ trực tiếp.

Ý tưởng
Ý tưởng của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Để bắt cặp tất cả các phần tử trong dãy, ta dùng 2 vòng lặp. Vòng lặp ngoài sẽ chạy từ đầu dãy đến phần tử kế cuối. Vòng lặp trong sẽ chạy từ phần tử tiếp theo của vị trí đang xét ở vòng lặp ngoài. Mỗi lần xét ta sẽ so sánh 2 phần tử trong cặp. Nếu chúng nghịch thế thì sẽ hoán đổi vị trí của chúng.

Ta thấy sau mỗi lần duyệt ở vòng lặp ngoài ta sẽ được phần tử đầu tiên đứng đúng thứ tự yêu cầu. Cứ thực hiện đến hết dãy ta sẽ được một dãy đã sắp xếp

Cài đặt
Mã dưới đây được cài đặt theo ngôn ngữ C/C++ với yêu cầu sắp xếp dãy tăng dần

void InterchangeSort(int *a, int n)
{
   for (int i = 0; i < n-1; i++)
      for (int j = i+1; j < n; j++)
         if (a[i] > a[j])
         {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
}

Đánh giá
Số phép so sánh của thuật toán này không đổi, không phụ thuộc tình trạng ban đầu của dãy. Phần tử thứ i được so sánh với n-i phần tử còn lại nên có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Tuy nhiên số phép hoán vị (3 phép gán) lại phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)