Khóa học CTDL và GT

Bài 13.3. Thuật toán Selection Sort và phân tích

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Sau khi tìm hiểu về các khái niệm cơ bản của sắp xếp, hôm nay chúng ta sẽ cùng nhau đi sâu vào một trong những thuật toán sắp xếp đơn giản và dễ hiểu nhất: Selection Sort.

Selection Sort có một ý tưởng rất trực quan, giống như cách chúng ta thường sắp xếp bài trong bộ bài tây vậy: liên tục tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần còn lại của dãy và đặt nó vào đúng vị trí của nó.

Cách Thức Hoạt Động Của Selection Sort

Hãy tưởng tượng bạn có một dãy các số cần sắp xếp theo thứ tự tăng dần. Selection Sort hoạt động bằng cách chia mảng làm hai phần:

1. Vùng đã sắp xếp (Sorted part): Ban đầu là rỗng, nằm ở phía bên trái của mảng.
2. Vùng chưa sắp xếp (Unsorted part): Ban đầu là toàn bộ mảng, nằm ở phía bên phải của mảng.

Thuật toán sẽ thực hiện lặp đi lặp lại các bước sau cho đến khi toàn bộ mảng được sắp xếp:

• Tìm phần tử nhỏ nhất (đối với sắp xếp tăng dần) trong vùng chưa sắp xếp.
• Hoán đổi phần tử nhỏ nhất đó với phần tử đầu tiên của vùng chưa sắp xếp.
• Kích thước của vùng đã sắp xếp tăng thêm một, và vùng chưa sắp xếp giảm đi một. Vị trí của phần tử vừa được hoán đổi vào trở thành phần tử cuối cùng của vùng đã sắp xếp.

Quá trình này lặp lại n-1 lần (với n là số lượng phần tử trong mảng), bởi vì sau n-1 lần lặp, n-1 phần tử đầu tiên đã ở đúng vị trí của chúng, và phần tử cuối cùng còn lại hiển nhiên cũng sẽ ở đúng vị trí cuối cùng trong mảng đã sắp xếp.

Hãy hình dung nó như một cuộc tuyển chọn:

• Ở lượt đầu tiên, bạn "tuyển" phần tử nhỏ nhất trong toàn bộ mảng và đặt nó ở vị trí đầu tiên.
• Ở lượt thứ hai, bạn "tuyển" phần tử nhỏ nhất trong phần còn lại của mảng (bỏ qua phần tử đầu tiên đã được đặt đúng chỗ) và đặt nó ở vị trí thứ hai.
• Cứ tiếp tục như vậy cho đến khi tất cả các vị trí đều được lấp đầy bởi phần tử nhỏ nhất tương ứng từ phần còn lại.

Thuật Toán Chi Tiết

Đối với mảng arr có kích thước n:

1. Lặp từ i = 0 đến n-2 (duyệt qua từng vị trí cần đặt phần tử nhỏ nhất).
2. Trong mỗi lần lặp i: a. Giả sử phần tử nhỏ nhất trong vùng chưa sắp xếp (arr[i] đến arr[n-1]) ban đầu là arr[i]. Lưu lại chỉ số của nó, ví dụ min_idx = i. b. Lặp từ j = i+1 đến n-1 (duyệt qua các phần tử còn lại trong vùng chưa sắp xếp). c. Nếu arr[j] nhỏ hơn arr[min_idx], cập nhật min_idx = j. d. Sau khi kết thúc vòng lặp j, min_idx sẽ chứa chỉ số của phần tử nhỏ nhất thực sự trong vùng arr[i...n-1]. e. Nếu min_idx không phải là i (nghĩa là phần tử nhỏ nhất không phải là phần tử đầu tiên của vùng chưa sắp xếp), hoán đổi arr[i] và arr[min_idx].

Cài Đặt Bằng C++

Dưới đây là cách cài đặt thuật toán Selection Sort bằng ngôn ngữ C++:

#include <iostream> // Cần cho việc in ra màn hình
#include <vector>   // Sử dụng std::vector cho mảng động
#include <algorithm> // Cần cho std::swap

// Hàm thực hiện thuật toán Selection Sort trên vector
void selectionSort(std::vector<int>& arr) {
    // Lấy kích thước của vector
    int n = arr.size();

    // Vòng lặp ngoài: Duyệt qua từng vị trí cần đặt phần tử nhỏ nhất
    // Chúng ta chỉ cần lặp đến n-2 vì phần tử cuối cùng sẽ tự động đúng chỗ
    for (int i = 0; i < n - 1; ++i) {
        // Giả sử phần tử tại vị trí i là nhỏ nhất trong vùng chưa sắp xếp
        int min_idx = i;

        // Vòng lặp trong: Tìm phần tử nhỏ nhất trong vùng chưa sắp xếp (từ i+1 đến hết)
        for (int j = i + 1; j < n; ++j) {
            // So sánh phần tử hiện tại với phần tử nhỏ nhất đã tìm thấy
            if (arr[j] < arr[min_idx]) {
                // Nếu arr[j] nhỏ hơn, cập nhật chỉ số của phần tử nhỏ nhất
                min_idx = j;
            }
        }

        // Sau khi kết thúc vòng lặp trong, min_idx là chỉ số của phần tử nhỏ nhất
        // trong vùng arr[i...n-1].
        // Hoán đổi phần tử nhỏ nhất này với phần tử tại vị trí i (đầu vùng chưa sắp xếp)
        // Chỉ hoán đổi nếu phần tử nhỏ nhất không phải là chính arr[i]
        if (min_idx != i) {
            std::swap(arr[i], arr[min_idx]);
        }

        // Sau mỗi lần lặp ngoài, phần tử tại vị trí i đã ở đúng vị trí sắp xếp của nó.
        // Vùng đã sắp xếp mở rộng thêm 1 phần tử.
    }
}

// Hàm tiện ích để in mảng
void printArray(const std::vector<int>& arr) {
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

// Hàm main để minh họa
int main() {
    std::vector<int> myVector = {64, 25, 12, 22, 11};

    std::cout << "Mang ban dau: ";
    printArray(myVector);

    selectionSort(myVector);

    std::cout << "Mang sau khi sap xep: ";
    printArray(myVector);

    // Minh hoa voi mot mang khac
    std::vector<int> anotherVector = {5, 2, 8, 1, 9, 4, 7, 6, 3};

    std::cout << "Mang ban dau (2): ";
    printArray(anotherVector);

    selectionSort(anotherVector);

    std::cout << "Mang sau khi sap xep (2): ";
    printArray(anotherVector);


    return 0;
}

Giải Thích Code

• #include <iostream>, <vector>, <algorithm>: Các thư viện cần thiết. iostream để nhập/xuất, vector để sử dụng std::vector (một kiểu mảng động linh hoạt hơn mảng C-style), và algorithm chứa hàm std::swap tiện lợi để hoán đổi giá trị.
• void selectionSort(std::vector<int>& arr): Định nghĩa hàm sắp xếp. Hàm nhận vào một tham chiếu đến std::vector<int>, cho phép hàm thay đổi trực tiếp vector gốc.
• int n = arr.size();: Lấy kích thước của vector để biết số lượng phần tử cần xử lý.
• for (int i = 0; i < n - 1; ++i): Vòng lặp ngoài. Biến i đánh dấu vị trí hiện tại mà chúng ta muốn đặt phần tử nhỏ nhất vào. Vùng arr[0...i-1] là vùng đã sắp xếp, và vùng arr[i...n-1] là vùng chưa sắp xếp. Vòng lặp này chạy n-1 lần, đủ để đưa n-1 phần tử đầu tiên về đúng vị trí.
• int min_idx = i;: Khởi tạo min_idx. Ban đầu, chúng ta giả định phần tử nhỏ nhất trong vùng chưa sắp xếp (arr[i...n-1]) là phần tử đầu tiên của vùng đó, tức là arr[i]. min_idx sẽ lưu giữ chỉ số của phần tử nhỏ nhất được tìm thấy.
• for (int j = i + 1; j < n; ++j): Vòng lặp trong. Biến j duyệt qua tất cả các phần tử sau vị trí i trong vùng chưa sắp xếp.
• if (arr[j] < arr[min_idx]) { min_idx = j; }: So sánh phần tử hiện tại (arr[j]) với phần tử nhỏ nhất đã tìm thấy cho đến nay (arr[min_idx]). Nếu arr[j] nhỏ hơn, cập nhật min_idx để lưu giữ chỉ số của phần tử nhỏ hơn mới này.
• if (min_idx != i) { std::swap(arr[i], arr[min_idx]); }: Sau khi vòng lặp trong kết thúc, min_idx chắc chắn là chỉ số của phần tử nhỏ nhất trong toàn bộ vùng arr[i...n-1]. Chúng ta hoán đổi phần tử tại vị trí i (đầu vùng chưa sắp xếp) với phần tử nhỏ nhất tìm được (arr[min_idx]). Điều kiện if (min_idx != i) chỉ là một tối ưu nhỏ, tránh hoán đổi một phần tử với chính nó nếu nó đã là phần tử nhỏ nhất.
• void printArray(...): Hàm phụ trợ để in nội dung của vector ra màn hình, giúp dễ dàng kiểm tra kết quả.
• main(): Hàm chính để khởi tạo một hoặc nhiều vector ví dụ, gọi hàm selectionSort và in kết quả ra.

Ví Dụ Minh Hoạ Chi Tiết

Hãy xem Selection Sort hoạt động như thế nào trên mảng [64, 25, 12, 22, 11]:

Kích thước mảng n = 5. Chúng ta cần 5 - 1 = 4 lượt lặp chính.

Trạng thái ban đầu: [64, 25, 12, 22, 11] Vùng đã sắp xếp: [] Vùng chưa sắp xếp: [64, 25, 12, 22, 11]

Lượt 1 (i = 0):

• Vùng chưa sắp xếp: [64, 25, 12, 22, 11] (từ index 0)
• Tìm phần tử nhỏ nhất trong vùng này. Duyệt từ index 1 đến 4.
  • arr[1] (25) < arr[0] (64)? Yes. min_idx = 1.
  • arr[2] (12) < arr[1] (25)? Yes. min_idx = 2.
  • arr[3] (22) < arr[2] (12)? No.
  • arr[4] (11) < arr[2] (12)? Yes. min_idx = 4.
• Phần tử nhỏ nhất là 11 tại index 4.
• Hoán đổi arr[0] (64) và arr[4] (11).
• Trạng thái sau hoán đổi: [11, 25, 12, 22, 64] Vùng đã sắp xếp: [11] Vùng chưa sắp xếp: [25, 12, 22, 64]

Lượt 2 (i = 1):

• Vùng chưa sắp xếp: [25, 12, 22, 64] (từ index 1)
• Tìm phần tử nhỏ nhất trong vùng này. Duyệt từ index 2 đến 4.
  • arr[2] (12) < arr[1] (25)? Yes. min_idx = 2.
  • arr[3] (22) < arr[2] (12)? No.
  • arr[4] (64) < arr[2] (12)? No.
• Phần tử nhỏ nhất là 12 tại index 2.
• Hoán đổi arr[1] (25) và arr[2] (12).
• Trạng thái sau hoán đổi: [11, 12, 25, 22, 64] Vùng đã sắp xếp: [11, 12] Vùng chưa sắp xếp: [25, 22, 64]

Lượt 3 (i = 2):

• Vùng chưa sắp xếp: [25, 22, 64] (từ index 2)
• Tìm phần tử nhỏ nhất trong vùng này. Duyệt từ index 3 đến 4.
  • arr[3] (22) < arr[2] (25)? Yes. min_idx = 3.
  • arr[4] (64) < arr[3] (22)? No.
• Phần tử nhỏ nhất là 22 tại index 3.
• Hoán đổi arr[2] (25) và arr[3] (22).
• Trạng thái sau hoán đổi: [11, 12, 22, 25, 64] Vùng đã sắp xếp: [11, 12, 22] Vùng chưa sắp xếp: [25, 64]

Lượt 4 (i = 3):

• Vùng chưa sắp xếp: [25, 64] (từ index 3)
• Tìm phần tử nhỏ nhất trong vùng này. Duyệt từ index 4 đến 4.
  • arr[4] (64) < arr[3] (25)? No.
• Phần tử nhỏ nhất là 25 tại index 3.
• min_idx là 3, bằng với i. Không cần hoán đổi.
• Trạng thái sau hoán đổi: [11, 12, 22, 25, 64] Vùng đã sắp xếp: [11, 12, 22, 25] Vùng chưa sắp xếp: [64]

Vòng lặp kết thúc (i đã đạt n-2 = 3). Mảng đã được sắp xếp.

Kết quả cuối cùng: [11, 12, 22, 25, 64]

Phân Tích Thuật Toán Selection Sort

Bây giờ, hãy cùng phân tích hiệu năng của Selection Sort.

Độ phức tạp thời gian (Time Complexity)

Để phân tích độ phức tạp thời gian, chúng ta xem xét số lượng phép so sánh (comparison) và phép hoán đổi (swap).

• Vòng lặp ngoài: Chạy n-1 lần (từ i = 0 đến n-2).
• Vòng lặp trong (tìm min):
  • Khi i = 0, vòng lặp trong chạy n-1 lần (từ j = 1 đến n-1).
  • Khi i = 1, vòng lặp trong chạy n-2 lần (từ j = 2 đến n-1).
  • ...
  • Khi i = n-2, vòng lặp trong chạy 1 lần (từ j = n-1 đến n-1).

Tổng số phép so sánh là: (n-1) + (n-2) + ... + 1 = n*(n-1)/2. Số phép so sánh này là luôn cố định bất kể dữ liệu đầu vào đã sắp xếp hay chưa, hay sắp xếp ngược.

Số phép hoán đổi: Trong mỗi lần lặp của vòng lặp ngoài, chúng ta thực hiện tối đa một phép hoán đổi (chỉ khi min_idx != i). Tổng cộng, chúng ta thực hiện chính xác n-1 phép hoán đổi. Đây là một đặc điểm quan trọng của Selection Sort - nó thực hiện số lượng hoán đổi tối thiểu so với nhiều thuật toán sắp xếp khác.

Vì số phép so sánh là n*(n-1)/2, và đây là thành phần chiếm ưu thế (tỷ lệ thuận với n^2) khi n lớn, nên độ phức tạp thời gian của Selection Sort là O(n^2) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất).

Độ phức tạp không gian (Space Complexity)

Selection Sort sắp xếp mảng tại chỗ (in-place). Nó chỉ sử dụng một vài biến phụ trợ như i, j, min_idx, và một biến tạm cho việc hoán đổi. Lượng bộ nhớ phụ trợ này không phụ thuộc vào kích thước của mảng n. Do đó, độ phức tạp không gian của Selection Sort là O(1).

Đặc điểm

• In-place: Có, nó không yêu cầu bộ nhớ bổ sung đáng kể.
• Stable: Không. Selection Sort không phải là thuật toán sắp xếp ổn định. Điều này có nghĩa là thứ tự tương đối của các phần tử có giá trị bằng nhau có thể bị thay đổi sau khi sắp xếp. Ví dụ: Mảng [5, 8, 5*, 2] (trong đó 5 là một phần tử 5 khác). Sau khi sắp xếp, mảng là `[2, 5, 5, 8]`. Thứ tự ban đầu của 5 và 5* đã bị đảo ngược.
• Adaptive: Không. Hiệu suất của nó không cải thiện ngay cả khi mảng đã được sắp xếp một phần hoặc gần như sắp xếp.

Ưu Điểm và Nhược Điểm

Ưu điểm:

• Đơn giản: Rất dễ hiểu và cài đặt.
• Ít hoán đổi: Thực hiện số lượng phép hoán đổi tối thiểu (n-1 lần). Điều này có thể là một lợi thế lớn nếu chi phí cho việc hoán đổi phần tử rất cao (ví dụ: sắp xếp các đối tượng lớn thay vì chỉ số nguyên).
• O(1) Space Complexity: Hiệu quả về không gian.

Nhược điểm:

• Chậm: Độ phức tạp thời gian O(n^2) làm cho nó không phù hợp với các tập dữ liệu lớn.
• Không hiệu quả trên dữ liệu gần sắp xếp: Hiệu suất không được cải thiện khi dữ liệu đầu vào đã được sắp xếp một phần.
• Không ổn định (Unstable): Có thể thay đổi thứ tự tương đối của các phần tử bằng nhau.

Khi nào nên sử dụng Selection Sort?

Mặc dù có độ phức tạp O(n^2), Selection Sort vẫn có chỗ đứng trong một số tình huống cụ thể:

• Khi bạn cần một thuật toán sắp xếp đơn giản nhất để cài đặt nhanh hoặc để học tập cơ bản.
• Khi số lượng hoán đổi là mối quan tâm chính và chi phí hoán đổi rất cao so với chi phí so sánh.
• Với các tập dữ liệu rất nhỏ, sự khác biệt về hiệu năng giữa O(n^2) và các thuật toán nhanh hơn không đáng kể.

Bài tập ví dụ:

Người hâm mộ nhiệt thành nhất

Trong một buổi tuyển chọn cầu thủ, FullHouse Dev được giao nhiệm vụ phân tích dữ liệu của các fan hâm mộ để chọn ra những người may mắn được gặp gỡ cầu thủ ngôi sao. Với sự nhiệt huyết và kỹ năng phân tích dữ liệu, FullHouse Dev bắt đầu giải quyết bài toán này.

Bài toán

FullHouse Dev nhận được danh sách \(N\) fan hâm mộ và thông tin rằng cầu thủ ngôi sao chỉ có thể gặp gỡ tối đa \(T\) người. Mỗi fan được định nghĩa bởi hai thông số: Tên và Chỉ số Fan. Chỉ số Fan càng cao thể hiện sự cuồng nhiệt càng lớn. Nhiệm vụ của FullHouse Dev là chọn ra \(T\) fan để cầu thủ gặp gỡ, ưu tiên những người có Chỉ số Fan cao hơn. Trong trường hợp có Chỉ số Fan bằng nhau, họ sẽ chọn người có tên đứng trước theo thứ tự từ điển.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(T\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi và một số nguyên cách nhau bởi khoảng trắng. Chuỗi là tên của fan, số nguyên là Chỉ số Fan.

OUTPUT FORMAT:

• In ra \(T\) dòng, mỗi dòng chứa tên của một fan được chọn. Fan có Chỉ số Fan cao hơn được in trước, nếu bằng nhau thì in tên đứng trước theo thứ tự từ điển.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq T \leq N\)
• \(1 \leq \text{Chỉ số Fan} \leq 10^9\)
• Tên chỉ bao gồm các ký tự trong tập [a-z].
• Không đảm bảo các tên là duy nhất.

Ví dụ

INPUT

3 2
surbhi 3
surpanakha 3
shreya 5

OUTPUT

shreya
surbhi

Giải thích

Thứ tự sắp xếp của các fan sẽ là {"shreya", "surbhi", "surpanakha"}. Do đó, hai fan được chọn là shreya và surbhi. Tuyệt vời! Đây là hướng dẫn giải bài "Người hâm mộ nhiệt thành nhất" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng và cấu trúc thuật toán:

1. Lưu trữ dữ liệu:

   • Cần một cách để lưu trữ thông tin của mỗi fan (Tên và Chỉ số Fan). Sử dụng struct hoặc pair trong C++ là phù hợp. Ví dụ, một struct Fan có hai trường: string name và int score.
   • Dùng std::vector để chứa danh sách N đối tượng Fan.

2. Đọc dữ liệu:

   • Đọc hai số N và T đầu tiên.
   • Dùng vòng lặp để đọc N dòng tiếp theo, mỗi dòng là Tên và Chỉ số Fan. Tạo đối tượng Fan tương ứng và thêm vào std::vector.

3. Sắp xếp:

   • Đây là bước quan trọng nhất. Cần sắp xếp vector các fan theo tiêu chí đã cho:
     • Ưu tiên Chỉ số Fan cao hơn (giảm dần).
     • Nếu Chỉ số Fan bằng nhau, ưu tiên tên đứng trước theo thứ tự từ điển (tăng dần).
   • Sử dụng hàm std::sort từ thư viện <algorithm>. Hàm này cho phép truyền vào một hàm so sánh tùy chỉnh (custom comparator) hoặc một lambda function.
   • Hàm so sánh tùy chỉnh (hoặc lambda): Viết một hàm nhận hai đối tượng Fan và trả về true nếu đối tượng thứ nhất nên đứng trước đối tượng thứ hai trong mảng đã sắp xếp.
     • Trong hàm này, kiểm tra Chỉ số Fan trước: nếu fan1.score != fan2.score, trả về fan1.score > fan2.score (để sắp xếp giảm dần score).
     • Nếu Chỉ số Fan bằng nhau (fan1.score == fan2.score), kiểm tra tên: trả về fan1.name < fan2.name (để sắp xếp tăng dần tên).

4. Chọn và In kết quả:

   • Sau khi vector đã được sắp xếp, T fan nhiệt thành nhất sẽ nằm ở đầu vector (từ index 0 đến T-1).
   • Dùng vòng lặp để duyệt qua T phần tử đầu tiên của vector.
   • Với mỗi phần tử, in ra tên của fan đó.

Tóm tắt các bước chính:

• Định nghĩa cấu trúc dữ liệu cho Fan.
• Đọc N, T và dữ liệu của N fan vào một vector.
• Viết hàm so sánh tùy chỉnh theo luật: score giảm dần, tên tăng dần khi score bằng nhau.
• Sử dụng std::sort với hàm so sánh tùy chỉnh để sắp xếp vector.
• In tên của T fan đầu tiên trong vector đã sắp xếp.

Làm thêm nhiều bài tập miễn phí tại đây