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

Insertion Sort là một thuật toán sắp xếp đơn giản và dễ hiểu. Ý tưởng chính của Insertion Sort là xây dựng dần dần mảng đã được sắp xếp bằng cách chèn từng phần tử từ mảng chưa sắp xếp vào vị trí đúng của nó trong mảng đã sắp xếp.

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

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;

        // Di chuyển các phần tử của arr[0..i-1],
        // lớn hơn key, đến vị trí phía sau chúng
        // để tạo chỗ cho key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}

// Ví dụ sử dụng:
let array = [12, 11, 13, 5, 6];
console.log("Mảng ban đầu: " + array);
let sortedArray = insertionSort(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:

   • Bắt đầu từ phần tử thứ hai (index = 1) và duyệt qua toàn bộ mảng.

3. Khóa key và chỉ số j:

   • key lưu trữ giá trị của phần tử hiện tại cần chèn vào mảng đã sắp xếp.
   • j là chỉ số của phần tử ngay trước key.

4. Vòng lặp while:

   • Di chuyển các phần tử của mảng đã sắp xếp (arr[0..i-1]) lớn hơn key một vị trí về phía sau để tạo chỗ trống cho key.
   • Giảm dần chỉ số j.

5. Chèn key vào vị trí đúng:

   • Sau khi vòng lặp while kết thúc, key được chèn vào đúng vị trí (arr[j+1]).

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

   • Sau khi hoàn thành vòng lặp ngoài, trả về mảng đã được sắp xếp.

Thời gian và không gian:

• Thời gian: O(n^2) trong trường hợp xấu nhất và trung bình, O(n) trong trường hợp tốt nhất (mảng đã được sắp xếp).
• 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ớ ngoài mảng đầu vào và một vài biến tạm.

Insertion Sort là thuật toán đơn giản và dễ hiểu, phù hợp với các mảng nhỏ hoặc gần như đã được sắp xếp, nhưng không hiệu quả đối với các mảng lớn và không được sắp xếp.