Kabuk Sıralama (Shell Sort)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan sıralama algoritmalarından birisi de kabuk sıralamadır (shell sort). İsmi Türkçeye kabuk sıralaması olarak çevrilsede aslında Donald Shell isimli algoritmayı ilk bulan kişinin isminden gelmektedir. Algoritma performansı O(n2)’dir. Çalışması aşağıdaki örnek üzerinde anlatılmıştır:

Sıralayacağımız sayılar:

5,7,2,9,6,1,3

olarak verilmiş olsun. Sıralama işlemi için öncelikle bir atlama miktarı belirlenir. Atlama miktarının belirlenmesi için çok çeşitli yollar bulunmasına karşılık en basit yöntem elimizdeki sayıların yarısından başlamaktır. Yani yukarıdaki örnekte elimizde 7 sayı olduğuna göre 3 atlama miktarı ile başlanabilir.

Sırasıyla her sayı kendinden 3 sonraki sayı ile karşılaştırılır ve bu sayılar kendi aralarında sıralanır. Bu sıralamayı daha rahat göstermek için aşağıdaki kolon gösterimi kullanılabilir:

5,7,2

9,6,1

Her kolon kendi içinde sıralanınca aşağıdaki sayılar elde edilir:

3,6,1

5,7,2

Yukarkıdaki örnekte de görüldüğü üzere sayıları sıralama işleminin 3te biri bitirilmiştir. Ardından atlama miktarı yarıya indirilir (bu örnek için 3/2 = 1 olur)

Bu durumda bütün sayılar tek bir doğrultuda sıralanır.

3,6,1,5,7,2,9

1,2,3,5,6,7,9

Yukarıdaki sıralamada örneğin kabarcık sıralaması (bubble sort) kullanılırsa dizinin orjinal haline göre (yani kabuk sıralamasının 3 atlamalı sıralama işlemi yapılmamış haline göre) çok daha başarılı olduğu görülür.

void shell_sort (int *p, int size)
{
int i, j, k, temp;
for (k = size; k > 1; ) {
k = (k < 5) ? 1 : ((k * 5 – 1) / 11);
for (i = k – 1; ++i < size; ) {
temp = p[i];
for (j = i; p[j - k] > temp; ) {
p[j] = p[j - k];
if ((j -= k) < k)
break;
}
p[j] = temp;
}
}
}

Yukarıdaki örnek kodda bir dizinin (p) içerisindeki sayıları kabuk sıralamasına göre sıralayan fonksiyon verilmiştir. Fonksiyon girilen sayıları 5/11 oranında küçülen atlama miktarları ile kabarcık sıralaması kullanarak sıralamaktadır. Okuyucu döngünün içerisinde yapılan ve temp değişkeni kullanılan işlemin bir yer değiştirme (swap) işlemi olduğuna dikkat edebilir.

« İşlem Çatallanması (Process Forking) | İmgecik Tekrarlama (Pixel Replication) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Kabuk Sıralama (Shell Sort)' isimli yazı 20 Dec 2008 tarihinde, saat: 02:12 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1865 defa okunmuştur.

Benzer yazıları C/C++, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar