Chủ đề nổi bật

Bài 17: Thuật toán sắp xếp chọn trong php

Chúng ta đã được học thuật toán sắp xếp nổi bọt dùng để sắp xếp các phần tử trong mảng tăng hoặc giảm dần. Và trong bài này chúng ta sẽ nghiên ...

Chúng ta đã được học thuật toán sắp xếp nổi bọt  dùng để sắp xếp các phần tử trong mảng tăng hoặc giảm dần. Và trong bài này chúng ta sẽ nghiên cứu một thuật toán khác đó là thuật toán sắp xếp chọn, một thuật toán có độ khó hơn thuật toán sắp xếp nổi bọt. 

Nội dung bao gồm:

  • Ý tưởng thuật toán sắp xếp chọn
  • Tìm kiếm phần tử lớn nhất, nhỏ nhất
  • Sắp xếp chọn tăng dần
  • Sắp xếp chọn giảm dần

1. Ý tưởng thuật toán sắp xếp chọn

Với thuật toán nổi bọt thì ý tưởng là với mỗi phần tử sẽ lặp hết các phần tử phía sau, nếu phần tử nào không đứng đúng vị trí thì hoán vị ngay lập tức. Với thuật toán sắp xếp chọn trong php thì lại khác, ý tưởng như sau: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí. Tiếp tục thao tác như vậy cho các vị trí tiếp theo.

Sắp xếp chọn tăng dần:

Bước 1: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí.

Bước 2: Duyệt từ vị trí số 2 đến vị trí cuối cùng, tìm ví trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 2, sau đó loại vị trí số 2 ra khỏi danh sách sắp xếp vì đã đặt đúng vị trí.

Bước n: Cứ như vậy cho đến vị trí phần tử cuối cùng, lúc này chỉ còn 1 phần tử nên coi như nó đã sắp xếp.

Giải thuật mô tả bằng hình:

Sắp xếp chọn giảm dần:

Tương tự như sắp xếp tăng dần, vẫn duyệt n bước với điều kiện hoán vị ngược lại là tìm vị trí phần tử lớn nhất và hoán vị với vị trí thứ n.

2. Tìm kiếm phần tử lớn nhất, nhỏ nhất

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 chọn có sử dụng thuật toán tìm kiếm giá trị lớn nhất, nhỏ nhất trong mảng nên tôi sẽ mở ra một phần nhỏ này dành cho những bạn chưa rành gì về kỹ thuật lập trình.

Để tìm giá trị nhỏ nhất, lớn nhất chúng ta sẽ dùng kỹ thuật đặt lính canh kết hợp với tìm kiếm tuyến tính, nghĩa là lúc đầu sẽ chọn phần tử thứ nhất làm lính cầm canh, sau đó duyệt các phần tử còn lại, phần tử nào lớn hơn nếu tìm MAX hoặc nhỏ hơn nếu tìm MIN thì thay thế cho lính canh đã chọn. Sau khi lặp hết các phần tử thì lính canh chính là vị trí lớn nhất, nhỏ nhất.

Bài giải: Tìm phần tử nhỏ nhất:

// Hàm tìm vị trí phần tử nhỏ nhất
function tim_min($mang)
{
    // Đếm tổng số phần tử
    $total = count($mang);
 
    // Gọi min là lính cầm canh
    // lúc đầu chọn vị trí số 0 ngồi canh
    $min = 0;
 
    // Duyệt lần lượt các phần tử
    for ($i = 0; $i > $total; $i++ )
    {
        // Nếu phần tử cầm canh lớn hơn phần tử thứ $i thì
        // lấy vị trí $i ngồi canh
        if ($mang[$min] > $mang[$i]){
            $min = $i;
        }
    }
 
    // Trả về vị trí nhỏ nhất
    return $min;
}

Bài giải: Tìm phần tử lớn nhất:

// Hàm tìm vị trí phần tử Lớn nhất
function tim_min($mang)
{
    // Đếm tổng số phần tử
    $total = count($mang);
 
    // Gọi max là lính cầm canh
    // lúc đầu chọn vị trí số 0 ngồi canh
    $max = 0;
 
    // Duyệt lần lượt các phần tử
    for ($i = 0; $i > $total; $i++ )
    {
        // Nếu phần tử cầm canh lớn hơn phần tử thứ $i thì
        // lấy vị trí $i ngồi canh
        if ($mang[$max] < $mang[$i]){
            $max = $i;
        }
    }
 
    // Trả về vị trí nhỏ nhất
    return $max;
}

3. Sắp xếp chọn trong PHP tăng dần

function SelectionSortAscending($mang)
{
    // Đếm tổng số phần tử của mảng
    $sophantu = count($mang);
 
    // Lặp để sắp xếp
    for ($i = 0; $i < $sophantu - 1; $i++)
    {
        // Tìm vị trí phần tử nhỏ nhất
        $min = $i;
        for ($j = $i + 1; $j < $sophantu; $j++){
            if ($mang[$j] < $mang[$min]){
                $min = $j;
            }
        }
 
        // Sau khi có vị trí nhỏ nhất thì hoán vị
        // với vị trí thứ $i
        $temp = $mang[$i];
        $mang[$i] = $mang[$min];
        $mang[$min] = $temp;
    }
 
    // Trả về mảng đã sắp xếp
    return $mang;
}

4. Sắp xếp chọn trong PHP giảm dần

function SelectionSortDescending($mang)
{
    // Đếm tổng số phần tử của mảng
    $sophantu = count($mang);
    // Lặp để sắp xếp
    for ($i = 0; $i < $sophantu - 1; $i++)
    {
        // Tìm vị trí phần tử lớn nhất
        $max = $i;
        for ($j = $i + 1; $j < $sophantu; $j++){
            if ($mang[$j] > $mang[$max]){
                $max = $j;
            }
        }
        // Sau khi có vị trí lớn nhất thì hoán vị
        // với vị trí thứ $i
        $temp = $mang[$i];
        $mang[$i] = $mang[$max];
        $mang[$max] = $temp;
    }
    // Trả về mảng đã sắp xếp
    return $mang;
}

5. Lời Kết

Có nhiều bạn thắc mắc tại sao trong vòng lặp for tôi chỉ lặp như sau:

for ($i = 0; $i < $sophantu - 1; $i++)

Lý do là phần tử cuối cùng đã ở đúng vị trí rồi nên ko cần phải lặp nữa, vì vậy điều kiện dừng vòng lặp là $i < $sophantu - 1.

Giải thuật sắp xếp chọn trong php rất là hay, trong phần lời giải mình không giải thích nhiều vì giải thích bằng giấy bút thì khó nói, các bạn coi phần ghi chú và làm theo và suy nghĩ sẽ hiểu ra thôi, hồi xưa mình cũng thế mà =). Bài tiếp theo chúng ta sẽ tìm hiểu một thuật toán sắp xếp khác, đó là thuật toán sắp xếp chèn, chúc các bạn cuối tuần vui vẻ nhé.

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