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

[Thuật toán] Sắp xếp trộn – Merge Sort

[Thuật toán] Sắp xếp trộn – Merge Sort Tháng Ba 4, 2015 nguyenvanquan7826 Thuật toán 5 responses Thuật toán sắp xếp trộn (Merge Sort) là một trong các thuật toán sắp xếp hay được sử dụng. Gần giống với thuật toán sắp xếp nhanh ...

Trịnh Tiến Mạnh viết 3 tuần trước

Tìm hiểu thuật toán sắp xếp chèn trong php

Kỹ thuật đặt cờ hiệu trong php Thuật toán sắp xếp chọn trong php Hướng dẫn phương thức get và post trong php Danh sách các hàm xử lý chuỗi trong php Như vậy chúng ta học qua hai thuật toán sắp xếp chọn và sắp xếp nổi bọt, tiếp tục mình sẽ giới thiệu thuật toán sắp xếp chèn trong php. ...

Trịnh Tiến Mạnh viết 17:18 ngày 04/09/2018

Tìm hiểu thuật toán sắp xếp nổi bọt trong php

Cách xây dựng hàm trong php Tìm hiểu giải thuật đệ quy trong php Tìm hiểu thuật toán tìm kiếm tuyến tính trong php Tìm hiểu kỹ thuật đặt lính canh trong php Sắp xếp là công việc quan trọng trong việc quản lý dữ liệu giúp tìm hiểu thông tin nhanh chóng. Nên bài này mình nghiên cứu một ...

Bùi Văn Nam viết 17:15 ngày 04/09/2018

Thuật toán sắp xếp chọn trong php

Tìm hiểu kỹ thuật đặt lính canh trong php Kỹ thuật đặt cờ hiệu trong php Tìm hiểu thuật toán sắp xếp chèn trong php Hướng dẫn phương thức get và post trong php Mình đã được học thuật toán sắp xếp nổi bọt rồi. Trong bài này mình tiếp tục tìm hiểu thuật toán sắp xếp chọn với những ý ...

Hoàng Hải Đăng viết 17:13 ngày 04/09/2018

Một số thuật toán sắp xếp đơn giản (phần 2)

Một số thuật toán sắp xếp đơn giản (phần 1) Chào các bạn, tiếp nối bài viết về thuật toán sắp xếp trước đó, hôm nay mình xin phép được giới thiệu thêm 2 thuật toán nữa đó là Quick Sort và Merge Sort, bên cạnh đó là những ví dụ cơ bản để giúp các bạn có cái nhìn khái quát hơn, đồng thời xác ...

Hoàng Hải Đăng viết 16:54 ngày 12/08/2018
0