Thuật toán Selection Sort Sắp xếp đơn giản và hiệu quả

Selection Sort là một thuật toán sắp xếp đơn giản. Ý tưởng chính của Selection Sort là tìm phần tử nhỏ nhất trong mảng và đưa nó về đầu mảng. Sau đó, tìm phần tử nhỏ thứ hai và đặt nó vào vị trí thứ hai, và cứ tiếp tục như vậy cho đến khi mảng được sắp xếp.

Dưới đây là cách triển khai Selection Sort trong JavaScript:

function selectionSort(arr) {
    let n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        // Tìm chỉ số của phần tử nhỏ nhất trong mảng từ i đến n-1
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp
        if (minIndex !== i) {
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    return arr;
}

// Ví dụ sử dụng:
let array = [64, 25, 12, 22, 11];
console.log("Mảng ban đầu: " + array);
let sortedArray = selectionSort(array);
console.log("Mảng sau khi sắp xếp: " + sortedArray);

Giải thích:

1. Khởi tạo:

   • n là độ dài của mảng.

2. Vòng lặp ngoài for:

   • Vòng lặp chạy từ i = 0 đến n - 2, duyệt qua các phần tử của mảng.

3. Tìm phần tử nhỏ nhất:

   • Khởi tạo minIndex là i, chỉ số của phần tử nhỏ nhất hiện tại.
   • Vòng lặp for bên trong chạy từ j = i + 1 đến n - 1, tìm phần tử nhỏ nhất trong mảng từ i đến n - 1.

4. Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của mảng chưa được sắp xếp:

   • Nếu minIndex không phải là i, hoán đổi giá trị của phần tử tại i với phần tử tại minIndex.

5. Trả về mảng đã sắp xếp:

   • Trả về mảng sau khi tất cả các phần tử đã được sắp xếp.

Thời gian và không gian:

• Thời gian: O(n^2) trong tất cả các trường hợp (tốt, trung bình, xấu).
• Không gian: O(1) vì sắp xếp được thực hiện tại chỗ, không sử dụng thêm không gian bộ nhớ.

Selection Sort đơn giản và dễ hiểu, nhưng không phải là thuật toán sắp xếp hiệu quả nhất đối với mảng lớn. Tuy nhiên, nó có ưu điểm là dễ triển khai và không thay đổi thứ tự các phần tử đã sắp xếp.