Tính ổn định

Trong bài học này, chúng ta sẽ kiểm tra tính ổn định của thuật toán sắp xếp nổi bọt.

Tính ổn định là gì?

Một thuật toán sắp xếp được gọi là ổn định nếu hai đối tượng có khóa bằng nhau xuất hiện theo cùng thứ tự trong đầu ra đã sắp xếp như trong mảng đầu vào cần sắp xếp.

Ví dụ, nếu cần sắp xếp mảng [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1], ở đây ta có hai số 8, được ký hiệu là 8₁ và 8₂. Sau khi sắp xếp, ta có thể thu được hai mảng sau: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] và [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]. Cả hai mảng đều đã được sắp xếp, nhưng ở mảng thứ hai, thứ tự của hai số 8 đã thay đổi, còn ở mảng thứ nhất, thứ tự vẫn giống như trong mảng đầu vào.

Giờ hãy kiểm tra điều này với thuật toán sắp xếp nổi bọt.

Lượt đầu tiên: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

Lượt thứ hai: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Sau tất cả các lượt, đầu ra cuối cùng sẽ là: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Hãy chú ý rằng thứ tự của hai số 8 giống nhau trong cả mảng đầu ra lẫn mảng đầu vào.

Vì vậy, thuật toán sắp xếp nổi bọt có tính ổn định!