Métodos de Ordenamientos

 

Burbuja Shell Insercion Seleccion Volver

Método de Ordenación Shell

 

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell.

 

Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso.

 

Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n).

 

Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

 

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.

 

Otro diagrama de flujo del ordenamiento Shell.

 

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


int a[5]; 
int n=5; 
 

void main() 
{ 
  int inter=(n/2),i=0,j=0,k=0,aux; 
  clrscr(); 
  for (i=0; i<5; i++) 
  { 
    printf("INSERTA UN VALOR DEL INDICE %d", i); 
    scanf("%d",& a); 
  } 
  while(inter>0){ 
  for(i=inter;i<n;i++) 
 { 
   j=i-inter; 
  while(j>=0)

 { 
  k=j+inter; 
  if(a[j]<=a[k]){ 
  j--; 
 } 
else

 { 
   aux=a[j]; 
   a[j]=a[k]; 
   a[k]=aux; 
   j=j-inter; 
  } 
 } 
} 
inter=inter/2; 
} 
for(i=0;i<5;i++) 
{ 
printf("%d n",a); 
getch(); 
} 
} 

 

 

Ver la animación por el método búsqueda Shell o Shell Sort     --> Ver Animación

 

 

 

 

 

Volver

 

 

*