Shell Sort Algoritması (Kabuk Sıralaması)

Shell Sort algoritması (Kabuk Sıralaması) nedir? Ne için kullanılır?

Shell sıralaması, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir: Eklemeli sıralama, sıralanacak dizi zaten büyük oranda sıralıysa daha verimli çalışır. Algoritma performansı O(n2)’dir. 

Shell Sort algoritması adımları

Ö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. Çü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.

Kodlama

Python, Java ve C dillerinde ise şu şekilde yazabiliriz.

JAVA

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;
}
}
}

PYTHON

def shellSort(arr):
n = len(arr)
gap = n // 2

while gap > 0:

for i in range(gap, n):

temp = arr[i]
j = i

while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap

arr[j] = temp
gap //= 2

C

int shellSort(int arr[], int n)
{

for (int gap = n/2; gap > 0; gap /= 2)
{

for (int i = gap; i < n; i += 1)
{

int temp = arr[i];

int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];

arr[j] = temp;
}
}
return 0;
}