PDF de programación - Algoritmos sobre secuencias y conjuntos de datos

Algoritmos sobre secuencias y conjuntos de datos

Algoritmos:

Alberto Valderruten

LFCIA - Departamento de Computación

Facultad de Informática

Universidad de A Coruña, España

www.lfcia.org/alg

www.fi.udc.es

Contenido

Algoritmos de búsqueda

Algoritmos de ordenación
• Inserción
• Shell
• Montículos (heapsort)
• Fusión (mergesort)
• Ordenación Rápida (quicksort)

Algoritmos aleatorios

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 2

Ordenación por Inserción (1)

procedimiento Ordenación por Inserción (var T[1..n])

para i:=2 hasta n hacer

x:=T[i];
j:=i-1;
mientras j>0 y T[j]>x hacer

T[j+1]:=T[j];
j:=j-1

fin mientras;
T[j+1]:=x

fin para

fin procedimiento



peor caso: max i comparaciones para cada i⇒Pn

mejor caso: min 1 comparación para cada i (entrada ordenada)

i=2 i = Θ(n2)

⇒ Θ(n)

¿caso medio?

→ cota inferior (Ω) para algoritmos de ordenación que intercambian
elementos adyacentes (inserción, selección, burbuja...)

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 3

Ordenación por Inserción (2)

Observación: ¿Inserción intercambia elementos adyacentes?

→ abstracción

Sea T [1..n] la entrada del algoritmo:
Definición: inversión ≡ cualquier (i, j) : i < j ∧ T [i] > T [j]

Ejemplo: 3

4

1

2
→ (3, 1), (3, 1), (3, 2), ..., (5, 3)

1

5

9

6

5

3

Sea I el número de inversiones: “medida del desorden” (en el ejemplo, I = 15)

Intercambiar 2 elementos adyacentes elimina una inversión

En el ejemplo, I = 15 ⇒ 15 intercambios para ordenar
hasta I = 0 ≡ vector ordenado

⇒ Inserción = O(I + n)

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 4

Ordenación por Inserción (3)

O(n) si I = 0 (mejor caso) ∨ I = O(n) (nuevo resultado)

Inserción = O(I + n)
⇒
O(n2) si I = O(n2) (peor caso)
Caso medio ⇒ ¿Imedio en una entrada?
Hipótesis:
Teorema: Imedio = n(n − 1)/4
Demostración: sean T [1..n] el vector, Ti[1..n] el vector inverso:

sin duplicados

permutaciones equiprobables

⇒ ¿Imedio en una permutación?

= (n − 1) + (n − 2) + ... + 1 =Pn−1

cualquier (x, y) es inversión en T o en Ti
No total de (x, y) con y > x
i=1 i = n(n − 1)/2
equiprobabilidad ⇒ Tmedio tiene la mitad de esas inversiones.



Aplicación: caso medio de Inserción

I = O(n2) ⇒ T (n) = O(n2)

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 5

Ordenación por Inserción (4)

Teorema: cualquier algoritmo que ordene intercambiando elementos

adyacentes requiere un tiempo Ω(n2) en el caso medio.

Demostración:

Imedio = n(n − 1)/4 = Ω(n2)
cada intercambio elimina sólo una inversión
⇒ Ω(n2) intercambios



¿Cómo conseguir un trabajo o(n2) ≡ ¬Ω(n2) ≡ “bajar de n2”?

Intercambiar elementos alejados

⇒ deshacer varias inversiones a la vez:

Ordenación de Shell

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 6

Ordenación de Shell (1)

Primer algoritmo de ordenación que baja de O(n2) para el peor caso
Secuencia de incrementos ≡ distancias para intercambios

naturales, ordenados descendentemente: ht, ...hk, hk−1, ...h1 = 1

t iteraciones: en la iteración k utiliza el incremento hk

Postcondición = {∀i, T [i] ≤ T [i + hk]}
≡ los elementos separados por hk posiciones están ordenados
→ vector hk-ordenado
Trabajo de la iteración k: hk ordenaciones por Inserción

Propiedad:

un vector hk-ordenado que se hk−1-ordena sigue estando hk-ordenado

Problema: ¿secuencia óptima de incrementos?

incrementos de Shell: ht = bn/2c, hk = bhk+1/2c

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 7

Ordenación de Shell (2)

Ordenación de Shell con incrementos de Shell:

procedimiento Ordenación de Shell (var T[1..n])

incremento := n;
repetir

incremento := incremento div 2;
para i := incremento+1 hasta n hacer

tmp := T[i];
j := i;
seguir := cierto;
mientras j-incremento > 0 y seguir hacer

si tmp < T[j-incremento] entonces

T[j] := T[j-incremento];
j := j-incremento

sino seguir := falso ;

T[j] := tmp

hasta incremento = 1

fin procedimiento

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 8

Ordenación de Shell (3)

Otros incrementos también funcionan
Ejemplo: n = 13 → 5, 3, 1 en vez de Shell (6, 3, 1)

ini

5-ord

3-ord

1-ord

81

35

28

11

94

17

12

12

11

11

11

15

96

28

35

17

12

12

15

28

35

41

41

35

17

75

58

41

95

15

17

58

28

96

94

75

58

58

75

81

41

81

81

94

75

94

96

95

15

95

95

96

Teorema: el peor caso de Shell con incrementos de Shell es Θ(n2)
Demostración:

(1) ¿Ω(n2)?

n potencia de 2 ⇒ incrementos pares excepto el último (= 1)
Peor situación:
los mayores ocupan las posiciones pares y los menores las impares
Ejemplo (el más favorable dentro de esta situación):

1

9

2

10

3

11

4

12

5

13

6

14

7

15

8

16

Es el más favorable: 8, 4 y 2-ordenado, todo el trabajo en 1-ordenar

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 9

Ordenación de Shell (4)

Demostración (cont.):

El i-ésimo menor está en la posición 2i − 1, i ≤ n/2
(ej: 8 en posición 15)
→ moverlo i − 1 veces
(ej: 8 → 7 desplazamientos)

⇒ colocar menores:Pn/2

i=1 i − 1 = Ω(n2)

(2) ¿O(n2)?

Trabajo realizado en iteración k con el incremento hk:
hk ordenaciones por Inserción sobre n/hk elementos cada una
= hkO((n/hk)2) = O(hk(n/hk)2) = O(n2/hk)
En el conjunto de iteraciones del algoritmo:

i=1 n2/hi) = O(n2Pt

T (n) = O(Pt

i=1 1/hi) = O(n2)



Observación 1: 6= O(n3) (← 3 bucles anidados)

Observación 2: No baja de O(n2) para el peor caso...

→ otros incrementos

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 10

Ordenación de Shell (5)

Otros incrementos:

incrementos
Hibbard: 1, 3, 7..,2k − 1
Sedgewick: 1, 5, 19, 41, 109... O(n4/3) (sim) O(n7/6) (sim, varias sec.)

O(n5/4) (sim)

caso medio

peor caso

Θ(n3/2) (teo)

Tabla: Complejidad temporal de la ordenación de Shell con distintos

incrementos.

Observación: código sencillo y resultados muy buenos en la práctica

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 11

Ordenación por montículos (1)

Algoritmo de ordenación por montículos (heapsort):

procedimiento Ordenación por montículos ( var T[1..n])

Crear montículo (T, M);
para i := 1 hasta n hacer

T[n-i+1] := Obtener mayor valor (M);
Eliminar mayor valor(M)

fin para

fin procedimiento

Procedimiento para crear un montículo a partir de un vector:

procedimiento Crear montículo (V[1..n], var M)
{ V[1..n]: entrada: vector con cuyos datos se construirá el montículo

M: entrada/salida: montículo a crear }

Copiar V[1..n] en M[1..n];
para i := n div 2 hasta 1 paso -1 hacer

hundir(M,i)

fin para

fin procedimiento

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 12

Ordenación por montículos (2)

¿Cómo mejorar la complejidad espacial (y algo T (n))?

→ utilizar la misma estructura
Ejemplo:

entrada
Crear Mont.
Eliminar(9)
Eliminar(8)
Eliminar(7)
Eliminar(6)
Eliminar(5)
Eliminar(4)
Eliminar(3)

4
9
8
7
6
5
4
3
3

3
6
6
6
4
4
3
4
4

7
8
7
5
5
3
5
5
5

9
3
3
3
3
6
6
6
6

6
4
4
4
7
7
7
7
7

5
5
5
8
8
8
8
8
8

8
7
9
9
9
9
9
9
9

Teorema: La ordenación por montículos es O(nlogn)
Demostración:

Crear Montículo es O(n), y n Eliminar es O(nlogn)



Observación: Incluso en el peor caso es O(nlogn),

pero en la práctica es más lento que Shell con incrementos de Sedgewick.

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 13

Ordenación por fusión (1)

O bien, por intercalación, o mergesort.

Utiliza un algoritmo de Fusión de un vector cuyas mitades están ordenadas
para obtener un vector ordenado:

procedimiento Fusión ( var T[Izda..Dcha], Centro:Izda..Dcha )
{fusiona los subvectores ordenados T[Izda..Centro] y T[Centro+1..Dcha] en T[Izda..Dcha],}
{utilizando un vector auxiliar Aux[Izda..Dcha]}

i := Izda ; j := Centro+1 ; k := Izda ;
{i, j y k recorren T[Izda..Centro], T[Centro+1..Dcha] y Aux[Izda..Dcha] respectivamente}
mientras i <= Centro y j <= Dcha hacer

si T[i] <= T[j] entonces Aux[k] := T[i] ; i := i+1
sino Aux[k] := T[j] ; j := j+1 ;
k := k+1 ;

{copia los elementos restantes del subvector que no se ha terminado de recorrer}
mientras i <= Centro hacer

Aux[k] := T[i] ; i := i+1 ; k := k+1 ;

mientras j <= Dcha hacer

Aux[k] := T[j] ; j := j+1 ; k := k+1 ;

para k := Izda hasta Dcha hacer

T[k] := Aux[k]

fin procedimiento

El procedimiento Fusión es lineal (n comparaciones).

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 14

Ordenación por fusión (2)

Ordenación: algoritmo Divide y Vencerás

- Divide el problema en 2 mitades, que se resuelven recursivamente.
- Fusiona las mitades ordenadas en un vector ordenado.
- Mejora: Ordenación por Inserción para vectores pequeños (n < umbral).

procedimiento Ordenación por Fusión Recursivo ( var T[Izda..Dcha] )

si Izda+UMBRAL < Dcha entonces

Centro := ( Izda+Dcha ) div 2 ;
Ordenación por Fusión Recursivo ( T[Izda..Centro] ) ;
Ordenación por Fusión Recursivo ( T[Centro+1..Dcha] ) ;
Fusión ( T[Izda..Dcha], Centro )

fin procedimiento

procedimiento Ordenación por Fusión ( var T[1..n] )

Ordenación por Fusión Recursivo ( T[1..n] );
Ordenación por Inserción ( T[1..n] )

fin procedimiento

Algoritmos - Algoritmos sobre secuencias y conjuntos de datos - 15

Ordenación por fusión (3)

Análisis de la versión puramente recursiva ≡ UMBRAL = 0:

T (1) = O(1)

T (n) = T (bn/2c) + T (dn/2e) + O(n) (Fusión)
Hip: n potencia de 2 ⇒
Teorema Divide y Vencerás: l = 2, b = 2, c = 1, k = 1, n0 = 1
caso l = bk ⇒ T (n) = Θ(nlogn)

= 1

T (n) = 2T (n/2) + O(n) = 2T (n/2) + n, n > 1

Podría mejorarse la complejidad espacial (= 2n: vector auxiliar)

→ El algoritmo adecuado es quicksort.

Observación: importancia de balancear los subcasos en Divide y Vencerás:
Si las llamadas recursivas fueran con subvectores de tamaños n − 1 y 1:
⇒ T (n) = T (n − 1) + T (1) + n = O(n2)
... pero ya no sería ordenación por