Yazan : Şadi Evren ŞEKER
Bu yazının amacı, literatürde iplik sıralaması (strand sort) olarak geçen sıralama algoritmasını (sorting algorithm) açıklamaktır. Sıralama algoritması bağlı listeler (linked list) üzerinde etkili olan bir algoritmadır ve iki sıralı listenin birleştirilerek yine sıralı bir liste oluşturulabileceği mantığına dayanır.
Sıralama algoritmasına geçmeden önce iki adet sıralı bağlı listenin (sorted linked list) nasıl birleştirileceğini hatırlatmak istiyorum. Ardından sıralama algoritmasını daha rahat anlayabiliriz.
Yukarıdaki şekilde gösterildiği üzere iki bağlı liste (L1 ve L2) verilmiş olsun. Yapılacak işlem gayet basit. Ya 3. bir listede ya da listelerden birisinde birleştirme işlemi yapmak. Biz listelerden birinde birleştirelim. Basitçe yapılacak işlem şu şekildedir:
if L1->data < L2->data ise L2’de birleştir
else L1’de birleştir.
Birleştirme için yapılacak işlem basit. Küçük olan listenin ilk elemanı saklanacak. Diğer listenin elemanı sırası gelen yere yerleştirilecek.
Yani yukarıdaki örnekte, L2’nin ilk elemanı daha büyük olduğu için L1’in ilk elamanı L2’nin ilk kendisinden büyük elemandan önceki konuma yerleştirilecek.
Ekleme işleminin neticesi yukarıda gösterildiği gibidir. Ardından işleme devam edilir. 7 yine 13’ten küçük olduğu için araya eklenecektir.
İşleme devam edilir ve sıradaki 11 sayısı yine araya eklenir.
Sıradaki sayı olan 22, 13’ten büyük olduğu için L2 göstericisi ilerletilir.
Sıradaki 22 sayısı 27’den küçük olduğu için araya yerleştirilecektir:
Netice olarak görüleceği üzere iki liste birleştirilerek tek bir liste haline gelmiş ve liste sıralı sayılardan oluşmuştur.
Şimdi gelelim sıralama algoritmasına. Algoritma verilen bir bağlı liste üzerinde sıralama yapmayı hedefler. Bir örnek üzerinden çalışmasını açıklayalım.
Yukarıda verilen bağlı listeyi sıralamak iplik sıralaması (strand sort) ile sıralamak isteyelim.
İlk aşamada birinci elemanı alıyor ve kendisinden büyük sayıları bir listeye atarak işe başlıyoruz.
Ardından aynı işlemi tekrar yaparak 3. bir liste oluşturuyoruz.
İplik sıralaması her zaman için 3 liste ile çalışmaktadır. Verinin tutulduğu Orijinal liste, iki adet de geçici liste olarak çalışır. Geçici listeler bir listede birleştirilip ardından yeniden bir liste oluşturulur.
Şimdiki adımımız yeni oluşturulan iki geçici listeyi birleştirmek.
Yukarıdaki son halinin üzerine Orijinal listeye geri dönüp ikl elemanından itibaren artan bir şekilde yeni liste çıkarıyoruz. Ancak tabi ilk eleman tek eleman olduğu için aslında yapılan işlem Orijinal liste ile yeni oluşturduğumuz geçici listenin birleştirilmesidir.
Sonuç olarak verilen liste sıralanmış olur.
Yukarıda örnekler üzerinden anlattığımız sıralama algoritmasını koda dökelim. Bunun için JAVA dilinde kod yazmaya iki listeyi birleştiren koddan başlayalım. Aşağıdaki şekilde özyineli (recursive) bir kod yazılabilir:
Dugum siraliBirlestir(Dugum list1, Dugum list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.veri < list2.veri) {
list1.sonraki = siraliBirlestir(list1.sonraki, list2);
return list1;
} else {
list2.sonraki = siraliBirlestir(list2.sonraki, list1);
return list2;
}
}
Ardından bu sırasız verilen listenin üzerinde çalışan ve Orijinal listeden iki adet geçici listeyi oluşturan kodu yazmaya çalışalım.
public Dugum iplikSirala(Dugum A){
System.out.println(" A giris " + A);
Dugum dolas = new Dugum();
dolas.sonraki = A;
Dugum B=null;
Dugum C=null;
Dugum Bbas;
while (A!=null){
B=A;
Bbas = B;
A= A.sonraki;
if(A==null)
break;
// Liste başından siliyoruz
System.out.println(" bveri "+ B.veri + " Averi "+ A.veri);
while(B.veri < A.veri){
B.sonraki = A;
A= A.sonraki;
B= B.sonraki;
B.sonraki = null;
if(A==null)
break;
}
System.out.println( " A liste basi "+ A);
System.out.println( " B liste basi "+ Bbas);
// Liste ortası ve sonu
dolas = new Dugum();
dolas = A;
while(dolas != null && dolas.sonraki != null && dolas.sonraki.veri > B.veri){
B.sonraki = dolas.sonraki;
dolas.sonraki = dolas.sonraki.sonraki;
B = B.sonraki;
B.sonraki = null;
}
System.out.println(" Birlesme oncesi A " + A + " B " + Bbas + " C " + C);
C= siraliBirlestir(Bbas,C);
Bbas = null;
B= null;
System.out.println(" A " + A + " B " + Bbas + " C " + C);
}
return C;
}
Yukarıdaki kodda, çok sayıda debug satırı bıraktım. Kod çalıştırılarak sıralama işleminin nasıl yapıldığı adım adım izlenebilir. Basitçe yukarıdaki yazıda anlattığım üzere, A listesi, sıralanacak olan elemanları, B listesi geçici listeyi, C listesi ise B ile birleştirilerek tutulan ikinci geçici listeyi tutmaktadır.
Sırasıyla A listesinden artan bir liste alınıp B listesine konuluyor. Ardından B listesi ile C listesi, C listesi üzerinde birleştirilerek sıralanmış oluyor.
Son olarak kullandığım bağlı listesi yapısındaki node (düğüm) kodunu ve test amaçlı main kodunu da içeren bütün kodu aşağıda yayınlıyorum. Kodlarken kendim sıfırdan bir bağlı liste yapısı (Gerekli olduğu kadarıyla) yazdım. Benzer bir kodlama için Java dilindeki hazır yapılar da kullanılabilir.
class Dugum{
Dugum sonraki;
int veri;
public Dugum(){
veri = 0;
sonraki=null;
}
public Dugum(int x){
veri = x;
}
Dugum diziEkle(int a[]){
Dugum bas = new Dugum(a[0]);
Dugum iter = bas;
for(int i = 1;i B.veri){
B.sonraki = dolas.sonraki;
dolas.sonraki = dolas.sonraki.sonraki;
B = B.sonraki;
B.sonraki = null;
}
System.out.println(" Birlesme oncesi A " + A + " B " + Bbas + " C " + C);
C= siraliBirlestir(Bbas,C);
Bbas = null;
B= null;
System.out.println(" A " + A + " B " + Bbas + " C " + C);
}
return C;
}
Dugum siraliBirlestir(Dugum list1, Dugum list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.veri < list2.veri) {
list1.sonraki = siraliBirlestir(list1.sonraki, list2);
return list1;
} else {
list2.sonraki = siraliBirlestir(list2.sonraki, list1);
return list2;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Dugum d = new Dugum();
int a[] = {2,3,9,15,22};
int b[] = {1,4,16,18,28};
d= d.diziEkle(a);
Dugum e = new Dugum();
e= e.diziEkle(b);
System.out.println(d);
Strand st = new Strand();
d = st.siraliBirlestir(d,e);
System.out.println(d);
int dizi[] = {2,4,19,3,4,8,0,11,16,43,1};
Dugum sirala = new Dugum();
sirala = sirala.diziEkle(dizi);
System.out.println(sirala);
sirala = st.iplikSirala(sirala);
System.out.println(sirala);
}
}
Yukarıdaki kodun, ekran çıktısı aşağıdaki şekildedir:
2 3 9 15 22 1 2 3 4 9 15 16 18 22 28 2 4 19 3 4 8 0 11 16 43 1 A giris 2 4 19 3 4 8 0 11 16 43 1 bveri 2 Averi 4 A liste basi 3 4 8 0 11 16 43 1 B liste basi 2 4 19 Birlesme oncesi A 3 4 8 0 11 16 43 1 B 2 4 19 C null A 3 4 8 0 11 16 43 1 B null C 2 4 19 bveri 3 Averi 4 A liste basi 0 11 16 43 1 B liste basi 3 4 8 Birlesme oncesi A 0 1 B 3 4 8 11 16 43 C 2 4 19 A 0 1 B null C 2 3 4 4 8 11 16 19 43 bveri 0 Averi 1 A liste basi null B liste basi 0 1 Birlesme oncesi A null B 0 1 C 2 3 4 4 8 11 16 19 43 A null B null C 0 1 2 3 4 4 8 11 16 19 43 0 1 2 3 4 4 8 11 16 19 43 BUILD SUCCESSFUL (total time: 0 seconds)