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(n2)’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.

Yorumlar

  1. gizem

    48,19,26,38,21,29 sıralamasını da yapabilirmisinz acaba? 48 38 e kdr geldiğinde sonda 48 den küçük 2 sayı kalıyor.önce 21 yerleşene kdr onu sonra da 29 u mu kaydırıcaz emin olamadım.yine de adım adım hepsini gösterirseniz sevinirim.teşekkür ederim.

  2. Şadi Evren ŞEKER Article Author

    çözüm aşağıdaki şekildedir:

    48 | 19,26,38,21,29
    48,19 | 26,38,21,29
    19,48 | 26,38,21,29
    19,48,26 | 38,21,29
    19,26,48 | 38,21,29
    19,26,48,38 | 21,29
    19,26,38,48 | 21,29
    19,26,38,48,21 | 29
    19,26,38,21,48 | 29
    19,26,21,38,48 | 29
    19,21,26,38,48 | 29
    19,21,26,38,48,29 |
    19,21,26,38,29,48
    19,21,26,29,38,48

    kısacası her adımda tek sayı sokabilirsiniz (insert) birden fazla sayıyı aynı anda kaydırmak gibi işlemler, bu sıralama algoritmasının hızlandırılması için kullanılan iyileştirmelerdir ve uygulanabilir ancak klasik halinde böyle bir uygulama yok, yukarıda anlatıldığı şekilde.

    başarılar

    1. Şadi Evren ŞEKER

      Gnome sort iyileştirme ile (optimization) insertion sort olarak çalışır ancak iyileştirme yapılmadan da çalışabileceği ve iyileştirilmemiş halinin sokma sıralamasından (insertion sort) daha kötü olduğu durumlardan bahsetmek mümkündür.
      Temel farkı gnome sort için sayının doğru yere yerleştirilmesinden sonra sıralama algoritmasının kaldığı yerden devam edip etmeyeceğidir. Yukarıdaki yazıda bu özellik kullanılmıştır ancak orijinal gnome sort bunu zorunlu kılmaz. Örneğin 3. aşamadaki 21 sayısı sıralamaya dahil edilirken en başa kadar taşınmaktadır. Ardından sıralama algoritması 4. sayı olan 83 ile sıralamaya devam ediyorsa bu durumda insertion sort olarak davranır. Bunun yerine orijinal gnome sort 21 sayısını başa taşıdıktan sonra sırasıyla 33 ve 44 sayılarına tekrar bakabilir, bu durumda insertion sorttan daha kötü çalışacaktır.

  3. Melike

    Merhaba benim de bir sorum olacakti.c++ dilinde bir program yazıyorum.programim şu şekilde: insertion sort algoritması kullanılarak bir listedeki öğrencilerin numaralarına göre siralanmasini istiyorum.listeye ekleme işlemleri ve kayıt tutulmasında sıkıntı yok fakat sıralamayı kod a dokme kısmında zorlandım yardımcı olabilir misiniz acaba?

  4. Melike

    Bu arada ek olarak belirtmem gereken şu var ki öğrenciler yığın yapısı ile tutulmakta. Yani insertion sıralama yığın üzerinden gerçekleşecek

  5. zeynep kemer

    selamlar Hocam,

    Videoda average case = (best case + worst case )/2 diyorsunuz ama algoritma kitaplarında (Levitin in ) bu asla doğru değil . Orada belli kabuller ve olasılıklar alınarak average case bulunuyor. Şimdi hangis doğru acaba . Teşekkürler

    1. Şadi Evren ŞEKER

      Tabi ki benim söylediğim, Levitin bu işi bilmez 🙂

      İşin şakası bir yana yanlış hatırlamıyorsam Levitin’in kitabında random dağılım için bir kabul yapılıyordu. Ayrıca notasyon olarak n^2/2 zaten sabit değerle çarpma /bölme işlemi olduğu için n^2’ye yakınsar ama bu yorumunuz üzerine internette biraz aradım ve birisi üşenmeyip zamanını ölçmüş:

       n min     ave     max ave/(min+max) ave/max
      
        2   1     1         1        0.5000
        3   2     2.667     3        0.5334
        4   3     4.917     6        0.5463
        5   4     7.717    10        0.5512
        6   5    11.050    15        0.5525
        7   6    14.907    21        0.5521
        8   7    19.282    28        0.5509
        9   8    24.171    36        0.5493
       10   9    29.571    45        0.5476
       11  10    35.480    55        0.5458
       12  11    41.897    66        0.5441
      13  12    48.820    78        0.5424        
       14  13    56.248    91        0.5408
      15  14    64.182   105        0.5393
      16  15    72.619   120        -       0.6052
       32  31   275.942   496        -       0.5563
       64  63  1034.772  1953        -       0.5294
      128 127  4186.567  8128        -       0.5151
      256 255 16569.876 32640        -       0.5077
      

      Görüldüğü üzere (max+min)/2 değerine yakın veriyor ortalama değer zamanını, yani bizim videoda söylediğimiz durum doğrudur.

      Başarılar

  6. GÖRKEM

    bana kullanıcıdan girilen 10 sayı ile insertion sortda sıralama yapılması gerek biraz yardımcı olusanız evinirim +C olarak tabikide 😀

    1. ÖMER

      aşağıda java kodlarıyla yazılmış 1 ile 100 arasında random sayılar üreten ve daha sonra bunları sıralayan program vardır işinize yarayacağını düşünüyorum.

      import java.util.Random;
      import java.util.Scanner;
      public class Test {

      public static void eklemeliSiralama(int arr[]) {
      for(int i=1;i0;j–){
      if(arr[j]<arr[j-1]){
      int gecici=arr[j];
      arr[j]=arr[j-1];
      arr[j-1]=gecici;

      }
      else
      break;

      }

      }
      }

      public static void main(String [] args){
      Scanner klavye = new Scanner(System.in);

      int []dizi =new int[10] ;
      for(int j=0;j<dizi.length;j++){
      Random random= new Random();

      dizi[j]=(int) (Math.random()*100);

      }
      System.out.print("Dizinin sıralanmamış hali: ");
      for(int a=0;a<dizi.length;a++){
      System.out.print(dizi[a]+" ");
      }

      eklemeliSiralama(dizi);
      System.out.print("\nDizinin sıralanmış hali: ");
      for(int i=0;i<dizi.length;i++){
      System.out.print(dizi[i]+" ");

      }

      }

      }

  7. GÖRKEM

    bana kullanıcıdan girilen 10 sayı ile insertion sortda sıralama yapılması gerek biraz yardımcı olusanız evinirim ++

    1. Ekrem

      Hocamız gayet güzel anlatmış, bir zahmet onu da siz yapın Görkem bey. Hazır kod size hiç bir şey kazandırmaz.

Ekrem için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir