Método de ordenación Shell

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados. El numero de operaciones necesarias es O(n^1.25).

Ejemplo en c++:

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

void shellsort(int a[],int n)
{
 int j,i,k,m,mid;
 for(m = n/2;m>0;m/=2)
 {
  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];
    a[i+m] = mid;
   }
  }
 }
}
}

main()
{
 int a[10],i,n;
 clrscr();

 printf("Ingrese numero de elementos\t: ");
 scanf("%d",&n);
 for(i=0;i< n;i++)
 {
  printf("\nElemento %d\t: ",i+1);
  scanf("%d",&a[i]);
 }

 printf("\nVector antes de ordenar : ");
 for(i=0;i< n;i++)
 printf("%5d",a[i]);
 shellsort(a,n);

 printf("\nVector luego de ordenar : ");
 for(i=0;i< n;i++)
 printf("%5d",a[i]);
 getch();
 return 0;
}

/* OUTPUT

Ingrese numero de elementos : 5
Elemento 1 : 21
Elemento 2 : 36
Elemento 3 : 54
Elemento 4 : 2
Elemento 5 : 0

Vector antes de ordenar : 21 36 54 2 0
Vector luego de ordenar : 0 2 21 36 54
*/