Ordenamiento Shell

Método de Ordenamiento Shell

Ordenamiento por intervalos decrecientes, nombrado así debido a su inventor Donald Shell,

este algoritmo ordena subgrupos de elementos separados que unidades respecto de su posición

en el arreglo. El valor K es llamado intervalo. Después de que los primeros K subgrupos fueron

ordenados generalmente utilizando inserción directa, se escoge un nuevo valor de K mas

pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de

los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor mas pequeño de K.

Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del

subgrupo y se aplica inserción directa.El método se basa en tomar como salto al principio N/2,

siendo N el numero de elementos, y luego se va reduciendo a la mitad en cada repetición hasta lograr un valor de 1.

El método Shell es una versión mejorada del método de inserción directa.

Este método también se conoce con el nombre de inserción con incrementos crecientes.

Análisis de eficiencia del ordenamiento Shell

El análisis de eficiencia de este método en un problema muy complicado y aun no resuelto.

Nadie ha capaz de establecer la mejor secuencia de incrementos cuando N es muy grande.

Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario "correr"

el algoritmo para analizar el tiempo de ejecución del mismo.

2)

• Algoritmo en java del ordenamiento Shell realizado por el grupo

public static int[] vecrandom(int n){

int v[]=new int[n+1];

Random rn=new Random();

for(int i=1;i<=n;i++) v[i]=rn.nextInt(1000)+1;

return v;

}

public static int[] shellempanada( int n , int v[] ) {

int i,cont=0,sc=0,sw=0,salt=1,val=0,vuelt=0;

while (salt>0) {

if (sw==0) salt=n/2;

sw=0;

while (sw==0) {

sc=salt+1;

vuelt=n-salt;

for(i=1;i<=vuelt;i++){

if(v[i]>v[sc]) {

val=v[i];

v[i]=v[sc];

v[sc]=val;

cont++;

}

sc++;

}

if(cont==0) {

salt=salt/2;

sw=1;

}

cont=0;

sc=0;

}

}

return v;

}

public static void main (String[] args) {

int n,a[],i,j,k,cont=0,sc=0,sw=0,salt=1,val=0,vuelt=0;

...