Juan Camilo Muñoz Castelblanco.
257120
Ejercicios del libro de Cormen cápitulo 2
2.1–2 Insertion sort
para ordenamiento decreciente
INSERTION-SORT(A)
1 for j . 2 to length[A]
2 do key
. A[j]
3 . Insert A[j] into the sorted sequence A[1 _ j - 1].
4 i . j - 1
5 while i > 0 and A[i] < key
6 do A[i + 1] . A[i]
7 i . i - 1
8 A[i + 1] . key
En la línea 5 se cambia la
instrucción por esta (while A[i] > key to A[i] < key), esto
hace que se ordene el arreglo A de forma decreciente
2.1-3
Algorithm
1 LINEAR-SEARCH(A; v)
Input:
A = a1; a2;… ;v; an;
Output:
An
index i such that v = A[i] or nil if v isn’t in A
for i = 1 to n do
if A[i] = v then
k=i
end if
end for
if(k>n) then
return nil
else
return k
end if
Invariante de
ciclo ( i=i+1, (if
A[i]=v ==>
k=i))
Inicialización: para la iteración 0 se
tiene que i=i+0, lo cual, se cumple, además que se posiciona a A en un lugar invalido.
Mantenimiento: Como la única condición
de terminación es que i vaya hasta n, i va a estar incrementándose en una
unidad hasta que llegue al valor n.
Finalización: La única condición de terminación
es que i vaya hasta n, i nunca se modifica, entonces va a estar incrementándose
hasta llegar a n
2.2-1 Expresar la siguiente expresión en términos de complejidad exacta
F(n) = n3/1000 - 100n2 - 100n + 3
F(n) pertenece a O(n3)
en notación asindotica exacta.
2.3-5 Algoritmo recursivo para búsqueda binaria, donde su complejidad
en el peor caso es de log2n
Algorithm
BINARY-SEARCH(A; v; p; r)
Input:
A
sorted array A and a value v.
Output:
An
index i such that v = A[i] or nil.
if p >= r and v != A[p] then
return nil
end if
j = A[floor((r - p)/2)]
if v = A[j] then
return j
else
if v < A[j] then
return BINARY-SEARCH(A; v; p; j)
else
return BINARY-SEARCH(A; v; j; r)
end if
end if
Problemas del libro de Cormen cápitulo 2
2.3-5 Correctitud
de Bubble sort
BUBBLESORT(A)
1 for i = 1 to length[A] do
2 for j = length[A] down to i + 1 do
3 if A[j] < A[j - 1]
4 then exchange A[j] . A[j - 1]
5 end if
6 end for
7 end for
Tenemos A=a1;a2;……………..an; y i=k ,
j>i
Para el elemento k del arreglo A, el siguiente
segmento de código, halla el menor valor entre todos los elementos de A que son
mayores a k y lo coloca en la posición k,
2 for j = length[A] down to i + 1 do
3 if A[j] < A[j - 1]
4 then exchange A[j] . A[j - 1]
5 end if
6 end for
Es decir, que el primer for
lo que hace es recorrer el arreglo desde su primera posición hasta el final del
arreglo,
1 for i = 1 to length[A] do
6 end for
de esto se obtiene que
para i=1, en la posición 1, se encontrará el menor valor de A, para i=2, en la posición 2, se encontrará el
menor valor de A pero sin el primer elemento, así sucesivamente, hasta llegar
al tope del arreglo, en donde ya se encuentra ordenado. Esto se da por el
concepto de que el primero es el menor de todos los elementos, el segundo es el
menor de todos los elementos menos el primero y así sucesivamente.