Bài 18: Thuật toán sắp xếp chèn trong php

Vậy là chúng ta đã được học qua 2 thuật toán sắp xếp chọn và sắp xếp nổi bọt. Vẫn còn một thuật toán sắp xếp nũa chúng ta sẽ được học trong bài hôm nay đó là là thuật toán sắp xếp chèn.

test php

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Nôi dung bao gồm:

Ý tưởng thuật toán
Cài đặt thuật toán

1. Ý tưởng thuật toán sắp xếp chèn

Ý tưởng thuật toán sắp xếp chèn như sau:

Trước hết ta xem phần tử a[0] là một dãy đã có thứ tự.

Bài viết này được đăng tại [free tuts .net]

Bước 1: Chèn phần tử a[1] vào dãy a[0] theo đúng vị trí sao cho dãy a[0] và a[1] được sắp xếp đúng thứ tự.

Bước 2: Chèn phần tử a[2] vào dãy a[0], a[1] sao cho dãy a[0], a[1], a[2] được sắp xếp đúng thứ tự.

Bước i: Chèn phần tử a[i] vào dãy a[o], a[1], a[2], …, a[i-1] sao cho dãy a[o], a[1], a[2], …, a[i-1], a[i] được sắp xếp đúng thứ tự

Sau N-1 bước thì kết thúc (vì mảng có N-1 phần tử).

Lưu đồ thuật toán sắp xếp chèn:

thuat toan sap xep chen png

Ví dụ: Sắp xếp tăng dần dãy 5 – 1 – 3 – 4 – 6 – 8. (Phần màu xanh là phần đã sắp xếp)

Bước 1: Coi như phần tử thứ nhất là số 5 đã được sắp xếp, dãy lúc này như sau: 5 - 1 – 3 – 4 – 6 – 8.

Bước 2: Lấy phần tử thứ hai là số 1 gán vào đúng vị trí trong dãy 5, lúc này dãy như sau: 1 – 5 - 3 – 4 – 6 – 8.

Bước 3: Lấy phần tử thứ ba là số 3 gán vào đúng vị trí trong dãy 1 – 5, lúc này dãy như sau: 1 – 3 – 5 – 4 – 6 – 8.

Bước 4: Lấy phần tử thứ tư là số 4 gán vào đúng vị trí trong dãy 1 – 3 – 5, lúc này dãy như sau: 1 – 3 – 4 – 5 – 6 – 8.

Bước 5: Lấy phần tử thứ năm là số 6 gán vào đúng vị trí trong dãy 1 – 3 – 4 – 5, lúc này dãy như sau: 1 – 3 – 4 – 5 – 6 – 8.

Bước 6: Lấy phần tử thứ sáu ( phần tử cuối cùng) gán vào đúng vị trí trong dãy 1 – 3 – 4 – 5 – 6, lúc này dãy như sau: 1 – 3 – 4 – 5 – 6 – 8.

Kết thúc: kết quả đã được sắp xếp như sau: 1 – 3 – 4 – 5 – 6 – 8

2. Cài đặt thuật toán sắp xếp chèn

Chúng ta đã được học bài xây dựng hàm trong php rồi nên tôi sẽ viết bài giải dưới dạng hàm nhé.

Sắp xếp tăng dần:

function InsertionSort($mang)  {
    // Tổng số phần tử
    $sophantu = count($mang);
 
    // Lặp qua từng phần tử của mảng để sắp xếp
    for ($i = 0; $i < $sophantu; $i++)
    {
        // Lặp từ phần tử thứ $i, ví dụ $i = 6
        // thì sẽ lặp từ phần tử số 6 trở về 0 để kiểm tra
        $loop = $i;
 
        // Lưu lại giá trị của $mang[$i] để khỏi bị mất
        $current = $mang[$i];
 
        // điều kiện dừng là $loop <= 0 (tức là hết mảng) hoặc
        // phần tử thứ $loop - 1 bé hơn phần tử thứ $i (vì đã tìm đc đúng vị trí)
        // nếu một trong 2 điều kiện đó đúng thì sẽ dừng vòng lặp
        while($loop > 0 && ($mang[$loop - 1] > $current))
        {
            // Di dời các phần tử lên 1 bậc
            $mang[$loop] = $mang[$loop - 1];
            $loop -= 1;
        }
 
        // Gán giá trị $current vào vị trí tìm được
        $mang[$loop] = $current;
    }
 
    return $m

Sắp xếp giảm dần:

Sắp xếp giảm dần cũng như tăng dần, chỉ khác là ta đổi dấu điều kiện lặp trong vòng lặp while.

function InsertionSort($mang)  {
    // Tổng số phần tử
    $sophantu = count($mang);
 
    // Lặp qua từng phần tử của mảng để sắp xếp
    for ($i = 0; $i < $sophantu; $i++)
    {
        // Lặp từ phần tử thứ $i, ví dụ $i = 6
        // thì sẽ lặp từ phần tử số 6 trở về 0 để kiểm tra
        $loop = $i;
 
        // Lưu lại giá trị của $mang[$i] để khỏi bị mất
        $current = $mang[$i];
 
        // điều kiện dừng là $loop <= 0 (tức là hết mảng) hoặc
        // phần tử thứ $loop - 1 lớn hơn phần tử thứ $i (vì đã tìm đc đúng vị trí)
        // nếu một trong 2 điều kiện đó đúng thì sẽ dừng vòng lặp
        while($loop > 0 && ($mang[$loop - 1] < $current))
        {
            // Di dời các phần tử lên 1 bậc
            $mang[$loop] = $mang[$loop - 1];
            $loop -= 1;
        }
 
        // Gán giá trị $current vào vị trí tìm được
        $mang[$loop] = $current;
    }
    return $mang;

3. Lời kết

Có lẽ hơi rối với thuật toán sắp xếp chèn trong php này đúng không các bạn. Mình cũng không biết giải thích thế nào cho các bạn hiểu thêm nữa, các bạn cố gắng gõ lại code, ngồi hình dung dần nhé =)). Bài tiếp theo chúng ta sẽ học phương thức get và post trong php

Bài trước Bài tiếp

Cùng chuyên mục:

Hàm key_exists() trong PHP

Cách sử dụng key_exists() trong PHP

Hàm mysqli_fetch_row() trong PHP

Cách sử dụng mysqli_fetch_row() trong PHP

Hàm end() trong PHP

Cách sử dụng end() trong PHP

Hàm mysqli_field_count() trong PHP

Cách sử dụng mysqli_field_count() trong PHP

Hàm count() trong PHP

Cách sử dụng count() trong PHP

Hàm mysqli_field_seek() trong PHP

Cách sử dụng mysqli_field_seek() trong PHP

Hàm compact() trong PHP

Cách sử dụng compact() trong PHP

Hàm mysqli_field_tell() trong PHP

Cách sử dụng mysqli_field_tell() trong PHP

Hàm array_values() trong PHP

Cách sử dụng array_values() trong PHP

Hàm mysqli_free_result() trong PHP

Cách sử dụng mysqli_free_result() trong PHP

Hàm array_unshift() trong PHP

Cách sử dụng array_unshift() trong PHP

Hàm mysqli_get_charset() trong PHP

Cách sử dụng mysqli_get_charset() trong PHP

Hàm array_shift() trong PHP

Cách sử dụng array_shift() trong PHP

Hàm mysqli_get_client_stats() trong PHP

Cách sử dụng mysqli_get_client_stats() trong PHP

Hàm array_unique() trong PHP

Cách sử dụng array_unique() trong PHP

Hàm mysqli_get_client_version() trong PHP

Cách sử dụng mysqli_get_client_version() trong PHP

Hàm array_uintesect() trong PHP

Cách sử dụng array_uintesect() trong PHP

Hàm mysqli_get_connection_stats() trong PHP

Cách sử dụng mysqli_get_connection_stats() trong PHP

Hàm array_sum() trong PHP

Cách sử dụng array_sum() trong PHP

Hàm mysqli_get_host_info() trong PHP

Cách sử dụng mysqli_get_host_info() trong PHP