El método de Shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.
En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.
CARACTERÍSTICAS
• Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.
• Se basa en comparaciones e intercambios.
• Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
• No es estable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos
• El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
• Sin embargo, optimizaciones posteriores han logrado reducir esa cota... Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log2n).
• En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que es posible incluso rebajar aún más esas cotas.
• En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
• No es un algoritmo en-línea.
• Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
• No es estable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos
• El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
• Sin embargo, optimizaciones posteriores han logrado reducir esa cota... Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log2n).
• En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que es posible incluso rebajar aún más esas cotas.
• En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
• No es un algoritmo en-línea.
EFICIENCIA
El análisis de eficiencia es un problema complicado y aun no resuelto.
Nadie ha sido capaz de establecer la mejor secuencia de incrementos cuando N es muy grande.
Una medida de eficiencia es:
Contar el # de comparaciones (C)
Contar el # de movimientos de items (M)
Estos están en función de el #(n) de items a ser ordenados.
Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2
Una medida de eficiencia es:
Contar el # de comparaciones (C)
Contar el # de movimientos de items (M)
Estos están en función de el #(n) de items a ser ordenados.
Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2
No hay comentarios:
Publicar un comentario