Insertion sort bir dizide yer alan elemanları, sıralamak için kullanılabilecek öğrenimi kolay bir algoritmadır. Algoritmanın temel prensibi sırasıyla dizideki bütün elemanları, o elamandan önceki elemanlarla karşılaştırarak yer değiştirmesidir.
Sort algoritması, çalışmak için ekstra alana ihtiyaç duymaz, aynı dizi üzerinden işlem yaparak memory(hafıza) alanından tasarruf sağlamaktadır.
public static void insertionSort(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
public static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6};
insertionSort(arr);
printArray(arr);
}
Kod içerisinde örnekte verildiği gibi 12, 11, 13, 5, 6 sıralayacak olalım.
i = 1 için key değerimiz ikinci eleman olan 11 olacaktır. Bu key değerinden önce gelen bütün değerleri kontrol ediceğiz eğer key değerimizden daha büyük bir sayı ise bunu bir sonraki indise “arr[j+1] = arr[j]” kodu ile koyacağız. Bu işlem 0 indisindeki ile karşılaştırma yapana kadar sürücektir en son olarak, en son taşıma yaptığımız indise key değerimizi koyacağız.