Giải Thuật trong lâp trình

Hôm nay tôi muốn đề cập đến một số thuật toán bất li thân của IT chúng ta, đó là các thuật toán sắp xếp. Ai đã học IT thì chắc đã cài đặt nó trên C hay C++ rồi, nhưng cài trên PHP tuy nó vẫn giống nhưng hiện tại trên izwebz chưa có nên tôi có cơ hội được đăng bài này.

Giải Thuật trong lâp trình

Giới thiệu về bản thân một chút, hiện tại tôi đang học tập tại Việt Nam(tại nguồn gốc trang này từ USA) nên phải giới thiệu kĩ càng và mới hoàn thành xong năm nhất.Tôi thích giới thiệu kĩ càng bởi vì tôi cảm nhận trang web này khá tốt, nên tôi muốn nguồn kiến thức đưa ra phải đạt một chuẩn nào đó. Hy vọng là sắp tới mấy anh admin của izwebz sẽ có thể giới thiệu kĩ, và thật về hiện tại của bản thân. Tôi thấy trang web của nước ngoài hay thế lắm, tôi cảm thầy rất tin tưởng và chuyên nghiệp nữa. The end introduction …

Bubble Sort: Sắp xếp nổi bọt

Ý tưởng thuật toán: Đúng như tên gọi của nó các phần tử sẽ được sắp xếp theo kiểu phần tử nào nhỏ nhất sẽ nổi lên đầu còn các phần tử lớn sẽ chìm xuống cuối.

Code bubble sort:

/*

Author: NguyenKien.

Description: code for Bubble Sort.

Date: 4/10/2010

*/

$i=0;

$j=0;

$temp=0;

for($i=0, $i<count($a); $i++)

{

for ($j=count($a)-1; $j>$i; $j--)

If($a[$j-1] > $a[$j])

{

$temp = $a[$j-1];

$a[$j-1] = $a[$j];

$a[$j] = $temp;

}

}

foreach ($a as $value)

echo $value . “ ,”;

?>

Output:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Giải thích đoạn code trên

Đánh số key cho mảng ở trên (chú ý hen, trong C thì các chỉ số là index nhưng trong PHP lại là key).

9 -> a[0]; 8 -> a[1]; 7-> a[2]; 6->a[3]; 5->a[4]; 4->a[5]; 3->a[6]; 2->a[7]; 1->a[8]; 0->a[9];

Ở vòng for đầu tiên với $i=0 sẽ thực hiện vòng lặp for thứ hai từ vị trí thứ 9 xuống vị trí thứ 0 của mảng trên, và bắt đầu so sánh nếu số trước lớn hơn số sau thì hoán vị hai số đó. Ví dụ giá trị của a[9] =0 và a[8] =1; rõ ràng a[8] =1 (số trước) > a[9]=0 (số sau). Thỏa mãn điều kiện if ở trên nên thực hiện hoán vị hai số này và tiếp tục so sánh như vậy cho tới j=1; như vậy sau giá trị $i=0 và chạy vòng for thứ hai thì phần tử 0 tức là giái trị của a[9] sẽ được đẩy lên đầu. (phần tử nhẹ nhất nổi lên đầu.).Như vậy có thể hiểu ngay sau khi tăng $i lên một thì giá trị =1 trong mảng $a sẽ đứng kế sau giá trị 0 trong mảng $a.

/*

Author: NguyenKien.

Description: code for Selection Sort.

Date: 4/10/2010.

*/

$b = array(9, 8, 7, 6, 5, 4, 3, 2, 1, 0);

$i=0;

$j=0;

$temp =0;

$min =0;

for ($i=0; $i<count($b); $i++) {

$min =$i;

for ($j=$i+1; $j <count($b); $j++) {

if ($b[$j] < $b[$min])

{

$min =$j;

$temp =$b[$i];

$b[$i] = $b[$min];

$b[$min] =$temp;

}

}

}

foreach ($b as $value)

echo $value." ,";

?>

Output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Ý tưởng thuật toán: xét một mảng cần sắp xếp ta sẽ chọn phần tử đầu tiên và giả sử nó là nhỏ nhất, sau đó qua sử lí ta sẽ tìm ra phần tử nhỏ nhất thực sự của mảng và hoán vị nó với phần tử vừa giá sử là nhỏ nhất.

Các thao tác nhìn có vẻ na ná bubble sort nhưng nó có thêm biến $min, biến này nhằm mục đích lấy chỉ số (à quên key chứ )của phần tử nhỏ nhất mà ta vừa giả sử và xét đến điều kiện if ($b[$j] < $b[$min]) nếu đúng thì gán lại chỉ số nhỏ nhất thực sự của mảng cho biến $min. Và thực hiện hoán vị $a[$i] (là giá trị của biến min mà ta giả sử) cho $a[$min] (giá trị vừa tìm ra và nhỏ hơn giá trị của $a[$i]). Chỉ vậy thôi. Đó là Selection Sort /*

Author: NguyenKien.

Description: code for Selection Sort.

Date: 4/10/2010.

*/

$b = array(9, 8, 7, 6, 5, 4, 3, 2, 1, 0);

$i=0;

$j=0;

$temp =0;

$x =0;

for ($i=1; $i<count($b); $i++)

{

$x =$b[$i];

for ($j=$i-1; $j>=0 && $x<$b[$j]; $j--)

$b[$j+1] = $b[$j];

$b[$j+1]=$x;

}

foreach ($b as $value)

echo $value." ,";

?>

Output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Ý tưởng thuật toán: Giải thích rễ hiểu nhất cho thuật toán này là khi các bạn chời bài tiến lên(ngoài băc mình hay gọi là chơi bài nam). Các bạn sẽ nhìn thầy một nhóm quân bài đã có thứ tự nhưng con bài tiếp theo lại không đúng với thứ tự của nhóm quân bài này (ví dụ nhìn thầy 2 cơ, 3 cơ, 4 cơ A tiếp theo không phải 5 cơ mà là K cơ. Trong khi đó 5 cơ lại ở đâu đó trong các quân bài cầm trên tay) nhiệm vụ của các bạn là nhìn lướt toàn bộ các quân bài có trên tay và lấy con 5 cơ đặt đúng vị trí sau 4 cơ. Đó cũng chính là cách mà insertion sort làm việc đó các bạn.

Giải thích code: Ở vòng lặp đầu tiên khi xét $i=0, và thực hiện tất các câu lệnh ở dưới nó khi $i=0 lập tức là lấy giá trị của nó liền tức là tóm lấy $b[$i]; và so sánh nó với $b[$j]. các bạn thấy nó ở trong điều kiện vòng lặp for thư hai && đó. Nếu đúng thì sẽthực hiện hoán vị $b[$j+1] = $b[$j]; Nếu không thì chính nó là nhỏ hơn số cần so sánh rồi, nó vẫn là chính nó thể hiện qua $b[$j+1]=$x; chỉ vậy thôi

Kết luận

Trong bài viết này tôi chỉ có thể public từng dó thôi, nếu các bạn thích cài đặt them các thuật toán shellsort, radix sort, merg sort hay binary search thì phải comment(còm men) ở dưới hay một số yêu cầu về lập trình PHP (chưa nói đến lập trình ứng dụng nha vì mình chưa có khả năng do mới tiếp xúc với PHP). Mình sẽ cố hết sức để viết. Do đây là bài viết đầu tiên nên rất cần thăm dò nhã hứng của các thành viên. Mình thích khen lắm..hi hi hi. Rất vui khi được đóng góp cho izwebz.

Chú ý: Trong các đoạn code trên tôi viết chỉ để mô phỏng các thuật toán trên thôi chưa tính đến chuyện tối ưu trong tính toán, ví dụ như bubble sort nếu viết như vậy thì các bạn sẽ được điểm kém khi học môn phân tích và thiết kế giải thuật, vì nó khong tối ưu về thời gian, rõ rang với code như vậy thì kể cả mảng đã sắp xếp rồi nó vẫn phải thực gần như ngần đó đoạn code sở dĩ gần như và câu lệnh if đều không thỏa(vì nó đã sắp xếp rồi). và trong insertion sort cũng như vậy. Các bạn có thể tìm hiểu làm sao để tối ưu nhé, code các bạn sẽ public trên izwebz hen, nhớ cài đặt trên PHP. Đang ngồi trên thư viện trường rất thoải mái khi viết bài này. Chào tất cả các bạn yêu izwebz . Good luck !!!!