Kabuk sıralaması

Vikipedi, özgür ansiklopedi
Kabuk sıralaması
Kabuk sıralama algoritması
SınıfSıralama algoritması
Veri yapısıDizi
Zaman karmaşıklığıO(n log² n), aralıkların dizilimine göre değişir
En iyiGenellikle değil
Alan karmaşıklığıO(n) toplam, O(1) yardımcı
Kabuk sıralaması algoritma renk çubukları

Shell sıralaması (İngilizceShell 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[değiştir | kaynağı değiştir]

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[değiştir | kaynağı değiştir]

C/C++ dilinde yazılmış Shell sıralaması[değiştir | kaynağı değiştir]

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ı[değiştir | kaynağı değiştir]

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ı[değiştir | kaynağı değiştir]

  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[değiştir | kaynağı değiştir]