Thuật Toán Sắp Xếp Chọn (Selection Sort) Trong C++: Chi Tiết và Dễ Hiểu

Chào mừng bạn đến với bài viết về thuật toán sắp xếp chọn (Selection Sort) trong C++. Đây là một trong những thuật toán sắp xếp cơ bản và quan trọng trong lập trình. Bài viết này sẽ cung cấp cho bạn cái nhìn tổng quan về ý tưởng, ví dụ minh họa, code C++ và đánh giá hiệu quả của thuật toán Selection Sort.

Ý tưởng của thuật toán Selection Sort

Thuật toán Selection Sort hoạt động dựa trên ý tưởng đơn giản: tìm phần tử nhỏ nhất (hoặc lớn nhất, tùy theo yêu cầu sắp xếp) trong phần mảng chưa được sắp xếp và hoán đổi nó với phần tử đầu tiên của phần mảng đó. Quá trình này lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Thuật toán Selection Sort chia mảng thành hai phần:

  1. Phần đã được sắp xếp (ở đầu mảng).
  2. Phần chưa được sắp xếp (ở cuối mảng).

Ở mỗi bước lặp, thuật toán sẽ tìm phần tử nhỏ nhất trong phần chưa được sắp xếp và chuyển nó về cuối phần đã được sắp xếp, từ đó mở rộng phần đã được sắp xếp và thu hẹp phần chưa được sắp xếp.

Ví dụ minh họa thuật toán Selection Sort

Giả sử chúng ta có mảng sau: [64, 25, 12, 22, 11] và muốn sắp xếp nó theo thứ tự tăng dần bằng thuật toán Selection Sort.

  • Bước 1: Tìm phần tử nhỏ nhất trong mảng [64, 25, 12, 22, 11]. Phần tử nhỏ nhất là 11. Hoán đổi 11 với 64, ta được mảng [11, 25, 12, 22, 64]. Phần đã sắp xếp là [11], phần chưa sắp xếp là [25, 12, 22, 64].

  • Bước 2: Tìm phần tử nhỏ nhất trong mảng [25, 12, 22, 64]. Phần tử nhỏ nhất là 12. Hoán đổi 12 với 25, ta được mảng [11, 12, 25, 22, 64]. Phần đã sắp xếp là [11, 12], phần chưa sắp xếp là [25, 22, 64].

  • Bước 3: Tìm phần tử nhỏ nhất trong mảng [25, 22, 64]. Phần tử nhỏ nhất là 22. Hoán đổi 22 với 25, ta được mảng [11, 12, 22, 25, 64]. Phần đã sắp xếp là [11, 12, 22], phần chưa sắp xếp là [25, 64].

  • Bước 4: Tìm phần tử nhỏ nhất trong mảng [25, 64]. Phần tử nhỏ nhất là 25. Không cần hoán đổi vì 25 đã ở đúng vị trí. Mảng là [11, 12, 22, 25, 64]. Phần đã sắp xếp là [11, 12, 22, 25], phần chưa sắp xếp là [64].

  • Bước 5: Mảng đã được sắp xếp hoàn toàn: [11, 12, 22, 25, 64].

Minh họa thuật toán Selection Sort sử dụng ngôn ngữ C++

Dưới đây là đoạn code C++ minh họa thuật toán Selection Sort để sắp xếp một mảng các số nguyên theo thứ tự tăng dần:

#include <iostream>
#include <algorithm> // Sử dụng hàm swap

using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            swap(arr[i], arr[min_index]);
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    cout << "Mảng sau khi sắp xếp: n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

  • Hàm selectionSort(int arr[], int n) nhận một mảng arr và kích thước n của mảng làm đầu vào.
  • Vòng lặp ngoài for (int i = 0; i < n - 1; i++) duyệt qua từng phần tử của mảng (trừ phần tử cuối cùng vì nó sẽ tự động được sắp xếp).
  • min_index = i gán chỉ số của phần tử nhỏ nhất hiện tại là i.
  • Vòng lặp trong for (int j = i + 1; j < n; j++) duyệt qua các phần tử còn lại của mảng để tìm phần tử nhỏ nhất thực sự.
  • if (arr[j] < arr[min_index]) so sánh phần tử hiện tại arr[j] với phần tử nhỏ nhất hiện tại arr[min_index]. Nếu arr[j] nhỏ hơn, thì cập nhật min_index thành j.
  • if (min_index != i) kiểm tra xem có cần hoán đổi hay không. Nếu min_index khác i, tức là đã tìm thấy một phần tử nhỏ hơn phần tử hiện tại, thì hoán đổi hai phần tử đó bằng hàm swap().
  • Hàm main() tạo một mảng mẫu, gọi hàm selectionSort() để sắp xếp mảng, và in ra mảng đã sắp xếp.

Đánh giá thuật toán Selection Sort

Độ phức tạp thời gian:

  • Trường hợp tốt nhất: O(n^2)
  • Trường hợp trung bình: O(n^2)
  • Trường hợp xấu nhất: O(n^2)

Selection Sort luôn thực hiện n^2 phép so sánh, không phụ thuộc vào trạng thái ban đầu của mảng. Điều này làm cho nó kém hiệu quả đối với các mảng lớn.

Độ phức tạp không gian: O(1)

Selection Sort là một thuật toán sắp xếp tại chỗ (in-place), nghĩa là nó không cần thêm không gian bộ nhớ đáng kể để thực hiện.

Ưu điểm:

  • Đơn giản và dễ hiểu.
  • Hoạt động tốt với các mảng nhỏ.
  • Số lần hoán đổi ít hơn so với một số thuật toán sắp xếp khác (ví dụ: Bubble Sort).

Nhược điểm:

  • Kém hiệu quả đối với các mảng lớn do độ phức tạp thời gian O(n^2).
  • Không ổn định (unstable), tức là thứ tự tương đối của các phần tử bằng nhau có thể bị thay đổi sau khi sắp xếp.

Kết luận:

Thuật toán Selection Sort là một thuật toán sắp xếp đơn giản và dễ hiểu, phù hợp cho việc học tập và áp dụng trên các mảng nhỏ. Tuy nhiên, đối với các mảng lớn, các thuật toán sắp xếp khác như Merge Sort hoặc Quick Sort sẽ hiệu quả hơn.