Shell Sort Algoritmasının ilk sürümü Donald Shell tarafından 1959 yılında yayınlandı. Shell Sort Algorithm, Türkçeleştirildiğinde ortaya ‘Kabuk Sıralaması Algoritması’ anlamı çıkıyor. Ancak bu isme çeviri yapmak ne kadar doğru bilinmez. Çünkü algoritmanın adı, geliştiricisinin soy isminden gelmektedir.

Insertion Sort ve Bubble Sort algoritmalarında eleman kümesi (array/dizi) içerisinde birbirine komşu olan elemanların karşılaştırılarak yerlerinin değiştirildiğini görmüştük. Bu iki algoritmanın aksine Shell Sort algoritmasında bu durum biraz farklı. Shell sort algoritmasında, birbirine komşu olmayan uzak elemanlar karşılaştırılmakta ve değiştirme işlemi gerçekleştirilmektedir.

En kötü durum performansı (worst-case performance) O(n²) olarak kabul edilmektedir. Ancak zaman karmaşıklığını belirlemek tam bir sorun oluşturmaktadır. O yüzden zaman karmaşıklığı eleman kümesine bağlıdır diyebiliriz.

Shell sort algoritmasını gösteren görsel animasyonu incelediğimizde elemanların küme içerisinde nasıl yerleştirildiklerini daha rahat görebiliriz.

Karmaşıklığının belirlenmesinde sıkıntılar olduğunu söylemiştik. Karmaşıklık yapısı için yukarıda verdiğim tabloyu inceleyebilirsiniz. Fazla kafa karışıklığı sebebiyet vermeden örnek uygulamamıza geçelim.

C# Console Uygulaması

int[] dizi = new int[] { 5, 1, 2, 7, 3, 4, 9, 6, 8 };
for (int atlama = dizi.Length / 2; atlama > 0; atlama = (atlama == 2 ? 1 : (int)Math.Round(atlama / 2.2)))
{
   for (int i = atlama; i < dizi.Length; i++)
   {
       int gecici = dizi[i];
       for (int j = i; j >= atlama && dizi[j - atlama] > gecici; j -= atlama)
       {
           dizi[j] = dizi[j - atlama];
           dizi[j - atlama] = gecici;
       }
   }
}

Genel olarak yapmak istediğimiz olaydan bahsedeyim. Öncelikle atlama noktası belirlememiz gerekiyordu. Biz bunun için dizi boyutunun yarısını tercih ettik. Bu atlama noktası ile atlama noktasına kadar olan elemanları karşılaştırdık ve değiştirme işlemlerini gerçekleştirdik.

Sıralama algoritmalarından Shell Sort Algoritmasını kavramaya çalıştık. Faydalı bir yazı olması dileğiyle. Sonraki yazı dizimizde görüşmek dileğiyle.

Barış Arıburnu

Yazılım Mühendisi

barisariburnu@gmail.com

www.barisariburnu.com