Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Shell Sort

No description
by

daniel juarez

on 2 May 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Shell Sort

Shell sort Implementación en C
for(gap=n/2;gap>0;gap=gap/2)
{
for(i=0;i<n;i=i+gap)
{
temp=a[i];
for(j=i;j>0&&a[j-gap]>temp;j=j-gap)
{
a[j]=a[j-gap];
}
a[j]=temp;
}
} Caracteristicas 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. 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. Sin embargo, optimizaciones posteriores han logrado reducirloPor ejemplo, con la optimización de Robert Sedgewick se llega a O(n^4/3) Con la propuesta por Vaughan Pratt se llega al orden de O(n*log^2 * n). No es estable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos Shell nos propone que hagamos sobre el array una serie de ordenaciones basadas en la inserción directa, pero dividiendo el array original en varios sub-arrays tales que cada elemento esté separado k elementos del anterior (a esta separación a menudo se le llama salto o gap)... Se debe empezar con k=n/2, siendo n el número de elementos de array, y utilizando siempre la división entera Debe su nombre al ingeniero y matemático estadounidense Donald Shell, que lo publicó en la revista Communications of the ACM en 1959 Ventajas y desventajas Ventajas

- Una ventaja del Shellsort es su eficiencia para listas de tamaño medio y pequeño. Para listas de mayor tamaño, este algoritmo no es la mejor opción.
- Shellsort es el algoritmo más rápido de todos aquellos de complejidad O(n^2), como es el caso del Bubble sort y el Insert sort.
- Es 5 veces más rápido que Bubble sort y aproximadamente dos veces más rápido que el insertion sort, su competidor más cercano.
- A diferencia de Radix, Quick y Merge sort, no necesita de memoria externa o pilas de llamadas. Ventajas

- Una ventaja respecto al Insertion sort es:

Cuando el intercambio ocurre en un segmento no continuo, el intercambio mueve el elemento una distancia mayor dentro del arreglo. Insertion sort solamente mueve el elemento una posición a la vez.

Debido a que hay mayor probabilidad de que los elementos esten ordenados en su posición final, el arreglo de vuelve parcialmente ordenado. Desventajas

- Una desventaja del Shellsort es que su eficiencia no se compara con los métodos de ordenamiento de merge, heap y quick sort.

- Shellsort es significativamente más lento que el merge, heap y quick sort, sin embargo, debido a la relativa simpleza del algoritmo, es una buena opción para ordenar listas de menos de 5000 elementos, a menos que la velocidad sea importante. . Complejidad 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(n^2) Imagina que te piden que en lugar de ordenar enteros, tienes que ordenar piedras... Si, si... piedras... por tamaño, con ayuda de una carretilla. Si colocas las que son más o menos pequeñas hacia el principio y las que son más gordas hacia el final, dejando las medianas por la mitad, no habrás conseguido ordenar las piedras todavía... pero las habrás dejado mucho más cerca de su ubicación definitiva. Ordenarlas ahora exhaustivamente supone menos esfuerzo.





Esta es la idea básica del ShellSort: si podemos desplazar "a grosso modo" los elementos más grandes hacia el final y los más pequeños hacia el principio con poco esfuerzo, estaremos dejando cada elemento más cerca de su ubicación definitiva. González Márquez Oscar.
Juárez Juárez Daniel.
Ramos Guitiérrez Josue.
Solórzano Villanueva Pilar.
Zamudio López Irvin.

1CM6
Estructura de datos
Full transcript