Quảng cáo
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 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:
Quảng cáo
- Ý 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.
Quảng cáo
Giải thuật mô tả bằng hình:
.png)
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:
Quảng cáo
// 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;
}
Quảng cáo
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:
Quảng cáo
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é.
Quảng cáo
Các chủ đề liên quan:
- PHP căn bản
- PHP nâng cao
- MVC PHP nâng cao
- PHP Ajax
- Regular Expression PHP
- PHP CURL
- Học Htaccess
- Design Pattern
- Bảo mật website
- PHP tutorials
- PHP và MySQL
- PHP MVC căn bản
- PHP 7
- Web tin tức PHP căn bản
- Note và Chat với PHP
- PHP 8
- Danh sách hàm trong PHP
Bài viết cùng chuyên mục:
- Hàm key_exists() trong PHP
- Hàm mysqli_fetch_row() trong PHP
- Hàm end() trong PHP
- Hàm mysqli_field_count() trong PHP
- Hàm count() trong PHP
- Hàm mysqli_field_seek() trong PHP
- Hàm compact() trong PHP
- Hàm mysqli_field_tell() trong PHP
- Hàm array_values() trong PHP
- Hàm mysqli_free_result() trong PHP
- Hàm array_unshift() trong PHP
- Hàm mysqli_get_charset() trong PHP
- Hàm array_shift() trong PHP
- Hàm mysqli_get_client_stats() trong PHP
- Hàm array_unique() trong PHP
- Hàm mysqli_get_client_version() trong PHP
- Hàm array_uintesect() trong PHP
- Hàm mysqli_get_connection_stats() trong PHP
- Hàm array_sum() trong PHP
- Hàm mysqli_get_host_info() trong PHP
Quảng cáo
