[Thuật toán sắp xếp NỔI BỌT (Bubble Sort)]

Nội Dung:
   1. Thuật toán hoạt động như thế nào.
   2. Cài đặt thuật toán.
   3. Bình luận.

#1. Thuật toán hoạt động như thế nào?

     Hôm nay chúng ta lại tiếp cận với một thuật toán sắp xếp nữa, cũng thuộc dạng kinh điển nha. Đó chính là thuật toán sắp xếp NỔI BỌT (Bubble Sort). Nghe cái tên có vẻ "cool" nhưng hơi khó hiểu nhỉ. Vậy ta lại cùng nhau coi phim, à lộn coi animation để hình dung dễ hơn về thuật toán này nhé.

Màu xanh lá: là biến chạy đánh dấu hai phần tử kề nhau đang được xét.

Màu cam: là các phần tử đã được sắp xếp.

     

     Nếu bạn nào có coi qua bài viết của mình về hai các thuật toán sắp xếp chọn và sắp xếp chèn thì có thể thấy với thuật toán sắp xếp nổi bọt thì đoạn animation đã bớt đi một màu (màu đỏ). Liệu thuật toán này có dễ hiểu hơn?

     Sắp xếp NỔI BỌT, cái tên có nghĩa là gì. Chắc hẳn nhiều bạn từng đun nước sôi đúng không, khi mà nước sôi thường sẽ có các bọt khí nổi lên. Ở đây ý nghĩa của từ Bubble - Nổi bọt cũng tương tự như vậy. Chúng ta đẩy những phần tử nhỏ nhất (hoặc lớn nhất) lên đầu qua các bước đổi chỗ.

     Ok, nhìn thì thấy dễ hình dung đúng không? Ở đây chúng ta thực hiện việc đổi chỗ hai phần tử cạnh nhau nếu phần tử phía trước lớn hơn phần tử phía sau.

     Dễ thấy rẳng cứ sau mỗi vòng lặp thì chúng ta sẽ có được phần tử lớn nhất trong số các phần tử chưa được sắp xếp. Và một lưu ý đó là những phần tử đã được lặp (màu cam) sẽ không cần phải duyệt lại trong các bước lặp tiếp theo.

     Thuật toán cũng không có gì quá khó hiểu đúng hem. Có thể nói bản chất là việc chúng ta so sánh đôi một các phần tử, ok vậy chúng ta bắt tay vào chuyên mục cài đặt bằng ngôn ngữ lập trình thôi. 

#2. Cài đặt thuật toán.

Cài đặt bằng C++

1. #include<iostream>  
2. using namespace std;  
3.   
4. main() {  
5.     int data[] = {9, 14, 3, 2, 43, 11, 58, 22};  
6.     int size = sizeof(data) / sizeof(int);  
7.     for(int i = 0; i < size-1; i++){  
8.         for(int j = 1; j < size-i; j++){  
9.             if(data[j-1] > data[j]){  
10.                 //ham swap co san trong c++  
11.                 swap(data[j-1], data[j]);  
12.             }  
13.         }  
14.     }  
15.     for(int i = 0; i < size; i++)  
16.         cout << data[i] << " ";  
17. }  

Cài đặt bằng Java

1. public class BubbleSort {  
2.     public static void main(String[] args) {  
3.         int[] data = {9, 14, 3, 2, 43, 11, 58, 22};  
4.         for(int i = 0; i < data.length-1; i++){  
5.             for(int j = 1; j < data.length - i; j++){  
6.                 if (data[j-1] > data[j]) {  
7.                     int temp = data[j-1];  
8.                     data[j-1] = data[j];  
9.                     data[j] = temp;  
10.                 }  
11.             }  
12.         }  
13.         for (int i = 0; i < data.length; i++){  
14.             System.out.println(data[i]);  
15.         }  
16.     }  
17. }  

Cài đặt bằng Python

1. def bubble_sort():  
2.     data = [9, 14, 3, 2, 43, 11, 58, 22]  
3.     for i in range(0, len(data)-1):  
4.         for j in range(1, len(data)-i):  
5.             if data[j-1] > data[j]:  
6.                 data[j-1], data[j] = data[j], data[j-1]  
7.     for x in range(0, len(data)):  
8.         print(data[x])  
9. bubble_sort()  

     OK, lại ngồi review code tý nhỉ. Như thường lệ mình có triển khai code trên ba ngôn ngữ lập khá phổ biến hiện nay đó là Cpp, Java, Python (thực ra là còn javascript nữa nhưng thằng này để các bạn tìm hiểu 😆). Bạn nào code ngôn ngữ nào quen có thể dễ dàng hình dung hơn (cơ mà toàn cú pháp cơ bản đúng hem các bạn)

     Lan man qué, chúng ta có gì và phải làm gì nhỉ:

     - Input: là một mảng các phần tử chưa được sắp xếp (ở đây mình đặt tên là data). Các bạn có thể                       viết một hàm sinh ra một mảng random với size nào đó để test cũng ok đấy.

     - Output: đưa ra một mảng các phần tử sau khi sắp xếp (có thể tăng dần hoặc giảm dần)

[2, 3, 9, 11, 14, 22, 43, 58]

     Trước tiên cũng như những thuật toán trước chúng ta phải duyệt qua các phần tử vậy cần một vòng lặp for bên ngoài lặp từ đầu cho đến phần tử cuối cùng. Ok, vòng lặp ngoài chỉ có chắc năng vậy thôi.

       Vòng lặp bên trong mới có nhiều điều để nói. Nếu nhìn vào mô phỏng thuật toán thì ta nghĩ đơn giản vòng lặp này thực hiện việc lặp qua các phần tử và đổi chỗ. Vậy sao không cho nó chạy một phát từ đầu đến cuối như vòng lặp ngoài như này: 

        Về lý thuyết thì hoàn toàn okkk không có gì sai cả. Nhưng ở đây ta gặp một vấn đề đó là độ phức tạp thuật toán khi đó sẽ lớn. Vì sao? Các bạn để ý cái animation nhé, có bao giờ nó thực hiện lặp lại qua các phần tử màu vàng không? Không đúng không, tại sao? Đơn giản thôi vì các phần tử đó đã vào đúng vị trí của nó và ta không cần lặp qua để sắp xếp nữa.

        Chính vì vậy vòng lặp bên trong sẽ chạy đến data.lenght - i (trừ đi i nghĩa là trừ số phần tử đã vào vị trí). Một câu hỏi nữa, sao lại chạy từ j = 1. Nếu cho chạy từ 0 thì chúng ta sẽ viết code như sau:

         Ở đây chỉ khác ở chỗ chúng ta viết đoạn code thực hiện đổi chỗ hai số thôi. Nếu bạn viết code đổi chỗ như khối màu đỏ số (2) kia kết hợp với cho for j = 0 to data.length - i thì rất có thể bạn sẽ gặp một ngoại lệ "ArrayIndexOutOfBoundsException" vì truy xuất ngoài mảng. Vậy người ta viết như code mẫu bên trên để tranh ngoại lệ này.

         Ok, chắc các bạn đã hình dung được về thuật toán này. Còn đoạn đổi chỗ thì mình không nói lại nha.

#3. Bình luận.

        Sắp xếp nổi bọt có tư tưởng khá là đơn giản nhưng việc cài đặt thuật toán lại phải lưu ý để tránh việ làm tăng độ phức tạp của thuật toán. Ngoài ra cũng cần lưu ý cách đổi chỗ hai phần tử trong thuật toán này để tránh việc gặp phải ngoại lệ tràn mảng "ArrayIndexOutOfBoundsException"

        Về độ phức tạp không gian và thời gian thì như sau. Ở đây mình cũng sẽ chưa đi vào giải thích cụ thể về khía cạnh này. Ta sẽ giành một bài riêng khi mà đã hiểu được một số thuật toán cơ bản khác nữa.

     + Độ phức tạp thời gian:

          - Trường hợp tốt: O(n)

          - Trường hợp xấu: O(n^2)

     + Độ phức tạp không gian: O(1)