Buscar en el sitio
Contacto
Analisisdisenodealgoritmo
E-mail: miguel-762011@hotmail.com
ALGORITMOS
ALGORITMO DE EFICIENCIAS
función multiplica (X,Y,n) Eficiencia
{
if (P es pequeño) { O(1)
return X*Y; O(1)
} else {
Obtener xi, xd, yi, yd; O(n)
z1 = multiplica (xi, yi, n/2); T(n/2)
z2 = multiplica (xi, yd, n/2); T(n/2)
z3 = multiplica (xd, yi, n/2); T(n/2)
z4 = multiplica (xd, yd, n/2); T(n/2)
aux = suma(z2,z3); O(n)
z1 = desplaza_izq(z1,n); O(n)
aux = desplaza_izq(aux,n/2); O(n)
z = suma(z1,aux); O(n)
z = suma(z,z4); O(n)
return z; O(1)
}
}
ALGORITMOS DE ORDENACIÓN POR INSERCIÓN
PROCEDURE Insercion(VAR a:vector;prim,ult:CARDINAL);
VAR i,j:CARDINAL; x:INTEGER;
BEGIN
FOR i:=prim+1 TO ult DO
x:=a[i]; j:=i-1;
WHILE (j>=prim) AND (x
a[j+1]:=a[j]; DEC(j)
END;
a[j+1]:=x
END
END Insercion;
ALGORITMO DE ORDENACIÓN POR SELECCIÓN
PROCEDURE Seleccion(VAR a:vector;prim,ult:CARDINAL);
VAR i:CARDINAL;
BEGIN
FOR i:=prim TO ult-1 DO
Intercambia(a,i,PosMinimo(a,i,ult))
END
END Seleccion;
ALGORITMO DE ORDENACIÓN BURBUJA
PROCEDURE Burbuja (VAR a:vector;prim,ult:CARDINAL);
VAR i,j:CARDINAL;
BEGIN
FOR i:=prim TO ult-1 DO
FOR j:=ult TO i+1 BY -1 DO
IF (a[j-1]>a[j]) THEN
Intercambia(a,j-1,j)
END
END
END
END Burbuja;
ALGOTMO ORDENACIÓN POR MECLA (MERGESORT)
PROCEDURE Mezcla(VAR a,b:vector;prim,ult:CARDINAL);
(* utiliza el vector b como auxiliar para realizar la mezcla *)
VAR mitad:CARDINAL;
BEGIN
IF prim
mitad:=(prim+ult)DIV 2;
Mezcla(a,b,prim,mitad);
Mezcla(a,b,mitad+1,ult);
Combinar(a,b,prim,mitad,mitad+1,ult)
END
END Mezcla;
ALGORITMO DE ORDENACIÓN MEDIANTE MONTÍCULOS (HEAPSORT)
PROCEDURE Monticulos(VAR a:vector;prim,ult:CARDINAL);
VAR i:CARDINAL;
BEGIN
HacerMonticulo(a,prim,ult);
FOR i:=ult TO prim+1 BY -1 DO
Intercambia(a,prim,i);
Empujar(a,prim,i-1,prim)
END
END Monticulos;
PROCEDURE HacerMonticulo(VAR a:vector;prim,ult:CARDINAL);
(* construye un monticulo a partir de a[prim..ult] *)
VAR i:CARDINAL;
BEGIN
FOR i:=(ult-prim+1)DIV 2 TO 1 BY -1 DO
Empujar(a,prim,ult,prim+i-1)
END
END HacerMonticulo;
PROCEDURE Empujar(VAR a:vector;prim,ult,i:CARDINAL);
(* empuja el elemento en posicion i hasta su posicion final *)
VAR j,k:CARDINAL;
BEGIN
k:=i-prim+1;
REPEAT
j:=k;
IF (2*j<=ult-prim+1) AND (a[2*j+prim-1]>a[k+prim-1]) THEN
k:=2*j
END;
IF (2*j
k:=2*j+1
END;
Intercambia(a,j+prim-1,k+prim-1);
UNTIL j=k
END Empujar;
ALGORITMO DE ORDENACIÓN RÁPIDA DE HOARE (QUICKSORT)
PROCEDURE Quicksort(VAR a:vector;prim,ult:CARDINAL);
VAR l:CARDINAL;
BEGIN
IF prim
l:=Pivote(a,a[prim],prim,ult);
Quicksort(a,prim,l-1);
Quicksort(a,l+1,ult)
END
END Quicksort;
PROCEDURE Pivote(VAR a:vector;p:INTEGER;prim,ult:CARDINAL)
:CARDINAL;
(* permuta los elementos de a[prim..ult] y devuelve una
posicion l tal que prim<=l<=ult, a[i]<=p si prim<=i
a[l]=p, y a[i]>p si l
de a[prim] *)
VAR i,l:CARDINAL;
BEGIN
i:=prim; l:=ult+1;
REPEAT INC(i) UNTIL (a[i]>p) OR (i>=ult);
REPEAT DEC(l) UNTIL (a[l]<=p);
WHILE i
Intercambia(a,i,l);
REPEAT INC(i) UNTIL (a[i]>p);
REPEAT DEC(l) UNTIL (a[l]<=p)
END;
Intercambia(a,prim,l);
RETURN l
END Pivote;
ALGORITMO DE ORDENACIÓN POR INCREMENTOS (SHELLSORT)
PROCEDURE Incrementos(VAR a:vector;prim,ult:CARDINAL);
VAR i,j,h,N:CARDINAL; v:INTEGER;
BEGIN
N:=(ult-prim+1); (* numero de elementos *)
h:=1;
ORDENACION
REPEAT h:=3*h+1 UNTIL h>N; (* construimos la secuencia *)
REPEAT
h:=h DIV 3;
FOR i:=h+1 TO N DO
v:=a[i]; j:=i;
WHILE (j>h) AND (a[j-h+prim-1]>v) DO
a[j+prim-1]:=a[j-h+prim-1];
DEC(j,h)
END;
a[j+prim-1]:=v;
END
UNTIL h=1
END Incrementos;
ALGORITMO DE Ordenación por Cubetas (Binsort)
PROCEDURE Cubetas(VAR a:vector);
VAR i:CARDINAL;
BEGIN
FOR i:=1 TO n DO
WHILE a[i]<>i DO
Intercambia(a,i,a[i])
END
END
END Cubetas;
ALGORITMO DIVIDE Y VENCERAS
PROCEDURE DyV(x:TipoProblema):TipoSolucion;
VAR i,k,:CARDINAL;
s:TipoSolucion;
subproblemas: ARRAY OF TipoProblema;
subsoluciones:ARRAY OF TipoSolucion;
BEGIN
IF EsCasobase(x) THEN
s:=ResuelveCasoBase(x)
ELSE
k:=Divide(x,subproblemas);
FOR i:=1 TO k DO
subsoluciones[i]:=DyV(subproblemas[i])
END;
s:=Combina(subsoluciones)
END;
RETURN s
END DyV;
DESCARGA EL COMTENIDO: