Stability

Bu derste, kabarcık sıralama (bubble sort) algoritmasının kararlı yapısını kontrol edeceğiz.

Kararlılık nedir?

Bir sıralama algoritması, eşit anahtarlara sahip iki nesne, sıralanacak girdi dizisinde göründükleri sırayla sıralanmış çıktıda da görünüyorlarsa kararlı olarak adlandırılır.

Örneğin, [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] dizisini sıralamamız gerekirse, burada 8₁ ve 8₂ ile gösterilen iki adet 8 vardır. Sıralamadan sonra iki olası dizi elde edilebilir: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] ve [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]. Bu dizilerin her ikisi de sıralıdır, ancak ikincisinde iki 8'in sırası farklıdır, oysa ilk dizide girdi dizisiyle aynıdır.

Şimdi bunu kabarcık sıralama algoritması için kontrol edelim.

İlk Geçiş: [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>]

İkinci Geçiş: [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>]

Tüm geçişlerden sonra nihai çıktı şöyle olacaktır: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

8'lerin sırasının hem çıktı hem de girdi dizilerinde aynı olduğuna dikkat etmeye çalışın.

Bu nedenle, Kabarcık sıralama algoritması Kararlıdır!