Học về thuật toán sắp xếp tăng dần, giảm dần trong PHP

Học về thuật toán sắp xếp tăng dần, giảm dần trong PHP là vấn đề được nhiều lập trình viên quan tâm, bởi những kiến thức trên trường lớp là không đủ, vì vậy bài Học về thuật toán sắp xếp tăng dần, giảm dần trong PHP sẽ chia sẻ tới bạn nhiều thông tin hữu ích

Mọi người vẫn hỏi tôi về việc học lập trình nói chung và PHP nói riêng có cần năng khiếu hay quá khó để tiếp cận hay không. Thì tôi có thể trả lời rằng, học lập trình cũng như việc bạn học tiếng Anh hay bất kỳ một ngôn ngữ khác, bởi lập trình...là ngôn ngữ của máy tính, để máy tính đọc và máy tính thực hiện theo yêu cầu của mình, bạn thích là học được.

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:

Học về thuật toán sắp xếp tăng dần, giảm dần trong PHP

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


Hy vọng với bài viết về Học về thuật toán sắp xếp tăng dần, giảm dần trong PHP đã giải đáp giúp bạn phần nào về kiến thức lập trình PHP. Như tôi đã nói, ngôn ngữ lập trình không quan trọng bằng tư duy giải thuật, tư duy logic để giải quyết vấn đề.

Với những năm trước đây, lập trình viên là một cái nghề khó và kén chọn người học, đồng nghĩa với việc thu nhập hàng tháng của các lập trình viên luôn cao. Còn những năm gần đây, thì lập trình là môn học phổ thông, và ai cũng nên học một ngôn ngữ lập trình nào đó.

Nếu bạn còn bất kỳ câu hỏi nào trong việc học lập trình online, hãy gửi yêu cầu cho tôi qua email hoidapcode.com@gmail.com hoặc để lại comment bên dưới, tôi sẽ giải đáp trong vòng 24 giờ!

Blog hoidapcode.com là blog được tổng hợp tự động các bài học, thông tin về lập trình trên mạng internet. Nếu bạn có ý kiến hoặc đóng góp về bài viết này, hãy liên hệ với tôi!