AN LISIS DEL ALGORITMO SHELLSORT
Páginas: 3 (655 palabras)
Publicado: 14 de abril de 2015
ANÁLISIS DEL ALGORITMO SHELLSORT
• Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del Bubble Sort, sin embargo no ordena elementosadyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande y van disminuyendo hastallegar al '1'.
DESCRIPCIÓN DEL MÉTODO
• El ShellSort 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 K subgrupos 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 nuevoconjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Cuando el incremento toma un valor de 1, todos los elementos pasan aformar parte del subgrupo y se aplica inserción directa.
• Para ilustrar mejor el proceso que sigue el procedimiento ShellSort, se tomará como ejemplo el vector :{6,1,5,2,3,4,0}
6 1 5 2 3 4 0 6 > 2 2042 602 4 5 6 1 > 3 54 6 > 0 2
Salto 3
• Lista Original n=7.
• Intervalo Inicial: n/2=7/2=3 – Intervalos Siguientes=IntervaloAnterior/2 •
Se compara a[i] con a[i+Intervalo] – Si No Están OrdenadosEntonces CAMBIARLOS
a[0] a[1] a[2] a[3] a[4] a[5] a[6] 6 1 5 2 3 4 0
Paso Intervalo Parejas que Intercambian por estar desordenados La Lista Queda 1 3 (6,2)= 2, 1, 5,6, 3, 4, 0 (5,4)= 2, 1, 4,6, 3,5,0 (6;0)=2, 1, 4,0, 3,5, 6 2, 1, 4,0, 3,5, 6 2 3 (2, 0)=0, 1, 4,2, 3,5, 6 0, 1, 4,2, 3,5, 6 3 3 Ninguno 0, 1, 4,2, 3,5, 6 4 3/2=1 (4, 2)=0, 1, 2,4, 3,5, 6 (4, 3)= 0, 1, 2,3,4,5, 6 0, 1, 2,3, 4,5, 6 5 1Ninguno Lista Ordenada
COMPLEJIDAD
• Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O ( n 2) (usando los incrementos de Shell...
• Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del Bubble Sort, sin embargo no ordena elementosadyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande y van disminuyendo hastallegar al '1'.
DESCRIPCIÓN DEL MÉTODO
• El ShellSort 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 K subgrupos 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 nuevoconjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Cuando el incremento toma un valor de 1, todos los elementos pasan aformar parte del subgrupo y se aplica inserción directa.
• Para ilustrar mejor el proceso que sigue el procedimiento ShellSort, se tomará como ejemplo el vector :{6,1,5,2,3,4,0}
6 1 5 2 3 4 0 6 > 2 2042 602 4 5 6 1 > 3 54 6 > 0 2
Salto 3
• Lista Original n=7.
• Intervalo Inicial: n/2=7/2=3 – Intervalos Siguientes=IntervaloAnterior/2 •
Se compara a[i] con a[i+Intervalo] – Si No Están OrdenadosEntonces CAMBIARLOS
a[0] a[1] a[2] a[3] a[4] a[5] a[6] 6 1 5 2 3 4 0
Paso Intervalo Parejas que Intercambian por estar desordenados La Lista Queda 1 3 (6,2)= 2, 1, 5,6, 3, 4, 0 (5,4)= 2, 1, 4,6, 3,5,0 (6;0)=2, 1, 4,0, 3,5, 6 2, 1, 4,0, 3,5, 6 2 3 (2, 0)=0, 1, 4,2, 3,5, 6 0, 1, 4,2, 3,5, 6 3 3 Ninguno 0, 1, 4,2, 3,5, 6 4 3/2=1 (4, 2)=0, 1, 2,4, 3,5, 6 (4, 3)= 0, 1, 2,3,4,5, 6 0, 1, 2,3, 4,5, 6 5 1Ninguno Lista Ordenada
COMPLEJIDAD
• Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O ( n 2) (usando los incrementos de Shell...
Leer documento completo
Regístrate para leer el documento completo.