PDF de programación - Tema II Clasificación en memoria principal - Estructura de datos y Algoritmos

Estructura de datos y
Algoritmos

Tema II
Clasificación en memoria principal

2.1. Introducción.
2.2. Métodos de clasificación directos:
2.2.1. Clasificación por inserción:
• Directa
• Binaria.
2.2.2. Clasificación por selección directa.
2.2.3. Clasificación por intercambio:
• Directo (método de la burbuja)
• Método por sacudida
2.3. Métodos de clasificación avanzados:
2.3.1. Inserción por incremento decreciente (Shell).
2.3.2. Clasificación por montón (Floyd)
2.3.3. Clasificación por partición (clasif. rápida)
• Obtención del k-ésimo menor elemento.

2.1. Introducción.
Tipos de Clasificación:

Clasificación interna (Estructuras en Mem.

Principal)

Clasificación externa (Estructuras en Mem.

Secundaria)

Cosas a tener en cuenta en la elección del
algoritmo
1. Tamaño del conjunto de datos.
2. Eficacia. Depende de (1).
3. Estabilidad:

El orden relativo de los elementos con iguales claves

permanece inalterado en el proceso de clasificación, es
decir, no intercambia elementos con claves iguales.

ordenado.

5. Tipo de clasificación:

interna o externa.

4. Comportamiento natural:

Si el mejor caso es que el arreglo esté inicialmente

Medida de la eficacia:

Depende de:

Número C de comparaciones.
Número M de movimientos.

Analizamos

El mejor caso
El promedio
El peor caso

Si ORDEN:

n2 Métodos Directos

Si ORDEN:

n * log (n) Métodos Avanzados
(Siendo "n" el número de elementos a clasificar)

2.2. Métodos de clasificación directos
Las colecciones de elementos a clasificar se

almacenarán en arreglos

Clasificación por inserción:

Consiste en insertar un elemento dado en el lugar

que le corresponda
Directa
Binaria

Clasificación por selección directa.
Clasificación por intercambio:
Directo (método de la burbuja)
Método por sacudida

Clasificación por inserción directa

En un primer paso se considera que la parte

ordenada esta formada por el primer
elemento del arreglo. El procedimiento será:
Tomar un elemento en la posición i (i= 2,3,…n)
Buscar su lugar en las posiciones anteriores

(parte ordenada)

Mover hacia la derecha los restantes
Insertarlo.

Clasificación por inserción binaria

Mejora el método de inserción.
Para ello se toma el elemento que ocupa la posición

central de la parte ordenada y se compara con el
elemento a insertar.. Si es mayor se descarta la
parte izquierda y si es menor la derecha. Aplicando
sucesivamente el mismo proceso se obtiene la
posición donde se debe insertar:
Tomar un elemento de la posición i
Buscar dicotómicamente su lugar en las posiciones

anteriores

Mover hacia la derecha los restantes
Insertarlo

2.2.2. Clasificación por selección directa.
Al hacer un movimiento colocamos el elemento en

su sitio definitivo.

En un primer paso se recorre el arreglo hasta

encontrar el elemento menor que se intercambia
con el de la primera posición.

Seguidamente se considera únicamente la parte del

arreglo no ordenada y se repite el proceso:
Seleccionar el elemento menor de la parte del arreglo no

ordenada

Colocarlo en la primera posición de la parte no ordenada

del arreglo.

Comparación de la inserción con la
selección
Inserción directa:

En cada paso un elemento siguiente de la secuencia fuente y

todos los del arreglo destino.

Selección directa:

Todos los elementos del arreglo fuente para encontrar el que es
menor y depositarlo como el siguiente elemento de la secuencia
destino.
Conclusión:

El método de selección directa es preferible al de inserción

directa ya que su número de movimientos promedio es de orden
n*Ln n.

En general, la implementación de una comparación tiene un

coste inferior al de un movimiento.

Por tanto, la selección directa será la opción a elegir en general,

aunque la inserción es algo más rápida cuando las llaves se
clasifican predominantemente al principio.

2.2.3. Clasificación por intercambio:
Clasificación por intercambio directo burbuja

Característica principal:

Intercambio de dos elementos.

Método:

Comparar e intercambiar pares de elementos
contiguos hasta clasificar todos los elementos.

Clasificación por sacudida o vibración
Mejora el método de la clasificación por burbuja alternando la

dirección de pases consecutivos.

El segundo pase comienza en las posiciones finales y se recorre en

sentido inverso al anterior.

En cada pasada hacia el final se decrementa el índice final (R) y en

cada pasada hacia el inicio se incrementa el índice de inicio (L).
El algoritmo se para, obviamente, cuando los índices se cruzan.
Análisis:

No se mejora el número de movimientos a realizar.
La mejora se realiza únicamente en el número de comparaciones.

Así los pases impares se hacen en sentido descendente y los pares

La parte del arreglo a ordenar estará en todo momento marcada por

en sentido contrario.

los índices L y R.

Conclusiones
La complejidad de los métodos directos de

clasificación de arreglos es del O(n2).

Veremos que para los métodos de clasificación

avanzada la complejidad es del O(n*lg(n)).

El método de selección directa es preferible al de

inserción directa ya que su número de movimientos
promedio es de orden n*Lg (n).

En general, la implementación de una comparación

tiene un coste inferior al de un movimiento.

Por tanto, la selección directa será la opción a elegir
en general, aunque la inserción es algo más rápida
cuando las llaves se clasifican predominantemente
al principio

2.3. Métodos de clasificación avanzados
Inserción por incremento decreciente (Shell)

Es una mejora del de inserción directa.
Este método propuesto por D .L, Shell
Se basa en la ordenación por inserción de los elementos que

difieren, h1 posiciones, después de los que difieren h2 y así
sucesivamente según un conjunto de incrementos decrecientes
hi, hasta ordenar los que difieren en ht,=1.

Existen numerosos conjuntos de incrementos decrecientes que
garantizan la clasificación del arreglo, como por ejemplo: 1,2,4,
.,.; 1,3,5,9, ...; 1,4, 13,40, 121 ,,,.; 1,3,7, I5,31, ...; etc,

Se comienza en cada caso por incremento mayor que permita el

tamaño del arreglo y se va reduciendo en cada actuación.

2.3.2. Clasificación por montón (Floyd)
Un montículo o montón se define como una
secuencia de llaves hi , i = L, L+1,...R tal que
mantienen la siguiente relación de orden:
hi <= h2i y hi <= h2i+1 para i = L,...,R/2

Seguidamente se amplía (hk...hn) tomando un
elemento por la izquierda y se reconstruye el
montón con este nuevo elemento y así
sucesivamente.

Dado un arreglo de n elementos, h1...hn, los

elementos a partir de la mitad del arreglo,
k=(nDIV2)+1, hasta el final, forman un montón
(hk...hn) puesto que no hay dos índices i,j en esta
parte que no satisfagan la definición de montón.

2.3.3. Clasificación por partición (clasif.
rápida)
Se basa en el hecho de que cuanto mayor sea la
distancia entre los elementos que se intercambian
más eficaz será la clasificación.

Se elige un valor de llave al azar, x, denominado
pivote. Se recorre el arreglo desde la izquierda
hasta encontrar una llave mayor que el pivote, y
desde la derecha hasta encontrar una menor

particiones.

Se intercambian y se repite el proceso hasta que
los índices de incremento y decremento se crucen.
De esta forma tendremos a la izquierda todos los

elementos menores que el pivote y a la derecha los
mayores.

A cada una de estas partes se denominan

Obtención del k-ésimo menor elemento.

La clasificación por partición permite,

además de clasificar un arreglo, calcular de
forma eficaz el k-ésimo elemento mayor del
mismo.

La mediana consiste en calcular el k-ésimo

mayor, con k=n/2.

Comparación (i)

Comparando los métodos directos de clasificación

sobre arreglos,
La selección directa será la opción a elegir en general,
La inserción es algo más rápida cuando las llaves

predominantemente se clasifican al principio y

La vibración puede ser mejor cuando el arreglo está

inicialmente casi ordenado.

Respecto a los métodos avanzados

La clasificación rápida tiene un magnífico comportamiento
en los casos mejor y promedio, sin embargo en el caso
peor es deficiente (cuando las llaves son muy parecidas en
valor).

En este caso es aconsejable otro método, por ejemplo, la

clasificación por montón.

Comparación (ii)

Los métodos avanzados

Presentan unos costes computacionales claramente inferiores a

los directos pero no son los más eficaces para todo n ya que
requieren más operaciones auxiliares que los directos.

Para n pequeño

Son preferibles los métodos directos ya que en estos casos las

diferencias entre los órdenes n2 y n*log(n) no son muy
significativas y las operaciones auxiliares de los avanzados
hacen que estos métodos sean menos eficaces.

En el caso de clasificación por partición,

En principio se realizará el proceso de partición, pero sólo hasta
que el tamaño de las particiones es lo suficientemente pequeño
para aplicar un m