Chủ đề nổi bật

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 ...

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.

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ướ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:


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

BẢNG MÃ KÍCH HOẠT KHÓA HỌC RẤT RẺ

Mình đã sưu tầm các mã giám giá rất rẻ và đăng nó ơ trong bài viết này, bạn hãy vào tham khảo để xem cần kháo nào thì hãy chọn cho riêng mình nhé, Lưu ý la chỉ có tại code24h.com, bạn sẽ không thể tìm thấy ở chỗ khác.

Xem Ngay

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 KẾ SAU
BÀI KẾ TIẾP

Nguồn: code24h.com

Bài liên quan
Mới nhất

Danh sách các múi giờ (Timezones) trong PHP

- Múi giờ (timezones) thường được sử dụng trong các hàm xử lý ngày tháng & thời gian. - Dưới đây là danh sách đầy đủ các múi giờ được hỗ trợ trong ngôn ngữ lập trình PHP. 1) Africa Africa/Abidjan Africa/Accra Africa/Addis_Ababa Africa/Algiers 2) America ...

Các hàm dùng để quản lý thư mục trong PHP

Hàm Mô tả chức năng chdir() chroot() closedir() dir() getcwd() opendir() readdir() rewinddir() scandir() ...

Danh sách tất cả các hàm xử lý chuỗi trong PHP

Hàm Mô tả chức năng addcslashes() Thêm một dấu gạch chéo ngược () phía trước các ký tự được chỉ định addslashes() Thêm một dấu gạch chéo ngược () phía trước các ký tự là dấu nháy kép, dấu nháy đơn và dấu gạch chéo ngược trong chuỗi bin2hex() Chuyển một chuỗi các ký tự ...

Cách khai báo và sử dụng hàm (function) trong PHP

1) Hàm là gì !? - Hàm là một tập hợp gồm nhiều câu lệnh, các câu lệnh này được sắp xếp theo một thứ tự xác định để xây dựng thành một chức năng cụ thể và mỗi hàm sẽ có một cái tên. Ví dụ Đoạn mã bên dưới, chúng ta có một hàm tên là GioiThieuBanThan. Hàm này gồm ba câu lệnh với ...

Vòng lặp for & foreach trong PHP

1) Vòng lặp là gì !? - Trong PHP, vòng lặp là một loại cú pháp giúp ta lặp lại việc thực thi một đoạn mã nhiều lần. - Ví dụ, nếu tôi muốn hiển thị lên màn hình 100 dòng chữ "Lập Trình Web" thì đáng ra phải gõ 100 câu lệnh echo "<p>Lập Trình Web</p>"; . Tuy nhiên, với việc sử ...

Lệnh điều kiện if ... else trong PHP

"Nếu bạn học tốt môn lập trình web thì bạn sẽ có thể thiết kế được website" - Câu trên được chia làm hai vế: Vế thứ nhất: "Nếu bạn học tốt môn lập trình web" Vế thứ hai: "Bạn sẽ có thể thiết kế được website" - Trong cuộc sống, ta gọi vế thứ nhất là điều kiện, vế thứ hai là một điều ...

Danh sách tất cả các hàm xử lý mảng trong PHP

Hàm Mô tả chức năng array_change_key_case Đổi tên của tất cả các phần tử trong mảng về dạng chữ in hoa hoặc chữ thường array_chunk array_column array_combine array_count_values array_diff array_diff_assoc array_diff_key ...

Danh sách các hàm xử lý tập tin hệ thống trong PHP

Hàm Mô tả chức năng basename() Trả về tên tập tin từ một đường dẫn chgrp() Thay đổi nhóm người dùng của tập tin được chỉ định chmod() Thiết lập quyền hạn của các nhóm người dùng trên tập tin được chỉ định chown() Thay đổi chủ sở hữu của một tập tin copy() Sao ...

Danh sách tất cả các hàm xử lý ngày tháng trong PHP

Hàm Mô tả chức năng checkdate Kiểm tra xem một ngày được xác định có hợp lệ hay không date date_add date_create date_create_from_format data_create_immutable data_create_immutable_from_format date_date_set date_default_timezone_get ...

Vòng lặp while & do while trong PHP

1) Vòng lặp while trong PHP - Trước khi nêu khái niệm "vòng lặp while là gì?" thì tôi có một ví dụ để giúp bạn có thể hình dung sơ qua về vòng lặp while. - Bạn đưa ra một điều kiện, nếu điều kiện đó là sai thì kết thúc, còn nếu đúng thì một đoạn mã sẽ được thực thi và bạn tiếp tục quay ...