Eklemeli Sıralama - Insertion Sort

Eklemeli sıralama algoritması diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır.
Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez.

Algoritmanın çalışma mantığı şu şekildedir.
Geçici olarak atanan dizi elemanının yerini bulunup oraya koyulması üzerine çalışır.Yeri bulmak için
dizi içerisinde geçici elemanın bulunduğu yerden başa doğru kaydırma işlemi yapılmaktadır.

Algoritmanın karmaşıklığı
En kötü başarım: Eklemeli sıralama algoritması en kötü durumda, örneğin liste tersten sıralıysa O(n^2) karmaşıklıkla çalışır.
En iyi başarım: Eklemeli sıralama algoritması en iyi durumda, örneğin liste sıralıysa sadece  n-1 karşılaştırma yapar ve
 O(n) karmaşıklıkla çalışır.
Ortalama başarım: Eklemeli sıralama algoritması ortalama O(n^2) karmaşıklıkla çalışır.

Örnek
1.(5 1 4 2 8 ) \to ( 1 5 4 2 8 )
gecici = 1 olur j=0 olur 1-5 karşılaştırılıp 5 bir sağ kaydırılıp 1 j'ye koyulur
2.(1 5 4 2 8 ) \to ( 1 4 5 2 8 )
gecici = 4 olur j=1 olur 4-5 karşılaştırılıp 5 bir sağ kaydırılıp 4 j'ye koyulur
3.(1 4 5 2 8 ) \to ( 1 2 4 5 8 )
gecici = 2 olur 2-5 sonra 2-4 karşılaştırılıp 4 ve 5 bir sağ kaydırılır
her kaydırma için j bir azaltılır ve 2 j'ye koyulur
4.( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
sıralı olduğundan değişim yapılmaz

Eklemeli sıralama algoritması java kodları

public static void eklemeliSiralama(int[] dizi) {
  int gecici = 0, j = 0;
  
  for (int i = 1; i < dizi.length; i++) {
   gecici = dizi[i]; // i. eleman gecici yapıyoruz   
   j = i - 1; //i nin bir eksiğini j ye atıyoruz
   
   // j sıfırdan büyükse ve
   //  geçici, dizinin j. elamanından küçük olana kadar kaydırma yap
   while (j >= 0 && gecici < dizi[j]) {
    dizi[j + 1] = dizi[j];
    j = j - 1;
    dizi[j + 1] = gecici;
   }

  }
 }

Kodlara ulaşmak için github adresine gidin