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
1.-Importancia del ordenamiento.
2.-Criterio para el análisis de un programa.
3.-Ordenamiento interno.
4.-Ordenamiento externo.
5.-Ordenamiento estable.
6.-Ordenamiento inestable.
7.-Análisis de eficiencia.
8.-Clasificación de los algoritmos de ordenamiento
Se consideran dos factores con respecto a: ¿QUE SE DESEA OPTIMIZAR?
-Espacio de memoria. -Redundancia del tiempo Al momento de tomar esta decisión se debe
investigar con que equipo de trabajo se cuenta (donde se ejecuta el programa), necesidades
del cliente (si debe ser rápido por que se atiende diario muchas personas).
TIPOS DE ORDENAMIENTO
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.
CLASIFICACIÓN DE LOS ALGORITMOS DE ORDENAMIENTO
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
UNIDAD II
ORDENAMIENTO POR INTERCAMBIO
¿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.
ORDENAMIENTO POR EL METODO DE LA BURBUJA
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
METODO DE ALGORITMO DE LA BURBUJA
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
ALGORITMO PAR_ IMPAR_
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;
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
ALGORITMO QUICT SORT
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
QUIT SORT
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
UNIDAD III
ORDENAMIENTOS POR SELECCION
ALGORITMO DE ORDENAMIENTO POR SELECCIÓN DIRECTA
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;
ANALIS DEL ORDENAMIENTO DE SELECCIÓN DIRECTA
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
ALGORITMO DE ORDENAMIENTO HEAPSORT
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;
METODO DE ORDENAMIENTO HEAPSORT
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.
REGRESAR A LA UNIDAD III
UNIDAD IV
ALGORITMO DE ORDENAMIENTO POR INSERCIÓN DIRECTA
PROCEDURE INSERCIÓNd;
Var
A,I,J:INTEGER;
Begin
For I:=2 to n do
Begin
A:=x[I];
x[0]:=A;
J:=i;
While (A < x[J-1]) do
Begin
x[J]:=x[J-1];
Dec (J);
End;
x[J]:=A;
End;
End;
METODO DE ORDENAMIENTO POR INSERCIÓN DIRECTA
En este método si el arreglo inicial está ordenado se hace una compa-
ración en cada paso. Si los elementos están ordenados en sentido inverso la
relación es O(n)². Este algoritmo funciona mejor mientras el arreglo se en-
cuentra más cerca del ordenamiento, se recomienda para valores de n pequeños.
El número de comparaciones cuando el arreglo está ordenado es n-1 y cuando
está desordenado es (n-1)*(n/2).
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
ALGORITMO DE ORDENAMIENTO SHELL
Procedure Shell;
Var
Aux,interv,i,j,k: integer;
Begin
interv:=n div 2;
While (interv > 0) do
Begin
For i:=interv+1 to n do
Begin
J:=i-interv;
While (j > 0) do
Begin
n:=j+interv;
if (x[j] < =x[k]) then
j:=0;
else
Begin
aux:=x[j];
x[j]:=x[k];
x[k]:=aux;
End;
j:=j-interv;
End;
End;
interv:=interv div 2;
End;
End;
<=x[k]) then j:="0;" else Begin aux:="x[j];" x[j]:="x[k];" x[k]:="aux;" End; j:="j-interv;" End; End; interv:="interv" div 2; End; End;
FUNCIONAMIENTO DEL METODO DE ORDENAMIENTO SHELL
En este método, los intervalos se calculan durante el ordenamiento ha-
ciendo una división de dos sub-arreglos del arreglo original y se clasifican
cada grupo por separado,es decir se comparan las parejas de elementos de cada
sección y si no están ordenadas se intercambian. La siguiente interacción es
cuando cada arreglo obtenido se vuelve a dividir entre dos y se comparan los
elementos de la misma manera, sucesivamente hasta que los intervalos sean=0.
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
ALGORITMO DE ORDENAMIENTO POR EL METODO DE CONTEO
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
ALGORITMO DE ORDENAMIENTO POR CONCATENACIÓN MERGE
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;
ALGORITMO DE ORDENAMIENTO DE CONCADIR
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
ALGORITMO DE ORDENAMIENTO POR CALCULO DE DIRECCIONES
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
