Sokma Sıralaması (Ekleme Sıralaması, Insertion Sorting)

Yazan : Şadi Evren ŞEKER

Sokma sıralaması, programlaması oldukça basit ancak performansı bölme sıralaması (merge sort), hızlı sıralama(quick sort) gibi sıralamalara göre nispeten yavaş bir sıralama algoritmasıdır. Çalışmasını aşağıdaki örnek üzerinden anlatmaya çalışalım:

Sıralanacak olan sayılarımız :

33 44 21 83 56 73 22 olsun. Bu sayıları sıralamaya ilk sayıdan başlıyoruz (yani 33).

ilk geçişte (pass) sadece 33 sayısı sıralanmış oluyor (yani hiçbirşey yapmıyoruz):

33| 44 21 83 56 73 22 ( | işareti o anda kadar sıraladığımız sayıları gösteriyor. Bu işaretin “|” solundaki sayılar sıralanmış kabul ediyoruz. Ve her geçişte bir sağındaki sayıyı alıyoruz)

ikinci geçişte sıralayacağımız sayı 44. 33 ile 44′ü karşılaştırıyoruz 33 küçük dolayısıyla yer değiştirmiyorlar:

33 44 | 21 83 56 73 22

üçüncü geçişte sıradaki sayı 21. 21 ile 44 karşılaştırılıyor ve 21 küçük olduğu için 44 ile yer değiştiriyorlar :

33 21 44 | 83 56 73 22 (geçişimiz henüz bitmedi çünkü 21, 33′ten de küçük:)

21 33 44 | 83 56 73 22 (şimdi 3. geçişi tamamladık ve bir sonraki sayı 83′ü alabiliriz:)

dördüncü geçişte 83 var:

21 33 44 83 | 56 73 22 ( bu geçiş çabuk bitti çünkü 83, 44′ten büyük ve sadece bunu görmemiz durmamız için yeterli sonuçta 56′ya kadar sıralamış olduk)

Beşinci geçişte 56′yı sıralayacağız:

21 33 44 56 83 | 73 22 ( burada 56 ile 83 karşılaştırıldı ve 56 sayısı 83′ün soluna kaydırıldı. Bunun sebebi 56′nın 83′ten küçük olması. Bu geçişte burada bitti çünkü 56, 44′ten büyüktür)

Altıncı geçişte sıra 73′te

21 33 44 56 73 83 | 22 ( sıralamamız yine tek adımda bitiyor çünkü 73, 83′ten küçük ve 56′dan büyük)

Yedinci geçişte 22 sayısını yerleştireceğiz ve adım adım 22′den küçük olan bir sayı görene kadar 22′yi dizide kaydırıyoruz:

21 33 44 56 73 22 83 |

21 33 44 56 22 73 83 |

21 33 44 22 56 73 83 |

21 33 22 44 56 73 83 |

21 22 33 44 56 73 83 |

Sonuçta işaretimiz “|” dizinin sonuna ulaştı ve dizimiz sıralanmış oldu.

Görüldüğü gibi sıralama algoritmasının ismi her seferinde sıradaki sayıyı sıralanmış dizideki uygun yere sokmaktan geliyor.

Sokma sıralamasının (insert sort) performansı O(n²)’dir. Bunun sebebi dizideki eleman sayısı kadar geçiş gerekmesi ve her geçişte en kötü ihtimalle elemsan sayısı kadar kaydırma gerekmesidir. Yani insertion sort’un en kötü durumu tersten sıralı bir listedir. Yukarıdaki örneği düşünecek olursak:

83 73 56 44 33 22 21 sıralamasındaki bir dizi en uzun sürede sıralanan dizidir. Buna karşılık sıralı bir dizi verildiğinde diziye 2n sayıda erişim erişim yeterlidir.

« HTML (Hyper Text Markup Language) | LEX »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Sokma Sıralaması (Ekleme Sıralaması, Insertion Sorting)' isimli yazı 12 Dec 2008 tarihinde, saat: 14:26 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1579 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar