Mục lục:
Định nghĩa - Bubble Sort có nghĩa là gì?
Sắp xếp bong bóng là một thuật toán sắp xếp hoạt động bằng cách lặp đi lặp lại các danh sách cần sắp xếp, so sánh từng cặp vật phẩm liền kề và hoán đổi chúng nếu chúng sai thứ tự. Quy trình vượt qua này được lặp lại cho đến khi không yêu cầu hoán đổi, chỉ ra rằng danh sách đã được sắp xếp. Sắp xếp bong bóng được tên của nó bởi vì các yếu tố nhỏ hơn bong bóng về phía đầu danh sách.
Sắp xếp bong bóng cũng được gọi là sắp xếp chìm hoặc sắp xếp so sánh.
Techopedia giải thích Sắp xếp bong bóng
Sắp xếp bong bóng có trường hợp xấu nhất và độ phức tạp trung bình là O (n2), trong đó n là số lượng vật phẩm được sắp xếp. Không giống như các thuật toán sắp xếp khác, sắp xếp bong bóng phát hiện xem danh sách được sắp xếp có được tích hợp hiệu quả vào thuật toán hay không. Hiệu suất sắp xếp bong bóng trên một danh sách đã được sắp xếp là O (n).
Vị trí của các yếu tố trong sắp xếp bong bóng đóng vai trò quan trọng trong việc xác định hiệu suất. Các yếu tố lớn khi bắt đầu không gây ra vấn đề vì chúng dễ dàng bị tráo đổi. Các yếu tố nhỏ về phía cuối di chuyển đến đầu từ từ. Như vậy, các yếu tố này được gọi là thỏ và rùa.
Thuật toán sắp xếp bong bóng có thể được tối ưu hóa bằng cách đặt các phần tử lớn hơn ở vị trí cuối cùng. Sau mỗi lần vượt qua, tất cả các yếu tố sau lần trao đổi cuối cùng được sắp xếp và không cần phải kiểm tra lại, do đó bỏ qua việc theo dõi các biến được hoán đổi.
