Informatica

Cap´ıtulo 2
M´
etodos de ordenaci´
on
2.1.

Ordenaci´
on por inserci´
on

La idea principales del funcionamiento m´etodo de ordenaci´on de una tabla T
con ´ındices entre P y U por inserci´on es realizar de manera iterada entre i = P +1
y U lo siguiente:
1. Suponer al inicio de la iteraci´on i-´esima que la subtabla T [P ], T [P +1], ...., T [i−
1] contiene elementos ordenados entresi, es decir
T [P ] < T [P + 1] < .... < T [i − 1].
2. En la iteraci´on i, el elemento T [i] se coloca en la posici´on correspondiente
de la subtabla T [P ], T [P + 1], ...., T [i − 1].
Ejemplo
P = 1, U = 4, T = [1 4 3 2]. En la iteraci´on i = 3, la tabla pasa a 1 4| 3 2 −→
1 3 4| 2 y luego pasar´ıamos a insertar para i = 4.
El pseudoc´odigo del m´etodo de inserci´on es el siguiente:InsertSort(Tabla T, ind P, ind U)
para i de P+1 a U:
A=T[i];
// variable auxiliar para evitar swaps
j=i-1;
mientras (j >= P && T[j]>A):
T[j+1]=T[j];
j--;
T[j+1]=A;
1

La operaci´on b´asica del algoritmo es la comparaci´on de clave T [j] > A situada
dentro del bucle. Para el an´alisis suponemos P = 1, U = N y T = σ. El trabajo del
bucle interno mientras (j >= P && T[j]>A) es muydependiente del estado
de la tabla, con lo cual es conveniente escribir
N

nIS (σ) =

nIS (σ, i)

(2.1)

i=2

donde nIS (σ, i) es el n´
umero de operaciones b´asicas que InsertSort realiza sobre
una tabla σ en la iteraci´on i-´esima.
Observando el pseudoc´odigo podemos acotar:
N

N

1 ≤ nIS (σ, i) ≤ i − 1 ⇒

1≤
i=2

N

nIS (σ, i) ≤
i=2

N −1

(i − 1) =
i=2

i
i=1

y portanto
N2 N
−
N − 1 ≤ nIS (σ) ≤
2
2
N2
2

(2.2)

Para la estimaci´on de WIS (N ) acabamos de encontrar una funci´on f (N ) =
− N2 tal que
nIS (σ) ≤

N2 N
− ∀σ ∈ EIS (N )
2
2

y por tanto
WIS (N ) ≤

N2 N
− .
2
2

Por otro lado si consideramos
σ
˜ = [N, N − 1, N − 2, ..., 3, 2, 1],
es f´acil comprobar que nIS (˜
σ , i) = i − 1 y por tanto
nIS (˜
σ) =

(i − 1) =i=2

N2 N
− .
2
2

Por tanto se tiene (ver secci´on 1.10):
WIS (N ) =

N2 N
− .
2
2

(2.3)

El caso mejor BIS (N ) se estima de forma similar, tomando en este caso la
permutaci´on σ
˜ = [1, 2, 3, ..., N − 1, N ], con lo que se obtiene (se dejan los detalles
como ejercicio):
BIS (N ) = N − 1.

(2.4)

Para la estimaci´on del caso medio empleamos la definici´on, asumimosequiprobabilidad y usamos de nuevo la cantidad intermedia nIS (σ, i):

AIS (N ) =
σ∈ΣN
N

=
i=2

1
nIS (σ)p(σ) =
N ! σ∈Σ

1
nIS (σ, i) =
N ! σ∈Σ
N

N

nIS (σ, i)
N

i=2

N

AIS (σ, i)

(2.5)

i=2

donde AIS (σ, i) es el trabajo medio que realiza el algoritmo InsertSort en la
iteraci´on i.
Para estimar AIS (σ, i) sea σ(i) el elemento que est´a en la posici´on i alinicio
de la i-´esima iteraci´on. Por el funcionamiento del algoritmo InsertSort se tiene en
ese momento que
σ(1) < σ(2) σ(j))
1 (σ(i) > σ(i − 1))
1 (σ(i) > σ(i − 2))
1 (σ(i) > σ(i − 3))

Total CDC
1
2
3

i-2 (σ(i) < σ(i − 1), ..., σ(i) < σ(3))
i-2 (σ(i) < σ(i − 1), ..., σ(i) < σ(2))
i-1 (σ(i) < σ(i − 1), ..., σ(i) < σ(1))

1 (σ(i) > σ(2))
1 (σ(i) > σ(1))
0

i-2
i-1
i-1Cuadro 2.1: Posibles CDCs en la iteraci´on i.
Por tanto podemos calcular
AIS (σ, i) = 1p(1) + 2p(i − 1) + ... + (i − 1)p(2) + (i − 1)p(1)

donde p(j) es la probabilidad es la probabilidad de que σ(i) termine en la posici´on
j(j ≤ i) tras la iteraci´on i. Asumiendo de nuevo equiprobabilidad se tiene que
p(j) ≃ 1/i al haber un total de i posibles posiciones (1, 2, 3, ..., i − 1, i) donde
puedesituarse el elemento σ(i). Con lo cual se tiene
1
AIS (σ, i) ≃
i

i−1

i+
j=1

i−1 i−1
i−1
=
+
i
2
i

Sustituyendo en (2.5) se tiene
N

AIS (σ, i) =
i=2

i−1 i−1
+
2
i

N −1

=
j=1

i
+
2

N −1

j=1

j
N2
+ O(N )
=
j+1
4

(2.6)

O(1)
O(N )

En el caso de InsertSort se tiene AIS (N ) ≃ 12 WIS (N ); por lo tanto InsertSort
es un m´etodo...