Kabuk sıralaması
Vikipedi, özgür ansiklopedi
Kabuk sıralaması | |
---|---|
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[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]
- "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.