analisis de complejidad de shellsort

INSTITUTO TECNOLOGICO SUPERIOR DE MISANTLA.



MAESTRIA EN SISTEMAS COMPUTACIONALES.


ANALISIS Y DISEÑO DE ALGORITMOS
DR. LUIS ALBERTO MORALES ROSALES.



ANALISIS DE COMPLEJIDAD DE ALGORITMOSHELLSORT.
ISC. YELITZA DIANAHI VIVEROS VARGAS









INTRODUCCION.
El estudio de algoritmos de ordenamiento tiene una gran importancia dentro de la Ciencia de la Computación, pues una buena cantidad delos procesos realizados por medios computacionales requieren que sus datos estén ordenados. Además, el hecho de almacenar los datos de manera ordenada permite implementar algoritmos de búsqueda muyrápidos. Esta y muchas otras razones de fin práctico impulsaron el estudio y la búsqueda de algoritmos de ordenamiento eficientes.
Este algoritmo de ordenación fue creado por Donald Shell, elalgoritmo se denomina Shell en honor a su inventor. El algoritmo se parece al algoritmo de ordenación por inserción. En el algoritmo de inserción, cada elemento se compara con los elementos contiguos de suizquierda de uno en uno, pero con el algoritmo de Shell la comparación se hace con intervalos mayores a uno, logrando con ello que la ordenación sea más rápida.

DESARROLLO.
En este método deordenamiento consiste en ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento. Después de que los primeros Ksubgrupos han sido ordenados (generalmente utilizando inserción directa), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno delos subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
El algoritmo es algo así:
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 )){
for( int i = gap; i < a.length; i++ ){
c=c+1;
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){...