Zaman Karmaşıklığı
(Time Complexity)
Aynı Yerde Sıralama Yapabilmesi

(in-place)

En İyi Durum (Best-Case) Ortalama Durum (Average-Case) En Kötü Durum (Worst-Case)
O(n) O(n3/2) O(n3/2) Evet

Kabuk Sıralaması (ing. Shell Sort) algoritması ismini yöntemin mucidi olan Donald Shell’den alıyor. (İngilizce’de kişinin soyadı “kabuk” anlamına geldiğinden algoritmanın ismi Türkçe’ye böyle geçmiş ama aslında yöntemin kabukla bir alakası yok 🙂 )

Kabuk Sıralaması aslında temel olarak Araya Sokma Sıralamasının (ing. Insertion Sort) bir varyasyonu. Eğer Araya Sokma Sıralamasına tam olarak hakim değilseniz bu yazıyı okumadan önce ilgili bağlantıdan yöntemi incelemenizi tavsiye ederim. Araya Sokma Sıralamasında bir eleman sadece yanındaki elemanlar ile sırasıyla karşılaştırılır ve bu elemanın dizinin kendisinin şu anki pozisyonuna uzak olan yerlerine gidebilmesi için bir çok karşılaştırma yapılması gerekmektedir. İşte Kabuk Sıralaması uzaktaki elemanların birbiri ile önceden karşılaştırılabilmesine ve yer değiştirebilmelerine izin vererek verim sağlamaya çalışır. Araya Sokma Sıralaması gibi fazladan yer ihtiyacı yoktur, sıralamayı aynı dizi üzerinde yapabilir.

Kabuk Sıralaması algoritmasının zaman karmaşıklığı analizi çok basit değildir çünkü seçilen aralık atlama ve azaltma sayılarının (kaynaklarda “increment sequence” olarak geçiyor) algoritmanın çalışması üzerinde büyük etkisi vardır. Algoritma en iyi durumda doğru atlama ve azaltma sayıları seçilerek Araya Sokma Sıralaması gibi O(n) zamanda çalışabilir. Ancak önemli olan nokta ise algoritmanın en kötü durumda bile, doğru atlama ve azaltma sayıları ile O(n3/2) zamanında çalışabileceğinin gösterilmiş olmasıdır. Fakat bizim aşağıda anlatacağımız yöntem basitlik açısından O(n2)’de çalışan bir yöntemdir.

Bizim kullanacağımız yöntemde ilk boşluk (ing. gap) dizinin yarısı kadar olacak. Daha sonra boşluklar hep yarıya inecek ve en son 1 olduğunda zaten normal Araya Sokma Sıralaması yapılacak. Yani örneğin 10 elemanlı bir dizi için bizim yöntemimiz için “increment sequence” {1,2,5} olmuş olacak. (Önce 10/2’den 5, daha sonra 5/2’den tam sayı bölmesi ile 2 ve son olarakta 1)

Örneğimiz üzerinden gidecek olursak :

9 2 5 10 1 4 6 3 8 7

Dizimiz 10 elemanlı olduğu için ilk boşluk sayımız 5. Bu durumda 9 4 ile, 2 6 ile, vs. olmak üzere (5’er atladığımıza dikkat edin) Araya Sokma Sıralaması uygulanacak. Bu durumda dizimizin yeni hali :

4 2 3 8 1 9 6 5 10 7

olur. Şimdi ise boşluğu 2’ye düşürüyoruz. Bu durumda 4 3 1 6 10 ve 2 8 9 5 7 kendi aralarında olmak üzere (2’şer atladığımıza dikkat edin) Araya Sokma Sıralaması uygulanır. (Burada ara işlemleri atlıyoruz ancak algoritma Araya Sokma Sıralamasının gerektirdiği tüm işlemleri yapmak zorunda). Dizimizin bu işlemlerden sonraki hali :

1 2 3 5 4 7 6 8 10 9

şeklinde olur. Son olarak boşluk 1’e düşürülür ve bu durumda klasik Araya Sokma Sıralaması uygulanarak dizi tamamen sıralanmış olur.

Dizinin boşluk 1’e indirilmeden önceki halinin, ilk halinden daha düzenli bir yapıda olduğunu dolayısıyla Araya Sokma Sıralaması uygulandığında daha az karşılaştırma yaparak işin biteceğini farketmişsinizdir. Yani önceki işlemler bir ön işleme gibi çalışıp diziyi kabaca düzenleyip son kısma hazırlamış oldu.

Örneğin aşağıdaki tam olarak tersten sıralı diziyi ele alırsak :

5 4 3 2 1

Normalde Araya Sokma Sıralaması bu dizi için oldukça fazla karşılaştırma yapacaktır. (her ele alınan eleman dizinin en başına kadar yol alacak) Ancak bu dizi üzerinde anlattığımız Kabuk Sıralama algoritmasını çalıştırırsak :

5 eleman olduğu için ilk boşluğu 2 alıyoruz, yani ilk önce 5 3 1 kendi arasında 4 2 kendi arasında sıralanacak. Dizinin yeni hali :

1 2 3 4 5 olur. Süper 🙂 Çünkü dizi daha boşluğu 1 yapmadan tam olarak sıralanmış oldu. Klasik Araya Sokma Algoritması sıralı dizide oldukça hızlı çalışıp bitecektir.

Algortimanın Java dilinde yazılmış örnek kodu aşağıdan incelenebilir :

public static void shellSort(int[] a)
{
   int insert;
   int moveItem;
	
   for(int gap=a.length/2; gap>0; gap/=2)
   {
	for(int next=gap; next<a.length; next++) 
        { 
           insert = a[next]; 
           moveItem = next; 
 
           while(moveItem >= gap && insert < a[moveItem-gap])
	   {
		a[moveItem] = a[moveItem-gap];
		moveItem -= gap;
	   }
			
	   a[moveItem] = insert;
	}
   }
}

Kodun çalışma mantığının Araya Sokma Sıralamasını anlatırken verdiğimiz kod ile aynı olduğuna, sadece boşlukları doğru yerde ayarlamamız gerektiğine dikkat edin.

5 thoughts on “Kabuk Sıralaması (Shell Sort)

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak.