Giới Thiệu

Thuật toán Sắp xếp Chèn (Insertion Sort) là một trong những thuật toán sắp xếp cơ bản và dễ hiểu. Đây là một phương pháp sắp xếp đơn giản, hoạt động hiệu quả cho các dãy nhỏ và thường được sử dụng để dạy các khái niệm cơ bản về thuật toán sắp xếp. Mặc dù thuật toán này không phải là lựa chọn tối ưu cho các dãy dữ liệu lớn, nó có những ứng dụng đặc biệt trong các tình huống cụ thể.

Ý Tưởng

Thuật toán Sắp xếp Chèn hoạt động bằng cách chia mảng thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Bắt đầu từ phần tử đầu tiên của mảng, thuật toán chọn từng phần tử từ phần chưa sắp xếp và chèn nó vào vị trí đúng trong phần đã sắp xếp, giữ cho phần đã sắp xếp luôn luôn được sắp xếp. Quy trình này tiếp tục cho đến khi tất cả các phần tử được chèn vào đúng vị trí của chúng trong mảng.

Ví Dụ

Dưới đây là một ví dụ về thuật toán Sắp xếp Chèn được triển khai bằng Java:

public class InsertionSortExample {
    // Phương thức để thực hiện sắp xếp chèn
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Bắt đầu từ phần tử thứ hai, vì phần tử đầu tiên được coi là đã được sắp xếp
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Di chuyển các phần tử lớn hơn key sang phải để tạo chỗ cho key
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    // Phương thức để in mảng
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};

        System.out.println("Mảng ban đầu:");
        printArray(array);

        insertionSort(array);

        System.out.println("Mảng sau khi sắp xếp:");
        printArray(array);
    }
}

Đánh Giá Thuật Toán Sắp Xếp Chèn

Độ phức tạp thuật toán:

• Trường hợp tốt: O(n) (Khi mảng đã được sắp xếp sẵn, thuật toán chỉ cần lặp qua các phần tử mà không cần di chuyển nhiều)
• Trung bình: O(n²)
• Trường hợp xấu: O(n²) (Khi mảng bị sắp xếp ngược hoàn toàn)

Không gian bộ nhớ sử dụng: O(1)

Tại chỗ (In-place): Có

Cách sử dụng:

Sắp xếp chèn thường được áp dụng trong các tình huống sau:

• Dữ liệu đầu vào nhỏ: Khi làm việc với các mảng nhỏ, thuật toán này hoạt động hiệu quả và đơn giản.
• Cần xử lý dữ liệu theo từng phần: Khi có dữ liệu được thêm vào dần dần và cần duy trì một phần đã sắp xếp.
• Chi phí hoán đổi thấp: Khi việc hoán đổi hoặc di chuyển phần tử không tiêu tốn nhiều tài nguyên.

Sắp xếp chèn là một lựa chọn hợp lý cho các tình huống mà việc duy trì sự đơn giản và hiệu quả cho dãy dữ liệu nhỏ hoặc trong trường hợp xử lý dữ liệu theo từng phần là quan trọng.