Bài 17: Thuật toán sắp xếp chọn trong ph - Học lập trình PHP căn bả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

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