MÉTODO DE ORDENACIÓN DE SHELL

MÉTODO DE ORDENACIÓN DE SHELL

Este algoritmo pretende optimizar el número de comparaciones que hay que hacer hasta colocar el número menor en su posición correcta. Para lograrlo este método fracciona al vector en 1/2, 1/4, 1/8...etc. Supongamos que el vector original fue dividido en 2, el método compara el 1er elemento de la 1ª parte con el 1er elemento de la 2ª parte y así sucesivamente lanzando a los números mayores a la izquierda y a los menores a la derecha.

Lo siguiente es la forma lógica en que las comparaciones se realizan primero entre i y i+n/2; luego entre i y i+n/4; luego entre i y i+n/8 y así sucesivamente hasta llegar a 1.

Algoritmo (Orientado a C)

n=tamaño del arreglo

                    inicio
                    n=tamaño del vector
                    E = n+1;
                        do{
                            E=E/2;
                            do{
                                sw=0;
                                i=0;
                                do{
                                    if ( vec[i] > vec [i+E] ){
                                        aux = vec[i];
                                        vec[i] = vec[i+E];
                                        vec[i+E] = aux;
                                        sw=1;
                                    }
                                    i++;
                                while( ( i+E) != n);
                            while( sw != 0);
                        while( E != 1);
                    fin

Las variables a la izquierda indican las condiciones en las que se encuentraron cuando se hiso el cambio de valores en las casillas.

Variables						Vector
E	sw	i	vec[i]	vec[i+E]	Inicio	0	1	2	3	4	5
7					cambio	44	55	12	94	42	18
3	0	0	44	94
		1	55	42	cambio	44	42	12	94	55	18
	1	2	12	18
		3
	0	0	44	94
		1	42	55
		2	12	18
		3
	0	0	44	94
		1	42	55
		2	12	18
		3
1	0	0	44	42	cambio	42	44	12	94	55	18
	1	1	44	12	cambio	42	12	44	94	55	18
		2	44	94
		3	94	55	cambio	42	12	44	55	94	18
		4	94	18	cambio	42	12	44	55	18	94
		5
	0	0	42	12	cambio	12	42	44	55	18	94
	1	1	42	44
		2	44	55
		3	55	18	cambio	12	42	44	18	55	94
		4	55	94
		5
	0	0	12	42
		1	42	44
		2	44	18	cambio	12	42	18	44	55	94
	1	3	44	55
		4	55	94
		5
	0	0	12	42
		1	42	18		12	18	42	44	55	94
		2	42	44
		3	44	55
		4	55	94
		5
					ordenado	12	18	42	44	55	94

Si usted quiere bajar este programa haga click aquí
Si usted quiere bajar el código fuente haga click aquí