Cài đặt thuật toán Insertion Sort trong lập trình

Trong lập trình, thuật toán Insertion Sort được sử dụng phổ biến để sắp xếp các phần tử trong một mảng hoặc danh sách. Đây là một thuật toán sắp xếp đơn giản nhưng hiệu quả cho các bộ dữ liệu nhỏ hoặc khi dữ liệu gần như đã được sắp xếp.

Khái niệm cơ bản

Thuật toán Insertion Sort hoạt động theo nguyên tắc duyệt qua từng phần tử của mảng, từ trái sang phải. Đối với mỗi phần tử, nó sẽ tìm vị trí thích hợp trong danh sách đã sắp xếp và chèn phần tử vào vị trí đó. Quá trình này được lặp đi lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Các bước thực hiện

1. Khởi tạo: Giả sử rằng phần tử đầu tiên của mảng đã được sắp xếp.
2. Duyệt mảng: Bắt đầu từ phần tử thứ hai, mỗi phần tử sẽ được so sánh với các phần tử trước đó trong mảng đã sắp xếp.
3. Chèn phần tử: Di chuyển các phần tử lớn hơn phần tử hiện tại sang phải để tạo chỗ trống, sau đó chèn phần tử hiện tại vào vị trí đúng.
4. Lặp lại: Tiếp tục quá trình cho đến khi tất cả các phần tử của mảng được sắp xếp.

Ví dụ minh họa

Giả sử bạn có một mảng A = [5, 2, 9, 1, 5, 6]. Khi áp dụng thuật toán này, các phần tử sẽ được sắp xếp theo thứ tự sau:

• Bước 1: Giả sử 5 đã được sắp xếp.
• Bước 2: So sánh 2 với 5. Di chuyển 5 sang phải và chèn 2 vào đầu mảng.
• Bước 3: So sánh 9 với 2 và 5. Không cần di chuyển, thêm 9 vào cuối mảng đã sắp xếp.
• Bước 4: So sánh 1 với 2, 5 và 9. Di chuyển 2, 5 và 9 sang phải, chèn 1 vào đầu mảng.
• Bước 5: So sánh 5 với các phần tử đã được sắp xếp. Chỉ cần chèn 5 vào đúng vị trí.
• Bước 6: So sánh 6 với 5 và 9. Chèn 6 vào giữa 5 và 9.

Kết quả cuối cùng là [1, 2, 5, 5, 6, 9].

Cài đặt bằng các ngôn ngữ lập trình

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Ví dụ sử dụng:
arr = [5, 2, 9, 1, 5, 6]
insertion_sort(arr)
print(arr)  # Output: [1, 2, 5, 5, 6, 9]

JavaScript

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        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:
const arr = [5, 2, 9, 1, 5, 6];
console.log(insertionSort(arr));  // Output: [1, 2, 5, 5, 6, 9]

C++

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Ví dụ sử dụng:
int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Kết quả sắp xếp: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Đánh giá hiệu suất

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

  • Trường hợp tốt nhất: O(n) khi mảng đã được sắp xếp.
  • Trường hợp trung bình và xấu nhất: O(n^2) khi mảng có thứ tự ngược lại.

• Độ phức tạp không gian: O(1) vì không cần thêm bộ nhớ ngoài mảng đầu vào.

Kết luận

Mặc dù không phải là thuật toán sắp xếp nhanh nhất đối với các bộ dữ liệu lớn, Insertion Sort lại cực kỳ hiệu quả và dễ hiểu cho các bộ dữ liệu nhỏ hoặc khi dữ liệu đầu vào gần như đã được sắp xếp. Điều này giúp nó trở thành một lựa chọn ưu tiên trong nhiều trường hợp thực tế.