Eklemeli sıralama

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)

Eklemeli Sıralama (İngilizcesi: Insertion 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:

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

Sözde Kodu(Pseudo Code)

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ı

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.[2]

Kaynakça

  1. Robert Sedgewick, Algorithms, Addison-Wesley 1983 (chapter 8 p. 95)
  2. Robert Sedgewick, Kevin Wayne, Algorithms 4th Edition, Addison-Wesley 2011 (chapter 2 p. 250)

Dış bağlantılar

This article is issued from Vikipedi - version of the 10/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.