ordenacion_insercion

Nmero de operaciones de un comando (funcin ops)Ordenacin por insercin

Resumen

Algoritmos y Estructuras de Datos II

Ordenacin

11 de marzo de 2015

Ordenacin Algoritmos y Estructuras de Datos II


Resumen

Contenidos

1 Nmero de operaciones de un comando (funcin ops)

2 Ordenacin por insercinEjemploAlgoritmoAnlisis

3 Resumen



Resumen

Nmero de operaciones de un comando

Una vez que uno sabe qu operacin quiere contar, debeimaginar una ejecucin arbitraria, genrica del comandointentando contar el nmero de veces que esa ejecucinarbitraria realizar dicha operacin.se es el verdadero mtodo para contar.Es imprescindible comprender cmo se ejecuta elcomando.A modo de ayuda, en las filminas que siguen se da unmtodo imperfecto para ir aprendiendo.El mtodo supone que ya sabemos cul operacinqueremos contar.



Resumen

Nmero de operaciones de un comandoSecuencia de comandos

Una secuencia de comandos se ejecuta de manerasecuencial, del primero al ltimo.Para contar cuntas veces se ejecuta la operacin,entonces, se cuenta cuntas veces se ejecuta en elprimero, cuntas en el segundo, etc. y luego se suman losnmeros obtenidos:ops(C1;C2;. . . ;Cn) = ops(C1) + ops(C2) + . . .+ ops(Cn)ops(C1;C2;. . . ;Cn) =

ni=1 ops(Ci )



Resumen

Nmero de operaciones de un comandoComando skip

El comando skip equivale a una secuencia vaca:ops(skip) = 0



Resumen

Nmero de operaciones de un comandoComando for

El comando for k:= n to m do C(k) od equivale tambin auna secuencia:for k:= n to m do C(k) od equivalea C(n);C(n+1);. . . ;C(m)ops(for k:= n to m do C(k) od) =

ops(C(n))+ops(C(n+1))+. . . +ops(C(m))ops(for k:= n to m do C(k) od) =

mk=n ops(C(k))

Esta ecuacin solamente vale cuando no se quierencontar las operaciones que involucran el ndice kimplcitas en el for: inicializacin, comparacin con la cotam, incremento; ni el cmputo de los lmites n y m. Por esoescribimos equivale entre comillas. En los apuntes hayotras ecuaciones posibles para el caso en que s quierancontarse.



Resumen

Nmero de operaciones de un comandoComando condicional if

El comando if b then C else D fi se ejecuta evaluando lacondicin b y luego, en funcin del valor de verdad que seobtenga, ejecutando C (caso verdadero) o D (caso falso).Para contar cuntas veces se ejecuta la operacin,entonces, se cuenta cuntas veces se la ejecuta durante laevaluacin de b y luego cuntas en la ejecucin de C o D

ops(if b then C else D fi) ={

ops(b)+ops(C) b es Vops(b)+ops(D) b es F



Resumen

Nmero de operaciones de un comandoAsignacin

El comando x:=e se ejecuta evaluando la expresin e ymodificando la posicin de memoria donde se aloja lavariable x con el valor de e.

ops(x:=e) =

ops(e)+1 si se quiere contar la asignacin

o las modificaciones de memoriaops(e) caso contrario



Resumen

Nmero de operaciones de un comandoEl ciclo do

El ciclo do b C od (o equivalente while b do C od) seejecuta evaluando la condicin b, y dependiendo de si suvalor es V o F se contina de la siguiente manera:

si su valor fue F, la ejecucin termina ahsi su valor fue V, la ejecucin contina con la ejecucin delcuerpo C del ciclo, y luego de eso vuelve a ejecutarse todoel ciclo nuevamente.

Es decir que su ejecucin es una secuencia deevaluaciones de la condicin b y ejecuciones del cuerpo Cque finaliza con la primera evaluacin de b que d F.



Resumen

Nmero de operaciones de un comandoEl ciclo do

ops(do b C od) = ops(b) +n

k=1dk

donde

n es el nmero de veces que se ejecuta el cuerpo del dodk es el nmero de operaciones que realiza la k -simaejecucin del cuerpo C del ciclo y la subsiguienteevaluacin de la condicin o guarda b



Resumen

Nmero de operaciones de una expresin

Similares ecuaciones se pueden obtener para laevaluacin de expresiones.Por ejemplo, para evaluar la expresin e


Resumen

Ejemplo: nmero de comparaciones de la ordenacinpor seleccin

ops(selection_sort(a)) =n-1

i=1 ops(min_pos_from(a,i))

=n-1

i=1n

j=i+1 ops(a[j] < a[minp])

=n-1

i=1n

j=i+1 1

=n-1

i=1 (n-i)

=n-1

i=1 i

=n*(n-1)

2= n

2

2 n2



Resumen

Ejemplo: nmero de intercambios de la ordenacinpor seleccin

ops(selection_sort(a)) =n-1

i=1 ops(swap(a,i,minp))

=n-1

i=1 1= n-1



Resumen

Conclusin del ejemplo

Nmero de comparaciones de la ordenacin por seleccin:n22 n2

Nmero de intercambios de la ordenacin por seleccin:n-1Esto significa que la operacin de intercambio no esrepresentativa del comportamiento de la ordenacin porseleccin, ya que el nmero de comparaciones crece msque proporcionalmente respecto a los intercambios.Por otro lado, pudimos contar las operaciones de maneraexacta.



Resumen

EjemploAlgoritmoAnlisis

Ordenacin por insercin

No siempre es posible contar el nmero exacto deoperaciones.Un ejemplo de ello lo brinda otro algoritmo de ordenacin:la ordenacin por insercin.Es un algoritmo que se utiliza por ejemplo en juegos decartas, cuando es necesario mantener un gran nmero decartas en las manos, en forma ordenada.Cada carta que se levanta de la mesa, se inserta en ellugar correspondiente entre las que ya estn en lasmanos, manteniendolas ordenadas.



Resumen


Ordenacin por insercinEjemplo

9 3 1 3 5 2 7

9 3 1 3 5 2 7

3 9 1 3 5 2 7

3 1 9 3 5 2 7

1 3 9 3 5 2 7

1 3 3 9 5 2 7

1 3 3 5 9 2 7

1 3 3 5 2 9 7

1 3 3 2 5 9 7

1 3 2 3 5 9 7

1 2 3 3 5 9 7

1 2 3 3 5 7 9



Resumen


Demo (www.sorting-algorithms.com)



Resumen


Ordenacin por insercinEn un arreglo

a

- -a[1,i)

ordenado

a[i,n] = A[i,n]

an no insertados

1 2 3 i -1 i n-1 n



Resumen


Ordenacin por insercinInvariante

a

- -a[1,i)

ordenado

a[i,n] = A[i,n]

an no insertados

1 2 3 i -1 i n-1 n

Invariante:el arreglo a es una permutacin del original yun segmento inicial a[1,i) del arreglo est ordenado.(pero en general a[1,i) no contiene los mnimos del arreglo)



Resumen


Ordenacin por insercinPseudocdigo

{Pre: n 0 a = A}proc insertion_sort (in/out a: array[1..n] of T)

for i:= 2 to n do {Inv: Invariante de recin}insert(a,i)

odend proc{Post: a est ordenado y es permutacin de A}



Resumen


Ordenacin por seleccinInvariante del procedimiento de insercin

a

- -a[1,i] sin celda j

ordenado

a[i,n] = A[i,n]

an no insertados

1 2 3 i -1 i n-1 nij1

-a[j,i] ordenado

Invariante:el arreglo a es una permutacin del originala[1,i] sin celda j est ordenado, ya[j,i] tambin est ordenado.



Resumen


Ordenacin por insercinProcedimiento de insercin

{Pre: 0 < i n a = A}proc insert (in/out a: array[1..n] of T, in i: nat)

var j: natj:= i {Inv: Invariante de recin}do j > 1 a[j] < a[j 1] swap(a,j-1,j)

j:= j-1od

end proc{Post: a[1,i] est ordenado a es permutacin de A}



Resumen


Ordenacin por insercinTodo junto

proc insertion_sort (in/out a: array[1..n] of T)for i:= 2 to n do

insert(a,i)od

end proc

proc insert (in/out a: array[1..n] of T, in i: nat)j:= ido j > 1 a[j] < a[j 1] swap(a,j-1,j)

j:= j-1od

end proc



Resumen


Nmero de Comparaciones e intercambiosProcedimiento insert(a,i)

comparaciones intercambiosi mn mx mn mx2 1 1 0 13 1 2 0 24 1 3 0 3...

......

......

n 1 n-1 0 n-1total insertion_sort n - 1 n

2

2 n2 0 n2

2 n2



Resumen


Ordenacin por insercin, casos

mejor caso: arreglo ordenado, n comparaciones y 0intercambios.peor caso: arreglo ordenado al revs, n

2

2 n2comparaciones e intercambios, es decir, del orden de n2.caso promedio: del orden de n2.



Resumen

Resumen

Hemos analizado dos algoritmos de ordenacinordenacin por seleccinordenacin por insercin

la ordenacin por seleccin hace siempre el mismonmero de comparaciones, del orden de n2.la ordenacin por insercin tambin es del orden de n2 enel peor caso (arreglo ordenado al revs) y en el casomedio,la ordenacin por insercin es del orden de n en el mejorcaso (arreglo ordenado),la ordenacin por insercin realiza del orden de n2 swaps(contra n de la ordenacin por seleccin) en el peor caso.



Resumen

Problema del bibliotecario

Con cualquiera de los dos algoritmos la respuesta es 4das,salvo que se trate de una biblioteca ya ordenada o casiordenada, en cuyo caso:

ordenacin por insercin es del orden de n,y por ello la respuesta sera: 2 das.



Resumen

Repaso de la ordenacin por seleccin

proc selection_sort (in/out a: array[1..n] of T)var minp: natfor i:= 1 to n-1 do

minp:= min_pos_from(a,i)swap(a,i,minp)

odend proc

fun min_pos_from (a: array[1..n] of T, i: nat) ret minp: natminp:= ifor j:= i+1 to n do if a[j] < a[minp] then minp:= j fiod

end fun

Se lo puede abreviar omitiendo la funcin auxiliar.Ordenacin Algoritmos y Estructuras de Datos II


Resumen

Forma abreviada de la ordenacin por seleccin

proc selection_sort (in/out a: array[1..n] of T)var minp: natfor i:= 1 to n-1 do

minp:= ifor j:= i+1 to n do

if a[j] < a[minp] then minp:= j fiodswap(a,i,minp)

odend proc



Resumen

Repaso de la ordenacin por insercin


insert(a,i)od

end proc

proc insert (in/out a: array[1..n] of T, in i: nat)j:= ido j > 1 a[j] < a[j 1] swap(a,j-1,j)

j:= j-1od

end proc

Tambin puede abreviarse omitiendo el procedimiento auxiliar.



Resumen

Forma abreviada de la ordenacin por insercin


j:= ido j > 1 a[j] < a[j 1] swap(a,j-1,j)

j:= j-1od

odend proc



Resumen

Demo (www.sorting-algorithms.com)

Ejecucin de ordenacin por seleccinentrada aleatoriacasi ordenadainvertidacon repeticiones

Ejecucin de ordenacin por insercinentrada aleatoriacasi ordenadainvertidacon repeticiones

Comparacin y conclusiones.



Resumen

Reflexin sobre paralelismo

Qu provecho podramos sacar a los algoritmos que hemosvisto si contramos con varios o muchos procesadorescapaces de cooperar entre ellos?


Nmero de operaciones de un comando (funcin ops)Ordenacin por insercinEjemploAlgoritmoAnlisis

Resumen

Documents

ordenacion_insercion