Giới thiệu

Thuật toán Sắp xếp Chọn (Selection Sort) là một trong những thuật toán sắp xếp cơ bản, cổ điển và dễ dàng triển khai. Đây là thuật toán thường được tiếp cận đầu tiên khi học các phương pháp sắp xếp cơ bản. Trong nhiều tình huống đơn giản, thuật toán này rất hiệu quả, đặc biệt khi làm việc với các mảng nhỏ và không yêu cầu tối ưu hóa thời gian.

Ý tưởng

Thuật toán hoạt động bằng cách tìm kiếm phần tử nhỏ nhất trong mảng chưa được sắp xếp và di chuyển nó về vị trí đầu tiên. Sau khi thực hiện bước này, phần tử nhỏ nhất đã ở đúng vị trí của nó, và chúng ta không cần quan tâm đến nó nữa. Mảng còn lại sẽ có kích thước nhỏ hơn (n – 1 phần tử), và thuật toán tiếp tục thực hiện tương tự từ phần tử thứ hai trong mảng.

Quá trình này lặp lại cho đến khi chỉ còn lại một phần tử trong mảng, khi đó tất cả các phần tử còn lại đều đã được sắp xếp đúng cách.

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

        // Di chuyển dần từ phần tử đầu tiên đến phần tử cuối cùng
        for (int i = 0; i < n - 1; i++) {
            // Tìm chỉ số của phần tử nhỏ nhất trong phần mảng chưa được sắp xếp
            int minIndex = i;
            for (int 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 phần chưa sắp xếp
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    // 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);

        selectionSort(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 (Insertion Sort)

Độ 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)
• Trung bình: O(n²)
• Trường hợp xấu: O(n²) (Khi mảng bị sắp xếp ngược)

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 là một dãy nhỏ: Khi kích thước mảng nhỏ, thuật toán này hoạt động hiệu quả.
• Chi phí đổi chỗ không đáng kể: Nếu việc hoán đổi phần tử không tiêu tốn nhiều tài nguyên.
• Cần kiểm tra toàn bộ phần tử: Khi cần duyệt qua tất cả các phần tử để đảm bảo sự chính xác của việc sắp xếp.
• Chi phí ghi vào bộ nhớ quan trọng: Trong các bộ nhớ như flash, nơi số lần ghi/đổi chỗ có thể được giảm thiểu (O(n) so với O(n²) của thuật toán sắp xếp nổi bọt).

Thuật toán sắp xếp chèn là một lựa chọn phù hợp khi cần sự đơn giản và hiệu quả cho các dãy nhỏ hoặc khi chi phí của việc hoán đổi là tối thiểu.