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

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:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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é.

Theo:freetuts.net

 

 

Được quan tâm nhiều nhất

  • Apple Watch Series 5 Teardown - Always on Display Explained

  • Apple Watch Series 4 Teardown

  • iPhone 11 Pro Max Teardown - Tiny Motherboard & BIG Battery!

Bạn thấy bài viết này thế nào?
Thể hiện yêu thương tác giả ở đây nhé!

Thích bài viết

thích

Chia sẻ ngay!

phuongle

Thành viên từ: 10/12/2019

Điểm uy tín: 8,327

SMod: 1,288 hướng dẫn đã chia sẻ

Team

Lập Trình Thành viên của Lập Trình

1 Thành viên

1,288 bài viết

Thêm bình luận

Bình luận bằng tài khoản Facebook

Săn Sale Ngay Trên Shopee - Giảm giá đến 500K Đóng
Amharic Amharic Arabic Arabic Bengali Bengali Chinese (Simplified) Chinese (Simplified) Chinese (Traditional) Chinese (Traditional) English English Filipino Filipino French French German German Hausa Hausa Hindi Hindi Indonesian Indonesian Italian Italian Japanese Japanese Korean Korean Persian Persian Portuguese Portuguese Russian Russian Serbian Serbian Spanish Spanish Thai Thai Turkish Turkish Urdu Urdu Vietnamese Vietnamese