Chủ đề nổi bật

Bài 13: Thuật toán sắp xếp nổi bọt trong php

Sắp xếp là một công việc rất quan trọng trong việc quản lý dữ liệu vì nó giúp chúng ta tìm kiếm thông tin một cách nhanh chóng. Tuy nhiên với ...

Sắp xếp là một công việc rất quan trọng trong việc quản lý dữ liệu vì nó giúp chúng ta tìm kiếm thông tin một cách nhanh chóng. Tuy nhiên với lập trình Web thì chúng ta lại ít đụng đến các thuật toán sắp xếp, và PHP cũng đã có cung cấp một số hàm sắp xếp sẵn rất tiện lợ. Nhưng chúng ta đang học lập trình nên bạn cũng không nên bỏ qua các kiến thứ về thuật toán này.

Trong bài này chúng ta sẽ nghiên cứu một thuật toán sắp xếp đơn giản nhất đó là thuật toán sắp xếp nổi bọt(bubble sort). Ý tưởng của thuật toán bắt nguồn từ việc so sánh 2 phần tử cạnh nhau và hoán vị chúng nếu không đúng vị trí. Ta có thể tiến hành từ trái qua phải hoặc từ phải qua trái tùy vào nhu cầu của mình.

Note: Để tiện việc giảng giải tôi gọi $n là tổng số phần tử của mảng, 1 là vị trí phần tử đầu tiên của mảng (trong mảng bắt đầu từ 0 nhưng tôi gắn nó bằng 1 để dễ dung hơn)

1. Sắp xếp nổi bọt tăng dần

Thuật toán sắp xếp nổi bọt tăng dần được xử lý như sau:

Cho vòng lặp $i chạy từ  1 tới ($n-1):

Lần lặp 1: $i = 1, lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 2,  nếu phần tử thứ 1 lớn hơn các phần tử đứng sau bắt đầu từ 2 thì hoán vị chúng.

Lần lặp 2: $i = 2, lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 3, nếu phần tử thứ 2 lớn hơn các phần tử  đứng sau nó bắt đầu từ 3 thì hoán vụ chúng.

Cứ như vậy cho đến khi ta lặp lần thứ ($n – 1), lúc này biến $i = ($n-1), ta so sánh với phần tử cuối cùng ($n) và hoán vị nếu không thỏa mãn.

Ví dụ: Cho mảng sau: $mang = array(1, 5, 9, 2, 4, 9), hãy dùng thuật toán sắp xếp nổi bọt để sắp xếp mảng theo thứ tự tăng dần.

Mảng này có 6 phần tử bắt đầu từ 0 -> 5. Vì thế ta có bài giải như sau:

$mang = array(1, 5, 9, 2, 4, 9); // mảng theo đề bài
 
$sophantu = 6; // hoặc dùng hàm $sophantu = count($mang);
 
// Sắp xếp mảng
for ($i = 0; $i < ($sophantu - 1); $i++)
{
    for ($j = $i + 1; $j < $sophantu; $j++) // lặp các phần tử phía sau
    {
        if ($mang[$i] > $mang[$j]) // nếu phần tử $i bé hơn phần tử phía sau
        {
            // hoán vị
            $tmp = $mang[$j];
            $mang[$j] = $mang[$i];
            $mang[$i] = $tmp;
        }
    }
}
 
// Hiển thị các phần tử của mảng đã sắp xếp
for ($i = 0; $i < $sophantu; $i++){
    echo $mang[$i] . ' ';
}

Trong bài này ta sử dụng vòng lặp for lồng nhau để duyệt các phần tử. Với mỗi vòng lặp $i, ta sẽ dùng vòng lặp $j để duyệt từ vị trí tiếp ($i + 1) theo đến cuối mảng, nếu không đúng vị trí thì thực hiện đổi vị trí cho nhau.

Có lẽ các bạn không hiểu ở chỗ hoán vị. tại sao lại có một biến $tmp? Các bạn thử suy nghĩ giả sử bạn đang ôm một cái bao khá năng nên bạn phải ôm 2 tay, và Bố của bạn đang ôm một cái ghế cũng khá nặng và đương nhiên cũng phải ôm 2 tay. Giờ bạn muốn đổi 2 món đồ vật này tức là bạn sẽ đưa cái bao cho Bố bạn và Bố bạn đưa cái ghế cho bạn.  Giờ làm sao để đổi đây? giải pháp là nhờ một người trung gian giữ hộ cái bao cho bạn, rồi bố bạn đưa cái ghế cho bạn, sau đó bố bạn lấy cái bao từ người trung gian ấy. Từ đó suy ra trong đoạn code hoán vị mình đã dùng biến $tmp để làm biến trung gian lưu trữ.

2. Sắp xếp nổi bọt giảm dầ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

Thuật toán sắp xếp nổi bọt giảm dần thì ý tưởng cũng tương tự như so sánh tăng dần, chỉ có khác khi so sánh 2 phần tử với nhau thì nếu phần tử thứ $i bé hơn phần tử ($i + 1) thì hoán vị 2 vị trí đó. Với ví dụ trên ta có bài giải như sau:

$mang = array(1, 5, 9, 2, 4, 9); // mảng theo đề bài
 
$sophantu = 6; // hoặc dùng hàm $sophantu = count($mang);
 
// Sắp xếp mảng
for ($i = 0; $i < ($sophantu - 1); $i++)
{
    for ($j = $i + 1; $j < $sophantu; $j++) // lặp các phần tử phía sau
    {
        if ($mang[$i] < $mang[$j]) // nếu phần tử $i bé hơn phần tử phía sau
        {
            // hoán vị
            $tmp = $mang[$j];
            $mang[$j] = $mang[$i];
            $mang[$i] = $tmp;
        }
    }
}
 
// Hiển thị các phần tử của mảng đã sắp xếp
for ($i = 0; $i < $sophantu; $i++){
    echo $mang[$i] . ' ';
}

3. Đưa thuật toán sắp xếp nổi bọt vào hàm

Tôi có thắc mắc là tại sao chúng ta lại code một cách không chuyên nghiệp gì hết vậy trong khi chúng ta đã học bài xây dựng hàm trong php? Để chương trình có tính mở rộng và dễ quản lý, bào trì thì chúng ta nên đưa đoạn code sắp xếp vào một hàm. 

// Ham sắp xếp
function sap_xep_tang($mang)
{
    $sophantu = count($mang);
    // Sắp xếp mảng
    for ($i = 0; $i < ($sophantu - 1); $i++)
    {
        for ($j = $i + 1; $j < $sophantu; $j++)
        {
            if ($mang[$i] > $mang[$j])
            {
                // hoán vị
                $tmp = $mang[$j];
                $mang[$j] = $mang[$i];
                $mang[$i] = $tmp;
            }
        }
    }
    return $mang;
}
 
// Hàm xuất ra màn hình
function xuat_mang_ra_man_hinh($mang)
{
    $sophantu = count($mang);
    for ($i = 0; $i < $sophantu; $i++){
        echo $mang[$i] . ' ';
    }
}
 
//--------------------------------------------------
// Chương trình chính
$mang = array(1, 5, 9, 2, 4, 9); // mảng theo đề bài
 
// sắp xếp
$mang = sap_xep_tang($mang);
 
// xuất ra màn hình
xuat_mang_ra_man_hinh($mang);

4. Lời kết

Thuật toán sắp xếp nổi bọt trong php đơn giản và dễ cài đặt, vì thế nó được sử dụng rât rộng rãi trong các chương trình học lập trình ở các trường đại học ở bộ môn cấu trúc dữ liệu căn bản. Bài này mình dừng ở đây, bài học tiếp theo chúng ta sẽ tìm hiểu thuật toán tìm kiếm tuyến tính 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 ...