Kabuk sıralaması

Kabuk sıralaması
Kabuk sıralaması
	Kabuk sıralama algoritması
Sınıf	Sıralama algoritması
Veri yapısı	Dizi
Zaman karmaşıklığı	O(n log² n), aralıkların dizilimine göre değişir
En iyi	Genellikle değil
Alan karmaşıklığı	O(n) toplam, O(1) yardımcı

Shell sıralaması (İngilizce: Shell sort), 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.
Eklemeli sıralama, dizideki öğeleri her adımda yalnızca bir sonraki konuma aktardığından verimsizdir.

Algoritmanın Geçmişi

Shell sıralaması algoritmasının adı algoritmayı bulan kişi olan Donald Shell'den gelmektedir. Donald Shell algoritmayı 1959 yılında yayınlamıştır.

Uygulamalar

C/C++ dilinde yazılmış Shell sıralaması

Aşağıda C/C++ dilinde yazılmış, bir sayı dizisini Shell sıralaması algoritmasını kullanarak sıralayan bir program verilmiştir.

/*

     SHELL SORT
     Written by erengencturk.net
*/

#include <stdio.h>

#define ELEMENTS 6

void shellsort(int A[],int max)
{
     int stop,swap,limit,temp,k;
   int x=(int)(max/2);
   while(x>0)
   {
        stop=0;
      limit=max-x;
      while(stop==0)
      {
           swap=0;
         for(k=0;k<limit;k++)
         {
              if(A[k]>A[k+x])
            {
                 temp=A[k];
               A[k]=A[k+x];
               A[k+x]=temp;
               swap=k;
            }
         }
         limit=swap-x;
         if(swap==0)
              stop=1;
      }
      x=(int)(x/2);
   }
}

int main()
{
  int i;
  int X[ELEMENTS]={5,2,4,6,1,3};
  printf("Unsorted Array:\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);

  shellsort(X,ELEMENTS);
  printf("\nSORTED ARRAY\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);

}

Java dilinde yazılmış Shell sıralaması

public static void shellSort(int[] a) {
    for (int i = a.length / 2; i > 0;
          i = (i == 2 ? 1 : (int) Math.round(i / 2.2))) {
        for (int i2 = i; i2 < a.length; i2++) {
            int temp = a[i];
            for (int j = i2; j >= i && a[j - i] > temp; j -= i){
                a[j] = a[j - i];
                a[j - i] = temp;
            }
        }
    }
}

Python dilinde yazılmış Shell sıralaması

  def shellsort(a):
      def increment_generator(a):
          h = len(a)
          while h != 1:
              if h == 2:
                  h = 1
              else: 
                  h = 5*h//11
              yield h

      for increment in increment_generator(a):
          for i in xrange(increment, len(a)):
              for j in xrange(i, increment-1, -increment):
                  if a[j - increment] < a[j]:
                      break
                  a[j], a[j - increment] = a[j - increment], a[j]
      return a

Dış bağlantılar

"Detailed analysis of Shell sort". 16 Ocak 2000 tarihinde kaynağından arşivlendi.
Robert Sedgewick. "Analysis of Shellsort and Related Algorithms". 7 Haziran 1997 tarihinde kaynağından arşivlendi.
"Shell Sort Java Applet". 14 Mayıs 2007 tarihinde kaynağından arşivlendi.
"Best known gap sequence". 20 Şubat 2007 tarihinde kaynağından arşivlendi.
"A graphical demonstration and discussion of shell sort". 3 Nisan 2008 tarihinde kaynağından arşivlendi.