Eklemeli sıralama

Eklemeli Sıralama (İngilizceInsertion Sort), bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Ancak buna karşın bazı artıları da vardır:

  • Uygulaması kolaydır.
  • Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.
  • Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
  • Karmaşıklığı olan seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir.
  • Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)
  • Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez.
  • Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur. Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.
Eklemeli sıralama
Insertion sort animation.gif
Eklemeli sıralama algoritmasının rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek.
Sınıf Sıralama algoritması
Veri yapısı Dizi
Zaman karmaşıklığı O(n²)
En iyi Genellikle değil
Alan karmaşıklığı O(1)

İnsanlar herhangi bir şeyi (örneğin, iskambil kartları) sıralarken, çoğu durumda eklemeli sıralamaya benzer bir yöntem kullanırlar.[1]

Çalışma PrensibiDüzenle

Eklemeli Sıralama dizi içerisindeki bir girdinin ait olduğu yere oturtularak ilerlenmesi ve bu sayede her döngüde kontrol edilmesi gereken girdi sayısını azaltması prensibi ile çalışır. Bu durumu iskambil kağıtlarını elimizde dizmeye benzetebiliriz. İşaretlenen kağıt/girdi kendisinden önce ve kendisinden daha büyük bir sayı kalmayana kadar başa çekilir. Arkasında kalan bütün indisler ise birer adım geriye düşer böylece bu döngü içerisindeki her adım bize, işaretlenen tüm girdilerin kendi sıralarında, kendilerinden önce sadece bu girdiden küçük sayıların kaldığını garanti eder.

Aşama aşama bir örnekDüzenle

8 2 4 9 3 6 --- > Bu sırasız, ham dizimiz.

8* 2 4 9 3 6 --- > Dizinin ilk indisi olan 8 seçildi. Öncesinde başka bir değer olmadığı için bir sonraki aşamaya geçiliyor.

8 2* 4 9 3 6 --- > Dizinin ikinci indisi olan 2 seçildi ve dizinin daha önce şu an tuttuğumuz 2 sayısından daha büyük bir değer oldukça başa taşınacak ve 8 ile yer değişecektir.

2 8 4* 9 3 6 --- > Benzer işlemleri bütün indislere sırası ile uyguluyoruz.

2 4 8 9* 3 6

2 4 8 9 3* 6

2 3 4 8 9 6*

2 3 4 6 8 9 --- > Sıralanmış dizimiz[2].

Bu örnekte * ile işaretlenmiş sayılar elde tutulan ve gerisinde kalanlar ile kıyaslanan sayıyı ; _ ile işaretlenmiş indisler ise elde tutulan sayının çekilebildiği en geri indisi göstermektedir.

Sözde Kodu(Pseudo Code)Düzenle

insertionSort(array A)
    for i = 1 to length[A-1] do
        value = A[i]
        j = i-1
        while j >= 0 and A[j] > value
            A[j + 1] = A[j]
            j = j-1
        A[j+1] = value

Karmaşıklık HesabıDüzenle

Eklemeli sıralama algoritmasının zaman karmaşıklığı hesaplanırken, yapılan karşılaştırmalar ve yer değiştirmeler dikkate alınır. Eklemeli sıralama algoritması   elemanlı bir listede, ikinci eleman için en fazla 1 karşılaştırma ve 1 yer değiştirme yapar, üçüncü eleman için 2 karşılaştırma ve 2 yer değiştirme, dördüncü eleman için 3 karşılaştırma ve 3 yer değiştirme yapar. Bu şekilde son eleman için en fazla   karşılaştırma ve   yer değiştirme yapar. Listedeki bütün elemanlar için yapılan karşılaştırmaların ve yer değiştirmelerin toplamı

 
yapar. Hesaplamalar sonucunda elde edilen
 
değerinin asimptotik üst sınırı   değerini verir.

En kötü başarım: Eklemeli sıralama algoritması en kötü durumda, örneğin liste tersten sıralıysa   karmaşıklıkla çalışır.

En iyi başarım: Eklemeli sıralama algoritması en iyi durumda, örneğin liste sıralıysa sadece   karşılaştırma yapar ve   karmaşıklıkla çalışır.

Ortalama başarım: Eklemeli sıralama algoritması ortalama   karmaşıklıkla çalışır.[3]

NotlarDüzenle

  1. ^ Robert Sedgewick, Algorithms, Addison-Wesley 1983 (chapter 8 p. 95)
  2. ^ 6.006- Introduction to Algorithms (PDF), erişim tarihi: 17 Mart 2021 
  3. ^ Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 250)

KaynakçaDüzenle

  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.

Dış bağlantılarDüzenle