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

3

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

3,6,1

5,7,2

9

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.