I. Định nghĩa thuật toán sắp xếp nổi bọt (bubble sort)

Thuật toán sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp cơ bản và phương pháp làm việc của nó khá đơn giản. Chúng ta thực hiện các thao tác trên dữ liệu cần sắp xếp bằng cách "nổi bọt" chúng lên theo thứ tự mong muốn, có thể là từ trái sang phải, từ dưới lên trên, hoặc từ trên xuống dưới, tùy theo cách thức thực hiện.

II. Miêu tả thuật toán sắp xếp nổi bọt (bubble sort)

1. Ý tưởng

Ý tưởng của thuật toán sắp xếp nổi bọt cũng giống như việc xếp hàng trong giờ thể dục. Giả sử thầy giáo thể dục muốn xếp các bạn học sinh trong lớp thành một hàng theo thứ tự từ thấp đến cao. Thầy so sánh chiều cao của hai bạn học sinh đứng cạnh nhau trong hàng, nếu bạn bên phải thấp hơn bạn bên trái, thì thầy sẽ đổi chỗ hai bạn đó cho nhau.

Quá trình này được lặp lại cho tất cả các cặp học sinh liền kề trong hàng, cho đến khi không còn cặp học sinh nào thỏa mãn điều kiện bạn bên phải thấp hơn bạn bên trái. Khi đó, ta có một hàng học sinh đã được sắp xếp từ thấp đến cao.

Cách làm này tương tự như khi các phần tử trong mảng được so sánh và đổi chỗ để đưa chúng về đúng vị trí.

2. Chi tiết thuật toán sắp xếp nổi bọt (bubble sort)

Xét một mảng gồm n số nguyên: a₁, a₂, a₃, ..., aₙ.

Với cách sắp xếp không giảm từ trái qua phải, mục đích của chúng ta là dần đưa các số lớn nhất về phía cuối dãy (ở bên phải).

Bắt đầu từ vị trí số 1, ta xét lần lượt từng cặp hai phần tử liền kề. Nếu phần tử bên phải nhỏ hơn phần tử bên trái, ta sẽ đổi chỗ hai phần tử đó. Nếu không, ta tiếp tục xét cặp tiếp theo. Bằng cách này, phần tử nhỏ hơn sẽ "nổi" lên, trong khi phần tử lớn hơn sẽ "chìm" dần và di chuyển về phía bên phải.

Khi kết thúc vòng lặp đầu tiên, chúng ta đã đưa phần tử lớn nhất về cuối dãy. Tiếp theo, trong vòng lặp thứ hai, ta lại bắt đầu từ vị trí đầu tiên và đưa phần tử lớn thứ hai về vị trí thứ hai ở cuối dãy. Quá trình này tiếp tục cho đến khi ta đã sắp xếp được tất cả các phần tử trong mảng theo thứ tự không giảm.

Hình ảnh minh họa thuật toán:

• Thuật toán C++ tham khảo:

• Thuật toán Java tham khảo: