Blog Archives

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