Yazan : Şadi Evren ŞEKER
Bu yazının amacı, tarak sıralaması (comb sort) olarak bilinen algoritmayı açıklamaktır. Algoritma, çıkışı itibariyle kabarcık sıralaması (bubble sort) ve hızlı sıralama (quick sort) karışımı olarak düşünülebilir.
Tarak sıralaması aslında anlaşılması oldukça kolay bir algoritmadır. Ancak anlamak için kabarcık sıralamasının (bubble sort) anlaşılması gerekir. Şayet bu algoritmayı bilmiyorsanız, önce bu algoritmayı okumanızı tavsiye ederim.
Kabarcık sıralamasında, sayılar sürekli olarak bir yanındaki sayı ile karşılaştırılır ve istenen sıraya göre yer değiştirme işlemi (swapping) yapılır. Tarak sıralamasında da benzer bir yaklaşım vardır ancak karşılaştırma ve yer değiştirme işlemleri hemen yan yana olan sayılar arasında değil de daha uzaktaki sayılar arasında yapılır. Yani kabarcık sıralaması bu anlamda aslında tarak sıralamasının özel bir örneği (mesafenin 1 olduğu ) olarak düşünülebilir. Tarak sıralamasında mesafe herhangi bir sayı olabilir.
Örnek olarak aşağıdaki şekilde verilmiş bir sayı dizisini ele alalım:
2,6,8,1,3,7,4,9,0,5
Yukarıdaki dizide 10 eleman bulunmakta ve ilk başta arama boşluğumuz (gap) 10/1,24 = 8,06 yani 8 olacak.
2 6 8 1 3 7 4 9 0 5
Bu durumda 0. elemandan başlayan algoritmamız, 0. eleman ile boşluk miktarı ilerisindeki elemanı karşılaştıracak ve 8. eleman ilk elemandan küçük olduğu için (9. sırada 0 var) yer değiştirme (swapping) işlemi yapılacaktır.
0 <-> 8
0 6 8 1 3 7 4 9 2 5
Ardından sıradaki elemana bakıyoruz yani 1 ile 8 fazlası olan 9 karşılaştırılıyor ve yine 9. sıradaki sayı, 1. sıradaki sayıdan küçük olduğu için, yer değiştirme (swapping) işlemi yapılıyor.
1 <-> 9
0 5 8 1 3 7 4 9 2 6
Ardından dizinin sonuna ulaşıldığı için bu defa yeni boşluk (gap) hesaplanıyor : 8/1,24 = 6 olarak bulunuyor.
A[0] = 0 ve A[6] = 7 olduğu için değişme olmuyor,
A[1] = 5 ve A[7] = 9 olduğu için yine değişme olmuyor,
A[2] = 8 ve A[8] = 2 olduğu için küçük olanı öne alıyoruz ve değiştirme işlemi yapılıyor:
2 <-> 8
0 5 2 1 3 7 4 9 8 6
Dizinin sonuna kadar olan sayılarda bir değişme olmuyor ve yeni boşluk değeri hesaplanıyor, 6/1,24 = 4 olur:
A[0] = 0 ve A[4] = 3 değişme olmaz,
A[1] = 5 ve A[5] = 7 değişme olmaz
A[2] = 2 ve A[6] = 4 değişme olmaz
A[3] = 1 ve A[7] = 9 değişme olmaz
A[4] = 3 ve A[8] = 8 değişme olmaz
A[5] = 7 ve A[9] = 6 olduğu için yer değiştirirlirler:
5 <-> 9
0 5 2 1 3 6 4 9 8 7
Dizinin sonuna ulaştığımız için yeni atlama değeri (gap) hesaplanır: 4/1,24 = 3
A[0] = 0 , A[3] = 1 değişme olmaz,
A[1] = 5 , A[4] = 3 olduğu için yer değiştirirler:
1 <-> 4
0 3 2 1 5 6 4 9 8 7
A[2] = 2 ve A[5] = 6 değişme olmaz
A[3] = 1 ve A[6] = 4 değişme olmaz
A[4] = 5 ve A[7] = 9 değişme olmaz
A[5] = 6 ve A[8] = 8 değişme olmaz
A[6] = 4 ve A[9] = 7 değişme olmaz
Dizinin sonunda yeni boşluk değeri hesaplanır (gap) : 3/1,24 = 2
A[0] = 0 ve A[2] = 2 değişme olmaz
A[1] = 3 ve A[3] = 1 yer değiştirilir:
1<->3
0 1 2 3 5 6 4 9 8 7
A[2] = 2 ve A[4] = 5 değişme olmaz
A[3] = 1 ve A[5] = 6 değişme olmaz
A[4] = 5 ve A[6] = 4 yer değiştirilir
4 <-> 6
0 1 2 3 4 6 5 9 8 7
A[5] = 6 ve A[7] = 9 değişme olmaz
A[6] = 5 ve A[8] = 8 değişme olmaz
A[7] = 9 ve A[9] = 7 yer değiştirilir:
7 <-> 9
0 1 2 3 4 6 5 7 8 9
Yeni boşluk değeri 2/1,24 = 1 olarak bulunur:
Bu durumda yan yana duran sayılardan sadece 5. ve 6. elemanlar düzeltilerek sıralama tamamlanır:
5 <-> 6
0 1 2 3 4 5 6 7 8 9
Görüldüğü üzere sıralama işlemi sırasında en kötü durum olan 1 aralıklı, komşuların kontrol edildiği durum en son olarak işlenir. Yani sırasıyla aşağıdaki atlama miktarlarında kontrol edilmiştir:
8, 6 , 4 , 3 , 2 , 1
Yukarıdaki atlama miktarlarından sadece sonuncusu 1 kabarcık sıralaması, diğerleri ise hızlı sıralama (quick sort) gibi dizinin bir seçim değerine göre (pivot) ikiye bölündüğü durumu olarak algılanabilir.
Yukarıdaki işlemleri yapan kod aşağıdaki şekilde yazılabilir:
void tarak_siralamasi(int *a, int boyut) {
int atlama = boyut;
bool degisti = false;
while (( atlama > 1) || degisti) {
if ( atlama > 1) {
atlama = (int)((double) atlama / 1.247330950103979);
}
degisti = false;
for (int i = 0; atlama + i < boyut; i++) {
if (a[i] - a[i + gap] > 0) {
int gecici = a[i];
a[i] = a[i + atlama];
a[i + atlama] = gecici;
degisti = true;
}
}
}
}