Tìm hiểu chi tiết Bubble Sort: Thuật toán sắp xếp nổi bọt

Các thuật toán sắp xếp đóng vai trò quan trọng trong việc tổ chức và quản lý dữ liệu lập trình, đảm bảo hiệu suất cũng như tính bền vững của các ứng dụng. Trong đó, Bubble Sort là một trong những thuật toán sắp xếp đầu tiên được giới thiệu cho những người mới.

Bubble Sort là gì?

Bubble Sort hay còn gọi là thuật toán sắp xếp nổi bọt hoặc sắp xếp bằng so sánh trực tiếp, là một trong những thuật toán sắp xếp đơn giản và dễ hiểu nhất. Nó thường được giới thiệu trong các bài học mở đầu về khoa học máy tính, lập trình vì độ dễ tiếp cận của nó.

Nguyên lý hoạt động của Bubble Sort rất trực quan. Thuật toán này hoạt động bằng cách liên tục lặp lại việc so sánh hai phần tử liền kề trong dãy và hoán đổi vị trí của chúng nếu chúng không theo thứ tự mong muốn. Quá trình này được lặp lại cho đến khi toàn bộ dãy đã được sắp xếp hoàn chỉnh.

Bubble Sort - hình 1

Cách thức hoạt động cụ thể của Bubble Sort là thuật toán bắt đầu bằng việc duyệt qua dãy và so sánh cặp phần tử đầu tiên. Nếu cặp phần tử đó không theo thứ tự mong muốn (tăng dần hoặc giảm dần tùy yêu cầu), thuật toán sẽ hoán đổi vị trí của chúng. Sau đó, nó tiếp tục với cặp phần tử tiếp theo cho đến khi tới cuối dãy. Quá trình này được lặp lại nhiều lần để toàn bộ dãy được sắp xếp hoàn chỉnh, có nghĩa là không còn cặp phần tử nào cần hoán đổi vị trí.

Ví dụ minh họa về Bubble Sort

Để hiểu rõ hơn, chúng ta hãy xem xét một ví dụ cụ thể. Giả sử chúng ta có một danh sách các số sau: [5, 3, 8, 4, 2].

Lượt duyệt thứ nhất:

So sánh 5 và 3, hoán đổi xong ta có [3, 5, 8, 4, 2].
So sánh 5 và 8, không hoán đổi ta có [3, 5, 8, 4, 2].
So sánh 8 và 4, hoán đổi xong ta có [3, 5, 4, 8, 2].
So sánh 8 và 2, hoán đổi xong ta có [3, 5, 4, 2, 8].

Phần tử 8 đã “nổi” lên vị trí cuối cùng.

Lượt duyệt thứ hai:

So sánh 3 và 5, không hoán đổi thì ta có [3, 5, 4, 2, 8].
So sánh 5 và 4, thực hiện hoán đổi ta có [3, 4, 5, 2, 8].
So sánh 5 và 2, hoán đổi xong ta có [3, 4, 2, 5, 8].

Phần tử 5 đã “nổi” lên ở vị trí gần cuối.

Lượt duyệt thứ ba:

So sánh 3 và 4, không hoán đổi ta có [3, 4, 2, 5, 8].
So sánh 4 và 2, hoán đổi thì có [3, 2, 4, 5, 8].

Phần tử 4 đã "nổi" lên vị trí trước số 5.

Lượt duyệt thứ tư:

So sánh 3 và 2, thực hiện hoán đổi có danh sách là [2, 3, 4, 5, 8].

Danh sách đã được sắp xếp hoàn toàn.

Bubble Sort - hình 2

Đánh giá về thuật toán Bubble Sort

Phân loại: Giải thuật sắp xếp.
Độ phức tạp trong trường hợp tốt nhất: O(n). Trường hợp tốt nhất xảy ra khi danh sách đã được sắp xếp, và thuật toán chỉ cần một lần duyệt qua để xác nhận rằng không cần phải hoán đổi phần tử nào.
Độ phức tạp trong trường hợp trung bình: O(n^2). Trường hợp trung bình xảy ra khi các phần tử trong danh sách được sắp xếp ngẫu nhiên.
Thời gian xấu nhất: O(n^2). Trường hợp xấu nhất xảy ra khi danh sách được sắp xếp ngược lại so với thứ tự mong muốn.
Không gian bộ nhớ được sử dụng: O(1). Thuật toán sử dụng không gian bộ nhớ cố định, không phụ thuộc vào kích thước của danh sách cần sắp xếp.

Bubble Sort - hình 3

Ưu và nhược điểm của Bubble Sort trong Java

Ưu điểm

Thuật toán sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán sắp xếp dễ tiếp cận nhất, đặc biệt hữu ích trong việc giảng dạy các nguyên tắc cơ bản về thuật toán sắp xếp. Dưới đây là những ưu điểm nổi bật của Bubble Sort:

Đơn giản và dễ hiểu: Cách thức hoạt động của thuật toán rất trực quan bằng cách liên tục so sánh và hoán đổi các phần tử liền kề, các phần tử lớn dần “nổi” lên trên cùng, giống như bong bóng trong nước.
Dễ triển khai: Việc triển khai Bubble Sort yêu cầu rất ít dòng mã, dễ dàng viết và kiểm tra. Trong hầu hết các ngôn ngữ lập trình, Bubble Sort có thể được triển khai chỉ với một vòng lặp lồng nhau đơn giản. Dưới đây là một ví dụ minh họa Bubble Sort bằng ngôn ngữ Python:

Bubble Sort - hình 4

Sắp xếp tại chỗ: Bubble Sort là một thuật toán sắp xếp tại chỗ (in-place sorting), có nghĩa là nó không yêu cầu thêm bộ nhớ ngoài không gian bộ nhớ đã được cấp phát cho danh sách đầu vào.
Phát hiện danh sách đã sắp xếp: Trong trường hợp tốt nhất, khi danh sách đã được sắp xếp, Bubble Sort chỉ cần một lần duyệt qua danh sách để xác nhận rằng không cần thực hiện hoán đổi nào. Nó giúp giảm thời gian thực thi xuống còn O(n) trong trường hợp tốt nhất.
Phù hợp với các danh sách nhỏ hoặc gần như đã sắp xếp: Bubble Sort hoạt động hiệu quả đối với các danh sách nhỏ hoặc những danh sách đã gần như được sắp xếp. Trong những trường hợp này, số lần hoán đổi và so sánh sẽ giảm đáng kể, làm cho thuật toán trở nên tương đối nhanh chóng và hiệu quả.
Tính ổn định: Bubble Sort là một thuật toán sắp xếp ổn định, nghĩa là nó giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau. Tính ổn định này rất quan trọng trong một số ứng dụng, chẳng hạn như khi cần giữ nguyên thứ tự ban đầu của các bản ghi có cùng khóa.

Bubble Sort - hình 5

Nhược điểm

Mặc dù thuật toán sắp xếp nổi bọt (Bubble Sort) có nhiều ưu điểm, nó cũng tồn tại một số nhược điểm đáng kể:

Thời gian thực thi chậm: Bubble Sort cần nhiều thời gian để sắp xếp các phần tử, đặc biệt khi phải xử lý các danh sách lớn. Do cách hoạt động dựa trên nhiều lần so sánh và hoán đổi các phần tử liền kề, thời gian thực thi của thuật toán này chậm hơn so với các thuật toán sắp xếp khác.
Độ phức tạp thời gian cao: Độ phức tạp thời gian của Bubble Sort trong trường hợp trung bình hay xấu nhất là O(n^2), nơi n là số lượng phần tử trong danh sách. Điều này có nghĩa là thời gian thực thi tăng khi số lượng phần tử tăng, làm cho Bubble Sort không thực tế khi xử lý các danh sách lớn.
Hiệu quả kém với danh sách ngẫu nhiên hoặc ngược chiều: Bubble Sort hoạt động tốt với các danh sách gần như đã sắp xếp, nhưng hiệu suất giảm mạnh khi xử lý các danh sách có thứ tự ngẫu nhiên hoặc ngược chiều, dẫn đến phải thực hiện nhiều phép hoán đổi cần thiết.
Thiếu tối ưu hóa: So với các thuật toán sắp xếp khác như Quick Sort hay Merge Sort, Bubble Sort thiếu các phương pháp tối ưu hóa giúp giảm số lần so sánh và hoán đổi, làm cho nó trở nên kém hiệu quả.
Ít ứng dụng thực tế: Do các nhược điểm về thời gian thực thi cũng như về mức độ hiệu quả, Bubble Sort hiếm khi được sử dụng trong các ứng dụng thực tế, mà thường chỉ được dùng trong giảng dạy để minh họa các khái niệm cơ bản về thuật toán và sắp xếp.

Bubble Sort - hình 6

Mặc dù Bubble Sort không phải là lựa chọn tốt nhất cho các danh sách lớn, nhưng với sự đơn giản, dễ hiểu cùng khả năng sắp xếp tại chỗ của nó, Bubble Sort vẫn là một điểm khởi đầu tốt cho những ai mới bắt đầu khám phá các thuật toán sắp xếp.

Giải thuật cho Bubble Sort

Sắp xếp từ trên xuống

Giả sử dãy cần sắp xếp có n phần tử.
Bắt đầu từ phần tử đầu tiên, so sánh hai phần tử liên tiếp là phần tử đầu và phần tử thứ hai.
Nếu phần tử đứng trước lớn hơn phần tử đứng sau, hoán đổi chúng.
Tiếp tục so sánh cặp phần tử thứ hai và thứ ba, rồi cặp thứ ba và thứ tư,..., cho đến khi so sánh (và hoán đổi nếu cần) phần tử thứ n-1 với phần tử thứ n.
Sau lần duyệt đầu tiên, phần tử cuối cùng sẽ là phần tử lớn nhất trong dãy.
Quay lại đầu danh sách, thực hiện so sánh và hoán đổi từ phần tử đầu đến phần tử thứ n-2.
Lặp lại quá trình này, mỗi lần duyệt giảm dần số phần tử cần so sánh đi một, cho đến khi không còn phần tử nào cần hoán đổi nữa.

Lưu ý: Nếu trong một lần duyệt qua danh sách không có bất kỳ cặp phần tử nào bị hoán đổi, điều này có nghĩa là danh sách đã được sắp xếp xong và không cần thực hiện thêm các lần duyệt khác.

Minh họa bằng mã giả:

Bubble Sort - hình 7

Sắp xếp từ dưới lên

Giả sử dãy cần sắp xếp có n phần tử.
Bắt đầu từ cặp phần tử cuối cùng (phần tử thứ n-1 và phần tử thứ n), so sánh hai phần tử.
Nếu phần tử đứng trước lớn hơn phần tử đứng sau, hoán đổi chúng.
Tiếp tục so sánh cặp phần tử thứ n-2 và n-1, rồi cặp thứ n-3 và n-2,..., cho đến khi so sánh (hoán đổi nếu cần) cặp phần tử thứ nhất và thứ hai.
Sau lần duyệt đầu tiên, phần tử nhỏ nhất sẽ nổi lên vị trí đầu tiên của dãy.
Quay lại phần tử thứ hai, thực hiện so sánh cũng như hoán đổi từ phần tử thứ hai đến phần tử cuối cùng.
Lặp lại quá trình này, mỗi lần duyệt giảm dần số phần tử cần so sánh từ phía cuối dãy, cho đến khi không còn phần tử nào cần hoán đổi nữa.

Lưu ý: Nếu trong một lần duyệt qua danh sách từ cuối lên đầu không có bất kỳ cặp phần tử nào bị hoán đổi, điều này có nghĩa là danh sách đã được sắp xếp xong và không cần thực hiện thêm các lần duyệt khác.

Minh họa bằng mã giả:

Bubble Sort - hình 8

Trong hai đoạn mã giả trên, biến swapped được sử dụng để kiểm tra xem có bất kỳ phần tử nào được hoán đổi trong lần duyệt qua danh sách hay không. Nếu không có phần tử nào được hoán đổi, vòng lặp sẽ kết thúc sớm, vì danh sách đã được sắp xếp.

Giảm bớt vòng duyệt

Giả sử dãy cần sắp xếp có n phần tử.
Khởi tạo biến i bằng n.
Lặp lại quá trình sau cho đến khi i lớn hơn 1:

Khởi tạo biến cờ has_swapped bằng 0 để theo dõi việc hoán đổi.
Duyệt qua các phần tử từ 1 đến i - 1: Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, hoán đổi chúng và đặt has_swapped bằng 1.
Nếu không có hoán đổi nào xảy ra (has_swapped bằng 0), kết thúc thuật toán vì danh sách đã được sắp xếp.
Giảm i đi 1 để không cần kiểm tra lại phần tử đã được sắp xếp.

Mã giả cho thuật toán Bubble Sort với giảm bớt vòng duyệt:

Bubble Sort - hình 9

Lưu ý: Sử dụng biến i để giảm số lượng phần tử cần kiểm tra sau mỗi lần duyệt, giúp giảm số vòng lặp cần thiết. Sử dụng biến cờ has_swapped để kiểm tra xem có bất kỳ hoán đổi nào xảy ra trong lần duyệt hiện tại không. Nếu không, danh sách đã được sắp xếp và ta có thể kết thúc thuật toán sớm.

Tạm kết

Mặc dù Bubble Sort có thể không phải là thuật toán sắp xếp hiệu quả nhất, nhưng nó vẫn là một công cụ hữu ích trong lập trình, đặc biệt là đối với những người mới bắt đầu. Hy vọng rằng thông qua bài viết này, bạn sẽ củng cố thêm kiến thức của mình về thuật toán sắp xếp!

Nếu bạn là một lập trình viên và muốn sắm cho mình một chiếc laptop, PC có hiệu suất làm việc ổn định, đừng quên ghé qua website của FPT Shop để tham khảo ngay những sản phẩm với mức giá ưu đãi nhất nhé. Bài viết xin đề xuất tới bạn danh sách laptop Dell bán chạy: