Bu işlem yapılırken dizi üzerinde sık sık kaydırma yapılır ve doğru pozisyona ilgili sayı yerleştirilir. Bubble Sort ve Selection Sort’a nazaran biraz karışık görülebilir, ancak göreceksiniz ki oldukça basit bir sıralama mantığı bulunmaktadır.

Insertion Sort Pseudo (sözde Kod) Kod

1- bir sayıyı eline al solundaki sayılara bak

2- Soldaki sayı elindeki sayıdan büyükse bir sağa kaydır.

3- Kendisinden küçük sayı bulunca boş bulunan indise yerleştir.

4- Diğer sayıya geç.

Burada dikkat etmeniz gereken 1. adım, 1. indisten başlar (0. indis değil)

Karmaşıklık Hesabı

Gördüğünüz üzere her adımda yeni bir eleman sıralanmış kısıma dahil olmaktadır. Karmaşıklık hesabı yaparsak her adımda bütün elemanları gezdiği için en kötü ihtimalde O(N^2)‘dir. Bu algoritma için en iyi ihtimalle başlangıçta dizinin sıralı olmasıdır. Böylelikle hiç yer değiştirme yapmadan sıralama bitecektir.

En kötü durum ise tersten yani bu örnek için büyükten küçüğe sıralanmış bir diziyi girdi olarak vermektir. Her eleman için en başa kadar karşılaştırma yapacağı için yaklaşık N^2 işlem gerçekleşecektir.

C/C++

void insertionSort(int arr[], int n)
{
   int i, deger, j;
   for (i = 1; i < n; i++)
   {
       deger = arr[i];
       j = i-1;
 
       
       while (j >= 0 && arr[j] > deger)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = deger;
   }
}


Java

void sort(int arr[])
    {
        int n = arr.length;
        for (int i=1; i=0 && arr[j] > deger)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = deger;
        }
    }


Python
 

def insertionSort(arr):
 
    
    for i in range(1, len(arr)):
 
        deger = arr[i]
        
        j = i-1
        while j >=0 and deger< arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = deger