Một sự khác biệt đáng kể khác giữa hai loại đó là sắp xếp bong bóng là thuật toán ổn định trong khi sắp xếp lựa chọn là thuật toán không ổn định. Một thuật toán được coi là ổn định các phần tử có cùng khóa xảy ra theo cùng thứ tự như chúng đã xảy ra trước khi sắp xếp trong danh sách hoặc mảng. Nói chung, hầu hết các thuật toán ổn định và nhanh chóng sử dụng bộ nhớ bổ sung.
Biểu đồ so sánh
| Cơ sở để so sánh | Sắp xếp bong bóng | Lựa chọn sắp xếp |
|---|---|---|
| Căn bản | Phần tử liền kề được so sánh và hoán đổi | Phần tử lớn nhất được chọn và hoán đổi với phần tử cuối cùng (trong trường hợp thứ tự tăng dần). |
| Độ phức tạp trường hợp tốt nhất | Trên) | O (n 2 ) |
| Hiệu quả | Không hiệu quả | Cải thiện hiệu quả so với sắp xếp bong bóng |
| Ổn định | Vâng | Không |
| phương pháp | Trao đổi | Lựa chọn |
| Tốc độ | Chậm | Nhanh so với sắp xếp bong bóng |
Định nghĩa sắp xếp bong bóng
Sắp xếp bong bóng là thuật toán lặp đơn giản nhất hoạt động bằng cách so sánh từng mục hoặc phần tử với mục bên cạnh và hoán đổi chúng nếu cần. Nói một cách đơn giản, nó so sánh thành phần thứ nhất và thứ hai của danh sách và hoán đổi nó trừ khi chúng không theo thứ tự cụ thể. Tương tự, phần tử thứ hai và thứ ba được so sánh và hoán đổi, và phần so sánh và hoán đổi này đi đến cuối danh sách. Số lượng so sánh trong lần lặp đầu tiên là n-1 trong đó n là các phần tử số trong một mảng. Phần tử lớn nhất sẽ ở vị trí thứ n sau lần lặp đầu tiên. Và sau mỗi lần lặp lại, số lần so sánh giảm dần và ở lần lặp cuối cùng chỉ có một phép so sánh diễn ra.
Thuật toán này là thuật toán sắp xếp chậm nhất. Độ phức tạp trường hợp tốt nhất (Khi danh sách theo thứ tự) của sắp xếp Bong bóng có thứ tự n ( O (n) ) và độ phức tạp trường hợp xấu nhất là O (n2) . Trong trường hợp tốt nhất, nó là thứ tự n vì nó chỉ so sánh các phần tử và không trao đổi chúng. Kỹ thuật này cũng đòi hỏi không gian bổ sung để lưu trữ biến tạm thời.
Định nghĩa sắp xếp lựa chọn
Lựa chọn sắp xếp đã đạt được hiệu suất tốt hơn một chút và hiệu quả hơn thuật toán sắp xếp bong bóng. Giả sử chúng ta muốn sắp xếp một mảng theo thứ tự tăng dần sau đó nó hoạt động bằng cách tìm phần tử lớn nhất và trao đổi nó với phần tử cuối cùng và lặp lại quy trình sau trên các mảng con cho đến khi toàn bộ danh sách được sắp xếp.
Sự khác biệt chính giữa Sắp xếp bong bóng và Sắp xếp lựa chọn
- Trong sắp xếp bong bóng, mỗi phần tử và phần tử lân cận của nó được so sánh và hoán đổi nếu được yêu cầu. Mặt khác, sắp xếp lựa chọn hoạt động bằng cách chọn phần tử và hoán đổi phần tử cụ thể đó với phần tử cuối cùng. Phần tử được chọn có thể lớn nhất hoặc nhỏ nhất tùy theo thứ tự, tức là tăng dần hoặc giảm dần.
- Độ phức tạp trường hợp xấu nhất là giống nhau trong cả hai thuật toán, tức là O (n2), nhưng độ phức tạp tốt nhất là khác nhau. Sắp xếp bong bóng có thứ tự n thời gian trong khi sắp xếp lựa chọn tiêu tốn một thứ tự thời gian n2.
- Sắp xếp bong bóng là một thuật toán ổn định, ngược lại, sắp xếp lựa chọn là không ổn định.
- Thuật toán sắp xếp lựa chọn là nhanh và hiệu quả so với sắp xếp bong bóng rất chậm và không hiệu quả.
Phần kết luận
Thuật toán sắp xếp bong bóng được coi là thuật toán đơn giản và kém hiệu quả nhất, nhưng thuật toán sắp xếp lựa chọn có hiệu quả so với sắp xếp bong bóng. Sắp xếp bong bóng cũng tiêu tốn không gian bổ sung để lưu trữ biến tạm thời và cần nhiều giao dịch hoán đổi.
