Thuật toán sắp xếp chèn (Insertion Sort) trong PHP

Thuật toán sắp xếp chèn (Insertion Sort) là một thuật toán sắp xếp đơn giản và trực quan, hoạt động theo cách tương tự như cách mà bạn có thể sắp xếp các thẻ bài trong tay. Thuật toán này rất hiệu quả với các dãy dữ liệu nhỏ hoặc gần như đã được sắp xếp. Dưới đây là hướng dẫn chi tiết về thuật toán sắp xếp chèn, bao gồm giải thích và mã PHP.

1. Giới thiệu

Thuật toán sắp xếp chèn làm việc bằng cách chia dãy dữ liệu thành hai phần: phần đã được sắp xếp và phần chưa được sắp xếp. Nó liên tục lấy phần tử từ phần chưa được sắp xếp và chèn nó vào vị trí chính xác trong phần đã được sắp xếp.

2. Quy trình

1. Bắt đầu từ phần tử thứ hai: Giả sử phần tử đầu tiên đã được sắp xếp (vì nó là phần tử duy nhất).
2. Lấy phần tử từ danh sách chưa sắp xếp: So sánh nó với các phần tử trong phần đã sắp xếp và tìm vị trí phù hợp để chèn.
3. Chèn phần tử vào đúng vị trí: Di chuyển các phần tử lớn hơn một vị trí sang bên phải và chèn phần tử vào vị trí trống.
4. Lặp lại cho các phần tử còn lại: Tiếp tục cho đến khi toàn bộ dãy được sắp xếp.

3. Thuật toán và Mã PHP

Thuật toán Sắp xếp Chèn:

1. Duyệt từ phần tử thứ hai đến cuối dãy.
2. Với mỗi phần tử, so sánh với các phần tử đã được sắp xếp và tìm vị trí chèn.
3. Di chuyển các phần tử lớn hơn một vị trí sang phải và chèn phần tử vào đúng vị trí.

Mã PHP:

function insertionSort($array) {
    $n = count($array);

    // Duyệt từ phần tử thứ hai đến cuối dãy
    for ($i = 1; $i < $n; $i++) {
        $key = $array[$i]; // Lưu giá trị hiện tại
        $j = $i - 1;

        // Di chuyển các phần tử lớn hơn $key sang bên phải
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }

        // Chèn $key vào đúng vị trí
        $array[$j + 1] = $key;
    }

    return $array;
}

// Ví dụ sử dụng
$numbers = [12, 11, 13, 5, 6];
$sortedNumbers = insertionSort($numbers);

echo "Sắp xếp chèn: " . implode(", ", $sortedNumbers);

4. Phân Tích

• Thời gian thực thi: O(n^2) trong trường hợp tồi tệ nhất (khi dãy dữ liệu được sắp xếp ngược), O(n) trong trường hợp tốt nhất (khi dãy đã được sắp xếp).
• Không gian bộ nhớ: O(1) vì thuật toán sắp xếp chèn thực hiện tại chỗ (in-place sorting).

5. Ứng Dụng

• Sắp xếp dãy nhỏ: Thuật toán sắp xếp chèn thường được sử dụng cho các dãy nhỏ hoặc gần như đã được sắp xếp, nơi mà hiệu suất của nó có thể vượt trội hơn so với các thuật toán sắp xếp phức tạp hơn.
• Phần của thuật toán sắp xếp phức tạp: Nó thường được sử dụng như một bước trong các thuật toán sắp xếp phức tạp hơn, như Quicksort, để sắp xếp các phân đoạn nhỏ.

Tóm tắt

Thuật toán sắp xếp chèn là một phương pháp đơn giản và hiệu quả cho việc sắp xếp các dãy nhỏ hoặc gần như đã được sắp xếp. Mặc dù có độ phức tạp thời gian cao hơn so với các thuật toán sắp xếp khác như Merge Sort hoặc Quick Sort, nó vẫn là một công cụ hữu ích trong nhiều tình huống thực tế. Việc hiểu và áp dụng thuật toán này có thể giúp cải thiện kỹ năng lập trình của bạn và giải quyết các bài toán sắp xếp một cách hiệu quả.

• PHP