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

MÉTODO DE ORDENAMIENTO SHELL

No description
by

Isabel Galo

on 17 March 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of MÉTODO DE ORDENAMIENTO SHELL

Método de Ordenación
(Procedimiento)
Características
• Se trata de un algoritmo de ordenación interna.
• Se basa en comparaciones e intercambios.
• En cierto modo, puede considerarse una ampliación del
algoritmo de inserción directa.
• No es estable: dados dos elementos que al
compararlos sean "iguales".
Pseudocódigo
Prueba de escritorio
YES!
Análisis de complejidad
Shell tiene un tiempo
de ejecución
en el peor caso de
O(n2)
usando los incrementos
de Shell que comienzan
con 1/2 del tamaño
del vector y se dividen
por 2 cada vez.

El mejor de los casos seria: O(n logn), puesto
sigue realizando la división de del numero total de datos hasta llegar a la insercion
Gráfica
GRACIAS!!!
Ejemplo
Definición
El algoritmo Shell sort nos permite ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada (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 de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K, dado que el último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
MÉTODO DE ORDENAMIENTO SHELL
Dividir la lista en n=n/2
grupos de dos,
considerando un
incremento
o salto entre los
elementos de n=n/2.
Clarificar cada grupo
por separado,
comparando
las parejas de elementos,
y si no estan ordenados,
se intercambian.
Se divide ahora la lista
en la mitad de grupos
(n=n/2), con incremento o
salto entre los elementos
también (n=n/2) y
nuevamente se clasifica
cada grupo por separado.
Así sucesivamente, se
sigue dividiendo la lista
en la mitad de grupos
que en el recorrido
anterior con un incremento
o salto decreciente en
la mitad que el salto
anterior, y luego clasificando
cada grupo por separado.
El algoritmo
termina
cuando se consigue
que el tamaño
de salto sea 1.
PASOS A SEGUIR
Ventajas y Desventajas
• Es uno de los algoritmos
más rápidos.
• No requiere memoria
adicional.
•Mejor rendimiento que
el método
de inserción clásico.
•Fácil implementación.
• Lento en cuanto a los
siguientes métodos
de ordenamiento.
•Realiza numerosas
comparaciones e
intercambios.
Función Shell ( arreglo[])

VARIABLES
i,j,incremento,aux: ENTERO;

INICIO
incremento <-- num/2;
MIENTRAS (incremento>0) HACER

PARA i <-- (incremento+1) HASTA (i<=num)
j=i-incremento;
MIENTRAS j>0 HACER
SI (arreglo[j]>=arreglo[j+incremento]) ENTONCES
aux <-- arreglo[j];
arreglo[j] <-- arreglo[j+incremento];
arreglo[j+incremento] <-- aux;
SINO
j <-- 0;
FIN (SI)
j= j - incremento;
FIN (MIENTRAS)
FIN (PARA)
incremento=incremento/2;
FIN (MIENTRAS)
TERMINA.
Full transcript