Sắp xếp bong bóng so với Sắp xếp lựa chọn
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 duyệt qua danh sách được sắp xếp nhiều lần trong khi so sánh các cặp phần tử liền kề. Nếu một cặp phần tử không đúng thứ tự, chúng sẽ được hoán đổi để đặt chúng theo đúng thứ tự. Việc truyền tải này được lặp lại cho đến khi không cần hoán đổi nữa. Sắp xếp lựa chọn cũng là một thuật toán sắp xếp, bắt đầu bằng cách tìm phần tử tối thiểu trong danh sách và hoán đổi nó với phần tử đầu tiên. Quá trình này được lặp lại cho phần còn lại của danh sách bằng cách đặt các phần tử được hoán đổi theo thứ tự.
Sắp xếp bong bóng 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 duyệt qua danh sách được sắp xếp nhiều lần trong khi so sánh các cặp phần tử liền kề. Nếu một cặp phần tử không đúng thứ tự, chúng sẽ được hoán đổi để đặt chúng theo đúng thứ tự. Việc truyền tải này được lặp lại cho đến khi không cần hoán đổi nữa (có nghĩa là danh sách đã được sắp xếp). Vì các phần tử nhỏ hơn trong danh sách đứng đầu khi bong bóng nổi lên, nó được đặt tên là sắp xếp bong bóng. Sắp xếp bong bóng là một thuật toán sắp xếp rất đơn giản nhưng nó có độ phức tạp thời gian theo trường hợp trung bình là O (n2) khi sắp xếp một danh sách có n phần tử. Do đó, sắp xếp theo bong bóng không thích hợp để sắp xếp danh sách có nhiều phần tử. Nhưng do tính đơn giản của nó, sắp xếp bong bóng được dạy trong phần giới thiệu các thuật toán.
Sắp xếp Lựa chọn là gì?
Sắp xếp lựa chọn cũng là một thuật toán sắp xếp khác bắt đầu bằng cách tìm phần tử tối thiểu trong danh sách và hoán đổi nó với phần tử đầu tiên. Sau đó, phần tử tối thiểu được tìm thấy từ phần còn lại của danh sách (từ phần tử thứ hai cho đến phần tử cuối cùng trong danh sách) và được hoán đổi với phần tử thứ hai. Quá trình này được lặp lại cho phần còn lại của danh sách bằng cách đặt các phần tử được hoán đổi theo thứ tự. Vì vậy, trong sắp xếp lựa chọn, ở bất kỳ bước nào của thuật toán, danh sách được chia thành hai phần trong đó một phần chứa các phần tử đã được sắp xếp và phần kia chứa các phần tử chưa được sắp xếp. Khi thuật toán tiếp tục, danh sách được sắp xếp tăng dần từ trái sang phải. Sắp xếp lựa chọn cũng có độ phức tạp thời gian theo trường hợp trung bình là O (n2). Do đó, nó cũng không phù hợp để sắp xếp các danh sách lớn.
Sự khác biệt giữa Sắp xếp bong bóng và Sắp xếp lựa chọn là gì?
Mặc dù cả thuật toán sắp xếp bong bóng và sắp xếp lựa chọn đều có độ phức tạp theo thời gian viết hoa chữ thường trung bình là O (n2), nhưng sắp xếp bong bóng hầu như vượt trội hơn hẳn so với sắp xếp lựa chọn. Điều này là do số lượng hoán đổi cần thiết của hai thuật toán (loại bong bóng cần nhiều hoán đổi hơn). Nhưng do sự đơn giản của sắp xếp bong bóng, kích thước mã của nó rất nhỏ. Tính ổn định là một điểm khác biệt trong hai thuật toán này. Thuật toán sắp xếp ổn định, là một thuật toán sắp xếp giữ lại thứ tự các bản ghi nếu danh sách chứa các phần tử có giá trị bằng nhau. Theo nghĩa đó, sắp xếp lựa chọn không phải là một thuật toán ổn định trong khi sắp xếp bong bóng là một thuật toán ổn định.
