Bir başka farklı dil, bir başka farklı algoritma köşemizde bugün Java ve Insertion Sort algoritmasını birleştirmeye karar verdim. Dediğim gibi daha önce de başka dillerde başka sıralama algoritmaları uygulamıştım, sorting/sıralama algoritmaları dillere alışmak için güzel bir başlangıç olduğundan bu çeşitlendirmeleri arttırmaya çalışacağım. Java için özellikle Insertion Sort u seçmemin bir sebebi yok ama düşündüğümde ilk aklıma gelen de o oldu.
İlk önce Insertion Sort (Yerleştirmeli Sıralama) nın ne olduğunu anlatayım. Pivot kelimesi her ne kadar türkçede de yer alsa da, belirleyici aslında daha anlatıcı bir tabir sanırım, bu sıralama tipinde işlem sırasında nerede olduğumuzu unutmamak adına pivot kullanılıyor. Listeyi ikinci öğesinden itibaren dolaşmaya başlıyoruz, bu öğeyi bir önceki ile karşılaştırıyoruz, eğer ondan küçükse, bu listenin ikinci öğesini ilk sıraya alıyoruz. Sonra pivotun (belirleyici) bize hatırlattığı üzere 3. öğeye geliyoruz, bunu da ikinci öğe ile karşılaştırıyoruz, eğer büyükse sorun yok ama küçükse bunu da onun soluna alıyoruz. Bu öğeyi yeni konumuna almadan önce bir önceki öğe ile de karşılaştırıyoruz, ondan da küçükse onun soluna alıyoruz. Pivot bize 4. öğeye bakmamızı söylüyor. Bu sefer bu öğeyi yeni listenin 3. öğesi ile karşılaştırıyoruz, küçükse soluna alıyoruz, 2. öğe ile karşılaştırıyoruz küçükse yine sola alıyoruz, böylelikle solundaki öğeden büyük olana kadar her öğeyi sola atmış oluyoruz. Tüm liste üzerinde bu şekilde ilerlediğimiz zaman, gittikçe sıraya giriyormuş gibi gözüken yeni bir liste ortaya çıkıyor.
Java kullandığımız için, tüm işlemleri bir class (sınıf) içine alıyorum ve asıl çağırma işlemini ve işleme sokacağımız listeyi main fonksiyonu içerisine koyuyorum. Ardından insertionSort fonkisyonu dahilinde pivot yardımıyla ilerleyerek, tüm öğeleri önceki öğeler ile karşılaştırıp yeni liste oluşturuyorum, tabii ki bu ilerleme listenin boyutu kadar oluyor:
public class Insertion{
public static void main(String[] args){
int[] sirasizliste = {42,4,23,16,8,15};
insertionSort(sirasizliste);
}
public static void insertionSort(int liste[]){
int uzunluk = liste.length;
for (int k = 1; k < uzunluk; k++) {
int pivot = liste[k];
int i = k-1;
while ( (i > -1) && (liste [i] > pivot) ) {
liste[i+1] = liste[i];
i--;
}
liste[i+1] = pivot;
}
sayiListesiYazdir(liste);
}
private static void sayiListesiYazdir(int[] liste) {
for (int j = 0; j < liste.length; j++) {
if (j + 1 == liste.length){
System.out.print(liste[j] + ")");
}else if(j == 0){
System.out.print("(" + liste[j] + ",");
}else{
System.out.print(liste[j] + ",");
}
}
System.out.println("\n");
}
}
Java da liste içindeki öğeleri yazdırmanın en temiz yolu for döngüsü ile öğeleri tek tek göstermek olduğu için bu işi sayıListesiYazdir fonksiyonu dahilinde yapıyorum. Bu dışarıda yer alan yardımcı bir fonksiyon olduğu için bunu çağırma işlemini yani sayiListesiYazdir(liste); komutunu, insertionSort dahilinde yer alan for döngüsünün dışında değil de for döngüsünün içinde ve sonunda çağırırsanız, pivot listede ilerlerken her yapılan hareketin sonunda listenin nasıl değiştiğini görebilirsiniz. Yazdırma fonksiyonu dahilinde yaptığım if-else ler tamamen, çıkacak listenin güzel bir görünüme sahip olması için yapılmıştır.
Neden Insertion Sort kullanabilirsiniz sorusu, yine kesin cevabı olmayan bir soru bence. Gittikçe sıraya giriyormuş gibi stabil ilerleyen kararlı bir yapısı olması ve çok az bozuk listeler için fazla hızlı olması bir dayanak olabilir. Küçük listeler için de fazlasıyla hızlı olabiliyor ancak ters sıralı listeler için tahminimce ciddi yavaşlıklara sebep olur.