Một số giải thuật cơ bản Phần 2_Bubble Sort

Tiếp theo giải thuật Chèn trực tiếp(Insertion sort) mình muốn nói tiếp 1 giải thuật cuối cùng trong phần bài viết các giải thuật cơ bản này là Giải Thuật Nổi bọt(Bubble Sort).Chúng tar bắt đầu nhé.

 Ý tưởng: (sắp tăng)
–Dựa vào ý tưởng đưa phần tử nhỏ lên đầu mảng và lớn về phía sau mảng.
–Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đứng đầu dãy hiện hành, sau đó không xét tới nó ở bước tiếp theo, do vậy ở lần lặp thứ i có vị trí đầu dãy là i.

Minh họa ví dụ Bubble sort
 Cho dãy số a

 Bước 1: Đưa phần tử nhỏ bắt đầu từ cuối mảng (j=7) lên vị trí i = 0

Bước 2: Đưa phần tử nhỏ bắt đầu từ cuối mảng (j=5) lên vị trí i = 1

Bước 3: Đưa phần tử nhỏ bắt đầu từ cuối mảng (j=6) lên vị trí i = 2


Cài đặt 

Mã nguồn PHP:
void Bubblesort(int a[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
swap(a[j],a[j-1]);
}

Một số bài tập lý thuyết minh họa và cài đặt.
Bài tập minh họa
 Minh họa thao tác sắp xếp dữ liệu theo phương pháp Bubble
Sort cho các dãy dữ liệu sau:
 Sắp xếp tăng:
 13 8 12 6 9 10 12 7
 A H K R E C Z G
Sắp xếp giảm
 13 8 12 6 9 10 12 7
 A H K R E C Z G

Bài tập cài đặt
 Viết bổ sung các hàm vào chương trình xử lý mảng 1 chiều
các hàm thực hiện những yêu cầu sau:
1. Viết hàm sắp xếp tăng theo PP Bubble sort cho dữ liệu số
nguyên/số thực/ký tự/ chuỗi ký tự.
2. Viết hàm sắp xếp tăng theo PP Bubble sort cho dữ liệu số
nguyên/số thực/ký tự/ chuỗi ký tự

Vậy là mình đã giới thiệu qua các giải thuật tìm kiếm và sắp xếp cơ bản nhất,Thời gian tới mình sẽ viết bài về các giải thuật gọi là hơi khó hơn chút.
Các giải thuật cho các bài viết tiếp theo ví dụ như là:Merge Sort,Quick Sort,Giải thuật tìm kiếm Knuth-Morris-Pratt,Giải thuật Boyer – Moore.Các bạn đón xem nhé.
Chúc các bạn học tốt.

Advertisements

Posted on September 28, 2013, in CTDL - GiảiThuật and tagged , , , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: