Shell Sorting


Bu algoritma Donal Shell tarafından bulunmuştur. İsmide ordan gelmektedir.

  • Direkt yerleştirmeli sıralamanın geliştirilmesiyle elde edilmiştir.
  • Diminishing  increment(azalan artış ) olarakta adlandırılır.
  • Parametre  olarak  “h” alın.
  • Her iterasyonda “h” değeri azalır ve sıfırlanmasıyla sıralama işlemi tamamlanmış olur.
  • Son  iterasyonda h=1 olması halinde tüm dizi için direkt yerleştirmeli sıralama yapılacaktır.

Çalışma Prensibi

  1. Dizi boytunu yarıya böler
  2. yarıya bölünen dizileri satır satır yazdırır.
  3. Satırların sütünlarını yukarıdan aşağı doğru küçükten büyüğe doğru sıralar.
  4. Yarıya bölünen dizilerin tekrar yarısını alır.
  5. Parçalama işi bittikten sonra dizi degerlerini yazdırır.
  6. Son olarak hazırlanmış değerlerin sıralaması için Bubble Sort kullanılır.

Bellek Kullanımı

  • Bellek kullanımında algoritma sadece O(1) ekstra alana ihtiyaç duyar
  • Selection Sort ile Bellek kullanımı bakımından aynı fakat hız olarak daha avantajlıdır

 

Shell Sort Algorithm

 

Kodlara da bir göz atacak olursak

#include<stdio.h>  
#include<conio.h>  

void shellsort(int a[],int n)
{
	int j,i,iterasyon,m,mid;
	for(m = n/2;m>0;m/=2)//paröalama işlemi
	{
		for(j = m;j< n;j++)
		{
			for(i=j-m;i>=0;i-=m)
			{
				if(a[i+m]>=a[i])
				break;
				else
				{
					mid = a[i];
					a[i] = a[i+m];
					iterasyon +=1;
					a[i+m] = mid;
				}
			}
		}
	}printf("Iterasyon %d\n",iterasyon);
}

int main()  
  {  
      int n,i;

      int dizi1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
      int dizi2[]={50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
      int dizi3[]={32,40,22,34,35,6,3,16,11,30,45,33,7,38,42,28,17,41,47,14,46,8,5,48,29,21,25,37,31,49,27,50,26,43,19,44,15,1,36,23,2,4,18,24,39,13,9,20,10,12};
      int dizi4[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,10,11,12,13,14,15,15,15,15,15,21,20,19,18,17,16,15,14,26,43,19,44,15,1,36,23,2,4,18,24,39,13,9,20,1};

      n = sizeof(dizi1)/sizeof(int);                
      shellsort(dizi1, n);                              
      for(i=0; i<n; i++) printf("%d ",dizi1[i]);       
      printf("\n \n \n");

      n = sizeof(dizi2)/sizeof(int);                
      shellsort(dizi2, n);                                
      for(i=0; i<n; i++) printf("%d ",dizi2[i]);       
      printf("\n \n \n");

      n = sizeof(dizi3)/sizeof(int);               
      shellsort(dizi3, n);                               
      for(i=0; i<n; i++) printf("%d ",dizi3[i]);      
      printf("\n \n \n");

      n = sizeof(dizi4)/sizeof(int);                   
      shellsort(dizi4, n);                               
      for(i=0; i<n; i++) printf("%d ",dizi4[i]);      

      getch();                                        
      return 0;
  }

 

Leave a reply


Powered by themekiller.com