Selection Sort (Sắp xếp chọn)

1. Giới thiệu

Vấn đề

Nếu ai đó cho bạn một dãy số gồm n phần tử lộn xộn, ngoài sử dụng thuật toán Bubble Sort đã được học trước đó thì bạn sẽ làm như thế nào để sắp xếp tăng dần nó nhỉ?

Ý tưởng đơn giản

Có thể nghĩ ra như vầy:

Bước 1: Đầu tiên, ta sẽ tìm ra giá trị nhỏ nhất (GTNN) của dãy số từ vị trí 1 → n.

Bước 2: Sau đó, đổi chỗ GTNN đó cho vị trí đầu tiên của dãy.

Bước 3: Lặp lại Bước 1 và Bước 2, nhưng là từ vị trí số 2 (vì giờ đây ta đã có giá trị đầu tiên là GTNN rồi, nên có thể bỏ qua nó).

(Xem rõ cách thức sắp xếp ở ảnh minh hoạ bên dưới hoặc mục 2, Giải thích)

Nhận xét: Tôi để ý rằng, khi đến Bước 3, thực sự ta đã thu hẹp được bài toán. Từ dãy số 1 → n, giờ đây chỉ còn 2 → n...và cứ như thế thu hẹp dần cho đến n → n thì coi như xong. Đây chính là thuật toán Selection Sort.

2. Code

        const selectionSort = (arr) => {
            
            // Chạy một Loop qua từng giá trị của mảng (Loop 1)
            for(let i = 0; i < arr.length; i++) {

                let minIndex = i; // Phần tử nhỏ nhất hiện tại trong vòng lặp
                
                // Loop so sánh các gt còn lại trong arr vs gt hiện tại của loop 1
                for(let j = i + 1; j < arr.length; j++) {
                    if(arr[minIndex] > arr[j]) {
                        minIndex = j; //Đổi index của loop 1 và 2
                    }
                }
                if(minIndex !== i) {
                    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; //Swap
                }
            }
            return arr;
        }
        
        const arr = [3, 1, 4, 2, 5];
        console.log("Array: ", arr);
        
        const sortedArr = selectionSort(arr);
        console.log("Array after sorted: ", sortedArr);

Output:

Giải thích

Với mảng ban đầu [3, 1, 4, 2, 5], ta thực hiện như sau:
    
Loop 1 (Với i = 0):
        Số nhỏ nhất: 1
        Đổi chỗ với số đầu tiên (3) trong dãy: 3 ←→ 1
        Kết quả sau Loop 1: [1, 3, 4, 2, 5]
    
Loop 2 (i = 1):
        Số nhỏ nhất: 2
        Đổi chỗ với số đầu tiên (3) trong dãy [3, 4, 2, 5]: 3 ←→ 2
        Kết quả sau Loop 2: [1, 2, 4, 3, 5]
    
Loop 3 (i = 2):
        Số nhỏ nhất: 3
        Đổi chỗ với số đầu tiên (4) trong dãy [4, 3, 5]: 4 ←→ 3
        Kết quả: [1, 2, 4, 3, 5]
    
Loop 4 (i = 3):
        Số nhỏ nhất đồng thời cũng nằm ở đầu dãy: 4 → Không cần đổi
        Kết quả mảng không đổi: [1, 2, 4, 3, 5]
    
Loop 5 (i = 4):
        Chỉ còn 1 số -> Done!
Kết quả Cuối Cùng: [1, 2, 4, 3, 5].

3. Kết Luận

• Độ phức tạp: O(n^2)
• Không hiệu quả với dữ liệu lớn, nhưng hữu ích để học các khái niệm cơ bản.