I. Làm quen với thuật toán

Nghe đến tên gọi thú vị của thuật toán sắp xếp này có khi các bạn cũng hình dung sơ sơ về phương thức làm việc của thuật toán rồi chứ. Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp cơ bản, chúng ta sẽ thao tác dữ liệu cần sắp xếp "nổi bọt" lần lượt theo thứ tự chúng ta mong muốn (từ trái sang phải, từ dưới lên trên, từ trên xuống dưới, ...).

II. Miêu tả về thuật toán

1. Ý tưởng

Ý tưởng thuật toán cũng giống như việc xếp hàng trong giờ thể dục. Thầy giáo thể dục muốn xếp các bạn 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 222 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ì đổi chỗ 222 bạn cho nhau.

2. Chi tiết thuật toán

Xét một mảng gồm nnn số nguyên: a1,a2,a3,...,ana_1, a_2, a_3, ..., a_na1​,a2​,a3​,...,an​

III. Những điều lưu ý của thuật toán

1. Ưu điểm

2. Nhược điểm

3. Thời gian tính và độ phức tạp

Với mỗi i=1,2,..,n−1i = 1,2,..,n-1i=1,2,..,n−1 ta cần n−in-in−i phép so sánh. Do đó số nhiều nhất các lần so sánh và đổi chỗ trong giải thuật là: (n−1)+(n−2)+...+2+1=(n−1)n2(n-1)+(n-2)+...+2+1=frac{(n-1)n}{2}(n−1)+(n−2)+...+2+1=2(n−1)n​ Do đó ta có độ phúc tạp là O(n2)O(n^2)O(n2).

IV. Tài liệu tham khảo

©️ Tác giả: Lê Ngọc Hoa từ Viblo