Stabilitas

Dalam pelajaran ini, kita akan memeriksa kestabilan algoritma bubble sort.

Apa itu stabilitas?

Algoritma pengurutan disebut stabil jika dua object dengan kunci yang sama muncul dalam urutan yang sama pada output yang sudah diurutkan seperti urutannya dalam array input yang akan diurutkan.

Misalnya, jika kita harus mengurutkan array ini: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , di sini kita memiliki dua angka 8, yang ditandai dengan 8₁ dan 8₂. Setelah pengurutan, dua array yang mungkin dihasilkan adalah [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] dan [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . Kedua array ini sudah terurut, tetapi pada array kedua, urutan kedua angka 8 berbeda, sedangkan pada array pertama, urutannya sama seperti pada array input.

Sekarang, mari kita periksa hal ini pada algoritma bubble sort.

Lintasan pertama: [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>]

Lintasan kedua: [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>]

Setelah semua lintasan, output akhirnya adalah: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Coba perhatikan bahwa urutan angka 8 sama pada array output dan input.

Jadi, algoritma bubble sort bersifat stabil!