TUTORIAL DE ALGORITMOS COMPUTACIONALES II ELABORADO POR LOS ALUMNOS: SERGIO ANTONIO BOJORQUEZ ESCAMILLA GILBERTO AARON ROJO FIGUEROA MIGUEL ANGEL VILLA BURGOS
Nota: La informaciòn contenida en éstos tutores puede tener errores ortográficos y de otro tipo. Por favor cheque y confirme de otras fuentes.
UNIDAD I.- INTRODUCCIÓN UNIDAD II.- ORDENAMINETOS POR INTERCAMBIO UNIDAD III.- ORDENAMIENTOS POR SELECCIÓN UNIDAD IV.- ORDENAMIENTOS POR INSERCIÓN UNIDAD V.- ORDENAMIENTOS POR DISTRIBUCIÓN UNIDAD VI.- ORDENAMIENTOS POR INTERCALACIÓN UNIDAD VII.- ORDENAMIENTOS POR CALCULO DE DIRECCIONES
UNIDAD I: INTRODUCCIÓN.- CONTENIDO
INTERNO.-Es el tipo de ordenamiento en el cual los datos a ordenar están localizados en la memoria principal dela memoria principal de la computadora. EXTERNO.- Existe cuando los datos a ordenar están localizados en algún dispo- sitivo externo. ESTABLE.- Es posible que existan dos registros en un archivo, y que contenga la mísma llave. Un algoritmo de ordenamiento se dice que es estable si el or- den original de los registros con llaves iguales es el mismo después del or- denamiento. Es decir tenemos dos registros i, j, y las llaves de k[i] y k[j] es la misma; si el registro de r[i] precede a r[j] en el archivo original, igual deberá suceder en el archivo ordenado. INESTABLE.-Un algoritmo de ordenamiento es inestable si el orden original de las llaves (del ejemplo anterior), si cambian al ordenarlos.
INTERNOS.- Son ejecutados en la memoria principal de la computadora. EXTERNOS.- Son ejecutados en un medio auxiliar, o de almacenamiento secundario. REGRESAR A LAS UNIDADES
¿En que consiste el algoritmo de la burbuja? La idea básica del ordenamiento de la burbuja es: el que pasa por un archi vo en forma secuencial varias veces. Cada paso consiste en comparar un elemen to del archivo con su sucesor (x[j] con x[j+i]), e intercambiar los dos ele- mentos si no están en el orden apropiado. El algoritmo utiliza una bandera bo- oleana que cambia cuando se realiza algún intercambio, y permanece sin cam- bio cuando no cambia ningún valor, pudiendo así truncar el ciclo y terminar el proceso de ordenamiento. Este algoritmo es de fácil comprensión y programación pero es de los menos eficientes puesto que existen n-1 pasos y n-i comprobaciones en cada paso. En el peor de los casos cuando los elementos estan invertidos, el Num. máximo de revisiones es n-1 y el Num. de intercambios o comparaciones esta dado por (n-1) * (n-1)=n²-2n+1. En el mejor de los casos cuando los elementos estan en orden el No. de re- visiones es mínimo 1 y el ciclo de comparaciones es n-1. Hablando de unidades de tiempo el algoritmo de la burbuja es o(n) en el mejor de los casos y o(n²) en el peor de los casos.
Procedure burbuja; var aux:integer; b:boolean; i,j:byte; Begin b:=true; i:=1; while (i<=n-1) and (b) do begin b:=false; <=n-1) and (b) do Begin b:="false" for j.="1" to n-1 do Begin if (x[j]> for j:=1 to n-1 do begin if (x[j]>[j+1]) then Begin b:=true; aux==x[j]; x[j]=x[j+1]; x[j+1]=aux; End; End; inc (i); End; End; 1 [20] 10 10 2 [10] 20 20 3 [40] 40 30 4 [30] 30 40 n=4 (n-1=3) b=t,f,t,t,f i=1,2,3 j=1,2,3 x=2,3 aux=20,40
Este algoritmo es de fácil comprensión pero es de los menos eficientes puesto que existen n-1 pasos y n-i comparaciones de cada paso. El numero de comparaciones se refleja en la tabla que se mostrará posteriormente. Una característica de este ordenamiento es que es de facil comprensión y programación, la unica ventaja es que requiere poco espacio adicional (una posición de memoria para retener el valor para intercambio). Este método tiene la desventaja de utilizar en excesivo tiempo de ordenamiento por el numero de comparaciones que realiza. REGRESAR A LA UNIDAD II
Procedure par_impar; var:r,i,j,aux:integer; Begin r:=(n+1)/2; for j:= 1 to r do Begin i:=1; while (i<n)do begin if (x[i]>[i+1] then Begin aux:=x[i]; x[i]:=x[i+1]; x[i+1]:=aux; inc (i,2); End Else inc (i,2); end; i:=2; while (i<n)do begin aux:=x[i]; x[i]:=x[i+1]; x[i+1]:=aux; inc(i,2); end else inc(i,2); end; end; end;
1 [40] 30 30 30 10 10 10 10 2 [30] 40 10 10 30 30 30 20 3 [10] 10 40 40 40 20 20 30 4 [60] 60 60 20 20 40 40 40 5 [20] 20 20 60 60 60 50 50 6 [50] 50 50 50 50 50 50 60 n=6 r=3 j=1,2,3. i=1,3,5,7,2,4,6,1,3,5,7,2,4,6,1,3,5,7,2,4,6. aux=40,40,60,30,40,60,30. REGRESAR A LA UNIDAD II
Procedure shakersort; var aux,k,i,r,j: integer; Begin i:=2; r:=n; k:=n; repeat for j:=r downto i do Begin if x[j-1] > x[j] then Begin aux:=x[j-1]; x[j-1]:=x[j]; x[j]:=aux; k:=j; End; End; i:=k+1; for j:=i to r do Begin if x[j-1] > x[j] then Begin aux:=x[j-1]; x[j-1]:=x[j]; x[j]:=aux; k:=j; End; End; r:=k-1; until(i > r); End; 1 [38] 38 12 12 2 [12] 12 38 23 3 [56] 23 23 38 4 [23] 56 56 56 I=2,3 R=4,2 K=4,2,3 J=4,3,2,3,4 AUX=56,38,38 REGRESAR A LA UNIDAD II
PROCEDURE QUICK SORT;
VAR
X:Array[1..N] Of Integer;
Procedure quik (Li, Ls:integer);
Var
I:=integer;
Procedure rangos (Li,Ls:integer :var J:integer);
Var
Ar,Ab,A:integer;
Begin
A:=x[Li];
J:=Li;
Ar:=Ls;
Ab:=Li;
Repeat
While (Ar > Ab) And (x[Ar] > = A) do
Begin
Dec (Ar);
End;
J:=Ar;
If (Ar <> Ab) then
Begin
x[Ab]:=x[Ar];
While (Ab < Ar) And (x[Ab] < = A) do
Begin
Inc (Ab);
End;
J:=Ab;
If Ab <> Ar then
Begin
x[Ar]:=x[Ab];
End;
End;
Until (Ab=Ar);
x[J]:=A;
End;
Begin
If (Li < Ls) then
Begin
Rangos (Li,Ls,J);
Quick (Li,J-1);
Quick (J+1,Ls);
End;
End;
Begin
Quick (1,n);
End;
FUNCIONAMIENTO DEL ORDENAMIENTO RAPIDO
La manera de realizar este ordenamiento es la siguiente: La instrucción A:=X[i] de l procedimiento rango es el elemento del que se quiere encontrar su posición. Para esto se inicializ dos apuntadores Ar (Arriba) y Ab(Abajo),como los limites inferior y superior del arreglo. En cualquier punto durante la ejecución cada elemento delante del apuntador Ar es mayor o igual que A y cada elemento detrás del apuntador Ab es menor o igual que A. Los apuntadores Ar Y Ab se mueven en forma alterna el uno hacia el otro. Ar de uno en uno hasta que x[Ar] sea menor que A. En ese momento x[Ar] y x[Ab], se intercambian. El algoritmo continua en la dirección opuesta, y se incrementa el apuntador Ab hasta que x[Ab]>A, cuando esta sucede x[Ab] y x[Ar] intercambian valores y se continua en la dirección opuesta; después de este intercambio [Ab]=A. REGRESAR A LA UNIDAD II
PROCEDURE SELECCIÓND; Var I,J,Idx,Gde:integer; Begin For I:=n downto 2 do Begin Gde:=x[1]; Idx:=1; For J:=2 to I do Begin If (x[J] > Gde) then Begin Gde:=x[J]; Idx:=J; End; End; x[Idx]:=x[I]; x[I]:=Gde; End; End;
En el primer paso del ordenamiento se efectuan n-1 comparaciones, en el segundo n-2 comparaciones, y así sucesivamente. El total de comparaciones aproximadas, esta dado por n(n-1)/2. La relación de ordenamiento es O(n)²; para cualquier estado inicial de los elementos del arreglo. Este método se le conoce por el nombre de: "EMPUJE HACIA ABAJO", y es recomendable para un número pequeño de elementos. REGRESAR A LA UNIDAD III
procedure heap_sort; Label 10,11 Var I,J,K,Y:Integer; Begin For K:=2 to n do Begin I:=K; Y:=X[K]; J:=I/2; While (J > 0) do Begin If Y < =x[J] then Goto 10; x[I]:=x[J]; I:=J; J:=I/2; End; 10: x[I]:=Y End; For k:=n downto 2 do Begin Y:=X[K]; x[K]:=x[1]; I:=1; J:=2; If (x[3] > x[2]) And (K-1 > =3) then J:=3; While (J < =K-1) do Begin If x[J] < =Y do Goto 11; x[I]:=x[J]; I:=J; J:=2*I; If x[J-1] > x[J] then Inc (J); End; 11:x[I]:=Y; End; End;
A éste método también se le llama ordenamiento de grupo, y consiste en que en el primer ciclo o primera parte del procedimiento se crea un desplazamiento de los elementos, obteniendo una estructura en la cual x[1] es el elemento mayor del arreglo. Si se presenta este arreglo resultante como un arbol se observa que cada elemento es el padre de los elementos z[i] z[i+1] puesto que es una estructura con un grupo en el cual j es <= A i/2. En la segunda parte del procedimiento se efectua el proceso de ordenamiento en el cual se recorre el arbol de tal forma que el resultado es una lista ordenada de elementos. Este método funciona solamente cuando el valor de A sea mayor i igual que 3 entre a mayor será su eficiencia.
Procedure Inserción_binaria
Var
a,i,j,m,l,r:integer;
Begin
For i:=2 to n do
Begin
a:=x[i];
i:=1;
r:=i;
while (l < r) do
Begin
m:=(l+r) div 2;
if(x[m] < a) then
l:=m+1;
else
r:=m;
End;
For j:=i downto r+1 do
Begin
x[j]:=x[j-1];
End;
x[r]:=a;
End;
End;
METODO DE ORDENAMIENTO POR INSERCIÓN_BINARIA Este algoritmo es similar al anterior, realiza el mismo número de pasos, toma la misma variable auxiliar ´A´ e inicializa 2 variables 1 y r. El ordenamiento se lleva a cabo de la siguiente manera: Saca mitad de l y r, compara el contenido de la mitad con el valor de "A" si es más grande, hace más grande el limite superior de lo contrario, hace más grande el limite inferior. Este proceso se realiza mientras el limite inferior sea menor que el superior, después se realiza un ciclo decrementado donde los números mayores se ban bajando, y por ultimo se asignan el valor de "A", al contenido del rengo "R". REGRESAR A LA UNIDAD IV
Procedure b_Radix; const m=1; Type tipo_nodo=record; info,next:integer; End; Var nodo: array[1...n] of tipo_nodo; fte: array[0...10] of integer; at: array[0...9] of integer; p,prim,q,i,j,y,exp,k: integer; Begin For i:=1 to n-1 do Begin nodo[i].info:=x[i]; nodo[i].next:=i+1; Eng; nodo[n].info:=x[n]; nodo[n].next:=0; prim:=1; For k:=1 to m do Begin For i:=0 to n do At[i]:=0; For i:=0 to 10 do fte[i]:=0; While(prim <> 0) do Begin p:=prim; prim:=nodo[prim].next; y:=nodo[p].info; exp:=1; For i:=1 to k-1 do exp:=exp*10; j:=(y div exp) mod 10; q:=at[j]; if q=0 then fte[j]:=p else nodo[q].next:=p; at[j]:=p; End; j:=0; while (j < = 9) And (fte[j]=0) do inc(j); prim:=fte[j]; while (j < = 9) do Begin i:=j+1; While (i < = 9) And (fte[i]:=0) do inc(i); if (i<=9) then Begin p:=i; nodo[at[j]].next:=fte[i]; End; j:=i; End; nodo[at[p]].next:=0; End; for i:=1 to n do Begin X[i]:=nodo[prim].info; prim:=nodo[prim].next; End; End;
<= 9) And (fte[j]:="0)" do inc(j); prim:="fte[j];" while (j <="9)" do Begin i:="j+1;" While (i <="9)" And (fte[i]:="0)" do inc(i); if (i<="9)" then Begin p:="i;" nodo[at[j]].next:="fte[i];" End; j:="i;" End; nodo[at[p]].next:="0;" End; for i:="1" to n do Begin X[i]:="nodo[prim].info;" prim:="nodo[prim].next;" End; End;METODO DE ORDENAMIENTO BASE RADIX
Este algoritmo está basado en los valores reales de los dígitos de acuerdo a la posición que ocupan los números que son ordnados. Para cada dígito de las cifras a ordenar se efectúan los siguientes pasos, comenzando con el dígito menos significativo y terminando con el dígito más significativo- . Se toma cada número en el orden original y se coloca en una de las 10 colas dependiendo del valor del dígito que se esté procesando, después comenzando con la cola de los números con dígitos 0 y terminando con los de dígito 9 se regresan al arreglo original. Cuando se efectúa este proceso para cada dígito al arreglo está ordenado. M es el número de dígitos que forman las cifras a ordenar. REGRESAR A LA UNIDAD V
Procedure conteo; Var s: array[1...n] of integer; p,i,j: integer; Begin For i:=1 to n do Begin p:=1; For j:=1 to n d begin if x[i] > x[j] then inc(p); end; s[p]:=x[i]; End; End; 1 [20] [1] 2 [15] [8] 3 [8] [15] 4 [1] [20] i=1,2,3,4 p=1,2,3,4 |1,2,3,4| |1,2,3 | |1,2 | |1 | j=1,2,3,4 |1,2,3,4| |1,2,3,4| |1,2,3,4| REGRESAR A LA UNIDAD V
Procedure Merge; Var apa,apb,apc: integer; Begin if (an+bn) > cn then write ("ERROR") else Begin apa:=1; apb:=1; apc:=1; while (apa < = an) And (apb < = bn) do Begin if a[apa] < b[apb] then Begin c[apc]:=a[apa]; inc(apa); End; else Begin c[apc]:=b[apb]; inc(apb); End; inc(apc); End; while apa < = an do Begin c[apc]:=a[apa]; inc(apa); inc(apc); End; While apb < = bn Begin c[apc]:=b[apb]; inc(apb); inc(apc); End; End; End;
Procedure concadir; Var aux: array [1...n] of integer; linf1,linf2,lsup1,lsup2,i,j,k,tam: integer; Begin tam:=1; while (tam < n) do Begin lsup1:=1; k:=1; while (lsup1+tam) < =n do Begin lsup2:=lsup1+tam; linf1:=lsup2-1; if (lsup2+(tam-1) > n) then linf2:=n else linf2:=lsup2+tam-1; i:=lsup1; j:=lsup2; while (i < =linf1) And (j < =linf2) do Begin if x[i]< =x[j] then Begin aux[k]:=x[i]; inc(i); End; else Begin aux[k]:=x[j] inc(j); End; inc(k); End; while (i < =linf1) do Begin aux[k]:=x[i]; inc(i); inc(k); End; lsup1:=linf2+1; end; i:=lsup1; while (k < =n) do Begin aux[k]:=x[i]; inc(k); inc(i); End; For k:=1 to n do x[k]:=aux[k]; tam:=tam*2; End; End; UNIDAD VII
Procedure hash; type tipo.nodo=record; next,info: integer; End; Var nodo:array [1...n] of tipo.nodo f: array [o...9] of integer p,prim,q,i,j,avail,y:integer; Begin for i:=1 to n-1 do Begin nodo[i].info:=x[i]; nodo[1].next:=i+1; End; nodo[n].info:=x[n]; nodo[n].next:=0; for i:=0 to 9 do f[i]:=0; for i:=1 to n do Begin Y:=x[i]; prim:=y div 10; insert_lista (f(prim),y); End; i:=0; for j:=0 to n do Begin p:=f[j]; while p <> 0 do Begin i:=i+1; x[i]:=nodo[p].info; p:=nodo[p].next; End; End; End; 1 [56] j=-->0 [0]=0 2 [28] 1 [1]=0->[14|] 3 [32] 2 [2]=0->[28|] 4 [14] 3 [3]=0->[32|] 5 [51] 4 [4]=0 5 [5]=0->[51|]-->[56|]-¬ 6 [6]=0 7 [7]=0 8 [8]=0 9 [9]=0 nodo info next [56 | 2 ] 1=1 [14] [28 | 3 ] 2 [28] [32 | 4 ] 3 [32] [14 | 5 ] 4 [51] [51 | 0 ] 5 [56] i=1,2,3,4,5 y=56,28,32,14,51 prim=5,2,3,1,5 p=0,4,0,2,0,3,0,0,5,1,0,0,0,0,0 REGRESAR AL principio