Tìm hiểu giải thuật sắp xếp Bubble Sort

Sharing is caring!

Xin chào các bạn Hi , hôm trước tui đã viết một bài về giải thuật Selection Sort. Hôm nay, tui sẽ viết tiếp giải thuật còn lại đó là Bubble Sort. Giải thuật này cũng tương đối dễ hiểu và dễ cái đặt, về mặt ý tưởng nó cũng khá là gần giống với Selection Sort nhưng có thay đổi một chút xíu trong việc đẩy phần tử nhỏ nhất về phía đầu array. Nói nhiều quá thành ra lan man mất, thôi vào luôn cho nóng nhá.

1. Bubble Sort

Giải thuật này dựa trên tính chất đó là cái gì nhẹ thì sẽ nổi lên và cái gì nặng thì nó chìm xuống, nghe có vẻ đơn giản ha.

Ý tưởng như sau:

Đi từ cuối array đến đầu array, so sánh phần tử thứ i và i – 1, nếu phần tử thứ i nhỏ hơn phần tử thứ i – 1 thì ta hoán vị hai phần tử này. Cứ như vậy ta so sánh từng cặp cho đến đầu array thì ta được một lượt. Nếu array có n phần tử thì ta có n – 1 lượt đi từ cuối array đến đầu array. Ý tưởng là như vậy, nhưng để cho dễ hình dung, mời các bạn xem ví dụ cụ thể sau.

Ví dụ:

Vẫn là cái array gồm 8 phần tử như trong bài Selection Sort bubble_00

màu xanh dương: phần tử của array đã được sắp xếp.

màu đỏ: là phần tử có giá trị nhỏ hơn phần tử đứng trước nó.

màu tím: là phần tử được neo. Ta đi từ cuối mảng đến vị trí của phần tử được neo.

mũi tên màu xanh lục: hoán vị hai phần tử đó.

mũi tên màu cam: hai phần tử đó đã hoán vị.

Bước 1:

Tui neo phần tử đầu tiên có giá trị 30, sau đó tui đi ngược từ cuối mảng lên đến vị trí neo(là vị trí 0), lần lượt so sánh từng cặp:

cặp 90 – 14

bubble_sort_01_1

Hoán vị 90 với 14. Sau khi hoán vị, ta lại thấy cặp 25 – 14:

bubble_sort_01_2

Hoán vị 25 với 14, hoán vị xong ta lại thấy cặp 70 – 14:

bubble_sort_01_3

Hoán vị 70 với 14, tiếp tục ta thấy cặp 30 – 10:

bubble_sort_01_4

Hoán vị 30 với 10. Vậy là hết lượt đầu tiên, tui đã đẩy phần tử có giá trị 10 về đầu array:

bubble_sort_01_5

Bước 2:

Tui lại neo phần tử thứ 1 là 30, tiếp tực đi từ cuối mảng đến vị trí neo. Lúc này ta thấy cặp 90 – 49

bubble_sort_02_1

Hoán vị 90 với 49, tiếp tục đi về phía ví trị neo, ta lại thấy cặp 70 – 25

bubble_sort_02_2

Hoán vị 70 với 25, ta lại thấy cặp 30 – 14

bubble_sort_02_3

Hoán vị 30 với 14. Hết lượt thứ 2 ta đẩy được thêm phần tử có giá trị 14 về đầu array.

bubble_sort_02_4

Bước 3:

Tui neo phần tử vị trí thứ 2 lúc này có giá trị là 30 và tiếp tục đi từ cuối array đến vị trí neo. Lúc này tui thấy cặp 90 – 65

bubble_sort_03_1

Hoán vị 90 với 65. Sau đó ta lại gặp cặp 70 – 49

bubble_sort_03_2

Hoán vị 70 với 49. Tiếp tục ta lại có cặp 30 – 25

bubble_sort_03_3

Hoán vị 30 với 25. Vậy là đến đây, ta lại kết thúc lượt thứ 3 và đồng thời đẩy phần tử có giá trị 25 về đầu array

bubble_sort_03_4

Bước 4:

Lại neo phần tử ở vị trí thứ 3 có giá trị là 30 và tiếp tục đi từ cuối array. Lúc này ta thấy cặp 70 – 65

bubble_sort_04_1

Hoán vị 70 với 65 và tiếp tục đi về phía vị trí neo,

bubble_sort_04_2

Đến lúc này ta thấy tất cả các phần tử đã được sắp xếp theo thứ tự tăng dần

bubble_sort_04_3

Như vậy, chỉ cần qua 4 lượt, tui đã sắp xếp được array này tăng dần rồi đó. cũng dễ ha. Trên đây là ví dụ chạy bằng tay để các bạn dễ mường tượng các phần tử nó so sánh và hoán vị với nhau, bây giờ ta đến bước cài đặt thuật toán này nha.  Who-s-the-man

2. Cài đặt thuật toán Bubble Sort:

Như các bạn thấy, trong ví dụ trên ta phải đi 4 lượt và mỗi lượt ta phải duyệt array từ phía cuối mảng về đầu mảng cho đến khi đụng vị trí của phần tử được neo. Do đó, tui sẽ dùng 2 vòng lặp for để thực hiện

  1. Vòng for i cho việc đi qua các lượt (chỉ cần đi đến phần tử kế cuối thôi)
  2. Vòng for j cho việc duyệt array từ phía cuối đi lên

Code snippet for C#:

Mỗi lần biến i tăng thêm 1 thì đồng thời đó cũng là vị trí neo luôn. Trong vòng lặp for j, điều kiện để vòng lặp for j dừng lại và không vượt qua vị trí neo là j > i (tại vì trước vị trí neo sẽ là cái phần tử đã được sắp xếp).

Ở đây, tui dùng biến nochange để kiểm soát một việc là trong vòng lặp for i chưa kết thúc mà các phần tử đã được sắp xếp rồi thì mình dừng lại luôn.

Như ví dụ trên, ở lượt thứ 4, sau khi hoán vị 70 với 65. Nếu ta tiếp tục neo phần tử ở vị trí thứ 4 có giá trị là 49 và lại đi từ cuối array đi lên thì ta sẽ không tìm thấy cặp số nào cần hoán vị cả.

bubble_sort_04_4

Đó là lý do tui dùng biến nochange để kiểm soát việc này. Cứ mỗi một lượt(vòng lặp for i) tui khởi động biến nochange true. Trong quá trì đi từ cuối array đi lên, nếu có cặp số nào cần hoán vị (điều kiện là a[j] < a[j – 1]), có nghĩa là có thay đổi, khi đó tui gán giá trị cho nochange là false. Sau khi kết thúc vòng lặp for j, chỉ cần kiểm tra biến nochange:

  1. nếu nochange == true thì thoát vòng lặp for i, kết thúc quá trình sắp xếp.
  2. nếu nochange == false thì lại tiếp tục lượt kế tiếp.

Full code for C#:

Code snippet for PHP:

Nếu các bạn đọc đến chổ này thì tui xin cảm ơn các bạn đã có cố gắng đọc bài viết này của tui. Có thể sẽ rất khó “xơi” cái món giải thuật sắp sếp này, nhưng tui cũng hy vọng bài viết này và bài Selection Sort có thể giúp ích cho các bạn trong việc nâng cao kỹ năng lập trình của mình.  Bye

Sharing is caring!

Tìm hiểu giải thuật sắp xếp Selection Sort
Kiểm tra một năm bất kỳ có phải là năm nhuận (leap year)

Vincent Le

Tui là Lê Minh Đạt, tên tiếng anh là Vincent(do thích nhân vật Vincent Valentine, ai từng là fan của trò Final Fantasy VII thì sẽ biết nhân vật này, hehe). Đang tập tành làm một blogger viết về mảng lập trình, mong muốn được chia sẻ những gì đã học được, tích góp được trong 10 năm đi làm thợ code.

shares