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ı (İngilizcesi: 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ı
1 public static void shellSort(int[] a) {
2 for (int i = a.length / 2; i > 0;
3 i = (i == 2 ? 1 : (int) Math.round(i / 2.2))) {
4 for (int i2 = i; i2 < a.length; i2++) {
5 int temp = a[i];
6 for (int j = i2; j >= i && a[j - i] > temp; j -= i){
7 a[j] = a[j - i];
8 a[j - i] = temp;
9 }
10 }
11 }
12 }
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
- Analysis of Shellsort and Related Algorithms, Robert Sedgewick
- Shell Sort Java Applet
- Best known gap sequence
- A graphical demonstration and discussion of shell sort
This article is issued from Vikipedi - version of the 12/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.