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

[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