Học về cách sắp xếp chèn trong php

Học về cách sắp xếp chèn trong php là vấn đề được nhiều lập trình viên quan tâm, bởi những kiến thức trên trường lớp là không đủ, vì vậy bài Học về cách sắp xếp chèn trong php sẽ chia sẻ tới bạn nhiều thông tin hữu ích

Mọi người vẫn hỏi tôi về việc học lập trình nói chung và PHP nói riêng có cần năng khiếu hay quá khó để tiếp cận hay không. Thì tôi có thể trả lời rằng, học lập trình cũng như việc bạn học tiếng Anh hay bất kỳ một ngôn ngữ khác, bởi lập trình...là ngôn ngữ của máy tính, để máy tính đọc và máy tính thực hiện theo yêu cầu của mình, bạn thích là học được.

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:


Học về cách sắp xếp chèn trong php

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


Hy vọng với bài viết về Học về cách sắp xếp chèn trong php đã giải đáp giúp bạn phần nào về kiến thức lập trình PHP. Như tôi đã nói, ngôn ngữ lập trình không quan trọng bằng tư duy giải thuật, tư duy logic để giải quyết vấn đề.

Với những năm trước đây, lập trình viên là một cái nghề khó và kén chọn người học, đồng nghĩa với việc thu nhập hàng tháng của các lập trình viên luôn cao. Còn những năm gần đây, thì lập trình là môn học phổ thông, và ai cũng nên học một ngôn ngữ lập trình nào đó.

Nếu bạn còn bất kỳ câu hỏi nào trong việc học lập trình online, hãy gửi yêu cầu cho tôi qua email hoidapcode.com@gmail.com hoặc để lại comment bên dưới, tôi sẽ giải đáp trong vòng 24 giờ!

Blog hoidapcode.com là blog được tổng hợp tự động các bài học, thông tin về lập trình trên mạng internet. Nếu bạn có ý kiến hoặc đóng góp về bài viết này, hãy liên hệ với tôi!