Este es un tema más propio de un curso de algorítmica que de uno de programación en Pascal, pero como la mayoría de los programas tienen que ordenar los datos para conseguir una acceso más rápido y sencillo, voy a comentar dos de los métodos de ordenación más conocidos, uno sencillo y lento, y otro más rápido y difícil de entender: burbuja y QuickSort.
En ellos voy a suponer que la lista de datos es un array, y que queremos ordenar esta lista de menor a mayor. Trabajaré con datos de tipo integer por simplicidad, pero adaptarlo a Strings, Records u otros tipos no tiene mayor dificultad.
Al final comentaré también algo sobre la "búsqueda
binaria", para que se vea a qué me refiero con eso de "acceso
más rapido".
Es posible que este sea el algoritmo más sencillo de escribir, y también el menos eficiente. La idea es sencilla: se van desplazando los números más pequeños hacia atrás hasta su posición correcta (de ahí el nombre de "burbuja": es como si los más ligeros fueran subiendo).
La idea es simplemente ésta:
for i := maximo downto 2 do { De final a principio }
if datos[i] < datos[i-1] then { Si está colocado al revés }
swap(datos[i], datos[i-1]); { Le da la vuelta }
es decir, recorre la lista desde el final hacia el principio, comparando cada elemento con el anterior. Si están colocados al revés (primero el mayor y luego el menor), hay que intercambiarlos.
La rutina de intercambio (swap) sería así:
procedure swap(var a,b: integer); { Intercambia dos datos }
var
tmp: integer;
begin
tmp := a;
a := b;
b := tmp;
end;
Esto coloca el último número de la lista en su posición adecuada. Nos puede servir si añadimos siempre un único elemento, que colocamos al final temporalmente y después llevamos a su posición adecuada.
Pero es muy frecuente que haya más de un dato descolocado, y que además no sepamos cuántos son estos datos que están desordenados. Entonces debemos "mejorar" la idea anterior para colocar todos los números que haga falta.
La primera forma intuitiva sería incluir el "for" anterior dentro de otro "for", para comprobar que todos los números quedan colocados. Esto es sencillo de programar, pero es ineficiente: si sólo hay un número descolocado, pero aun así probamos todos uno por uno, perdemos tiempo inútilmente. La forma sería:
for j := 1 to maximo-1 do
for i := maximo downto j+1 do { De final a principio }
if datos[i] < datos[i-1] then { Si está colocado al revés }
swap(datos[i], datos[i-1]); { Le da la vuelta }
Una forma más rápida para datos que no estén muy desordenados será con un "while" o un "repeat": si damos una pasada a toda la lista sin recolocar ningún número, es que ya están todos colocados, y entonces no tiene sentido seguir mirando. Entonces, nuestra rutina de ordenación quedaría, por ejemplo:
procedure Burbuja; { Ordena según burbuja }
var
cambiado: boolean;
begin
writeln;
writeln('Ordenando mediante burbuja...');
repeat
cambiado := false; { No cambia nada aún }
for i := maximo downto 2 do { De final a principio }
if datos[i] < datos[i-1] then { Si está colocado al revés }
begin
swap(datos[i], datos[i-1]); { Le da la vuelta }
cambiado := true; { Y habrá que seguir mirando }
end;
until not cambiado; { Hasta q nada haya cambiado }
end;
Este algoritmo puede ser útil para datos poco desordenados, en los que añadamos datos al final. Si se trata de datos muy desordenados, resulta lento.
Hay otros bastante parecidos a éste, que van comparando y moviendo
elementos de uno en uno. En cambio, hay otros que se basan en "bloques",
y que suelen ser recursivos, como MergeSort y QuickSort.
Este algoritmo de ordenación es más eficiente que el anterior para datos bastante desordenados. Se basa en aquello tan popular de "divide y vencerás". La idea en sí también es sencilla: partir un problema complicado en trozos que sean más sencillos de resolver uno por uno.
En este caso, se trata de dividir nuestra lista en "sublistas" cada vez más pequeñas (se hará de forma recursiva). Finalmente, volvemos a juntar todas esas listas en una sola.
¿Y cómo las juntamos? Pues miramos el primer elemento de cada una y los vamos cogiendo por orden, hasta reconstruir la lista inicial, pero ya ordenada.
Este algoritmo no voy a desarrollarlo, porque me centraré en QuickSort, que suele ser más rápido. Aun así, voy a poner el pseudo-código, por si alguien quiere implementarlo:
función MERGESORT (a: lista): lista
opcion
|a| = 1: devolver a { Tamaño 1: fin de recursión }
|a| <> 1:
(x1,x2) := DESCOMPONER(a) { Si no, divide en dos trozos }
s1 := MERGESORT (x1) { Aplica recursivamente a los }
s2 := MERGESORT (x2) { dos trozos }
devolver MERGE(s1,s2) { Y finalmente combina en una }
fopc { única lista grande }
ff
En un caso "general", puede que éste sea el algoritmo más rápido (aunque en muchos casos particulares puede no serlo).
Lo que este hace es mirar el valor del centro de la lista. Mueve a su derecha todos los valores menores y a la izquierda todos los mayores, pero no los ordena aún, sino que luego recursivamente vuelve a hacer lo mismo en ambos trozos. Así finalmente queda ordenado.
Más en detalle: dentro de cada uno de esos dos trozos (valores mayores y menores que el del centro), avanza desde su extremo hacia el centro, comprobando qué valores ya están colocados donde les corresponde, y moviendo al lado opuesto los que no lo estén.
Así, la parte recursiva del algoritmo es:
procedure Sort(l, r: Integer); { Esta es la parte recursiva }
var
i, j, x, y: integer;
begin
i := l; j := r; { LÃmites por los lados }
x := datos[(l+r) DIV 2]; { Centro de la comparaciones }
repeat
while datos[i] < x do i := i + 1; { Salta los ya colocados }
while x < datos[j] do j := j - 1; { en ambos lados }
if i <= j then { Si queda alguno sin colocar }
begin
swap(datos[i], datos[j]); { Los cambia de lado }
i := i + 1; j := j - 1; { Y sigue acercándose al centro }
end;
until i > j; { Hasta que lo pasemos }
if l < j then Sort(l, j); { Llamadas recursivas por cada }
if i < r then Sort(i, r); { lado }
end;
Pues con todo esto, vamos a ver ya un programa de ejemplo que use estos
dos métodos para ordenar un array de números enteros:
{--------------------------}
{ Ejemplo en Pascal: }
{ }
{ Ejemplo de ordenacio- }
{ nes: Burbuja y Quick- }
{ sort }
{ ORDENA.PAS }
{ }
{ Este fuente procede de }
{ CUPAS, curso de Pascal }
{ por Nacho Cabanes }
{ }
{ Comprobado con: }
{ - Free Pascal 2.2.0w }
{ - Turbo Pascal 7.0 }
{ - Tmt Pascal Lt 1.01 }
{--------------------------}
program Ordenar;
const
maximo = 100; { Número de datos }
maxVal = 30000; { Maximo valor que pueden tomar }
var
datos: array[1..maximo] of integer; { Los datos en sí }
i: integer; { Para bucles }
procedure swap(var a,b: integer); { Intercambia dos datos }
var
tmp: integer;
begin
tmp := a;
a := b;
b := tmp;
end;
procedure generaNumeros; { Genera números aleatorios }
begin
writeln;
writeln('Generando números...');
for i := 1 to maximo do
datos[i] := random(maxVal);
end;
procedure muestraNumeros; { Muestra los núms almacenados }
begin
writeln;
writeln('Los números son...');
for i := 1 to maximo do
write(datos[i], ' ');
writeln;
end;
procedure Burbuja; { Ordena según burbuja }
var
cambiado: boolean;
begin
writeln;
writeln('Ordenando mediante burbuja...');
repeat
cambiado := false; { No cambia nada aún }
for i := maximo downto 2 do { De final a principio }
if datos[i] < datos[i-1] then { Si está colocado al revés }
begin
swap(datos[i], datos[i-1]); { Le da la vuelta }
cambiado := true; { Y habrá que seguir mirando }
end;
until not cambiado; { Hasta q nada se haya cambiado }
end;
procedure QuickSort; { Ordena según Quicksort }
procedure Sort(l, r: Integer); { Esta es la parte recursiva }
var
i, j, x, y: integer;
begin
i := l; j := r; { Límites por los lados }
x := datos[(l+r) DIV 2]; { Centro de la comparaciones }
repeat
while datos[i] < x do i := i + 1; { Salta los ya colocados }
while x < datos[j] do j := j - 1; { en ambos lados }
if i <= j then { Si queda alguno sin colocar }
begin
swap(datos[i], datos[j]); { Los cambia de lado }
i := i + 1; j := j - 1; { Y sigue acercándose al centro }
end;
until i > j; { Hasta que lo pasemos }
if l < j then Sort(l, j); { Llamadas recursivas por cada }
if i < r then Sort(i, r); { lado }
end;
begin { Esto llama a la parte recursiva }
writeln;
writeln('Ordenando mediante QuickSort...');
Sort(1,Maximo);
end;
{ ------------ Cuerpo del programa ------------- }
begin
randomize;
generaNumeros;
muestraNumeros;
Burbuja;
muestraNumeros;
readln;
generaNumeros;
muestraNumeros;
QuickSort;
muestraNumeros;
readln;
end.
¿Para qué tener los datos ordenados? Pues no sólo para que queden más bonitos en pantalla ;-) Si tenemos 20.000 datos, al hacer una búsqueda nos puede ayudar muchísimo saber que están ordenados.
¿A qué me refiero? Es sencillo: si los datos no están ordenados, para comprobar si un dato ya existe, tendremos que mirar todos. En cambio, si están ordenados sabemos dónde buscar: si queremos saber si "Martínez" está en nuestra agenda (o base de datos, por eso de que ya tiene 20.000 datos y ya es más que una simple agenda ;-) ) iremos directamente a la M. Si llegamos a la N (o incluso a "Mas...") y no ha aparecido, sabemos que no está.
Esto es lo que hacemos en un diccionario, por ejemplo, y esta es la idea de la búsqueda binaria.
Lo de "binario" es porque lo que haremos será siempre mirar el valor que tenemos en el medio. Si nos hemos pasado, vamos hacia la izquierda; si nos hemos quedado cortos, vamos a la derecha. En cualquiera de los dos casos, volvemos a mirar en el medio, y así sucesivamente.
Si al final encontramos el dato, claramente es que estaba, y ya sabemos cual es la ficha que debemos modificar; si nos pasamos no estaba, y tendremos que avisar al usuario, o añadir una nueva ficha. Pero hemos hecho muchas menos comparaciones que mirando una por una. ¿Cuantas menos? Pues como cada vez vamos dividiendo a la mitad el tamaño de la zona a mirar, el número de comparaciones estará muy cerca del logaritmo en base 2 del número de datos que teníamos. Así para nuestra base de datos de 20.000 personas, haremos
log2 (20.000) = 11 aprox. => cerca de 12 comparaciones
La cuenta sale rápido: antes teníamos que hacer 20.000 comparaciones en el peor caso, ó 1 en el mejor caso. Consideremos que como media deberíamos hacer 10.000 comparaciones. Ahora hacemos unas 12 (puede que sea 11, o bien 13 ó 14, según lo "cuidadosos" que seamos programando, pero no más) Por tanto, ahora la búsqueda es 1.000 veces más rápida.
Es decir, si el señor "Martínez" nos dice que ha cambiado su dirección, y queremos apuntarlo en nuestra base de datos, la diferencia es tardar 2 segundos en encontrar su ficha (con búsqueda binaria) o cerca de media hora (2.000 segundos, con búsqueda lineal).
Pero vale ya de rollos y vamos a ver un ejemplo, que cree una lista
de números, la ordene y luego busque un valor en ella:
{--------------------------}
{ Ejemplo en Pascal: }
{ }
{ Búsqueda binaria }
{ BUSCABIN.PAS }
{ }
{ Este fuente procede de }
{ CUPAS, curso de Pascal }
{ por Nacho Cabanes }
{ }
{ Comprobado con: }
{ - Free Pascal 2.2.0w }
{ - Turbo Pascal 7.0 }
{--------------------------}
program BuscaBin; { Búsqueda binaria }
const
maximo = 400; { Número de datos }
maxVal = 500; { Maximo valor que pueden tomar }
var
datos: array[1..maximo] of integer; { Los datos en sí }
i: integer; { Para bucles }
donde: integer; { Posicion en la que ha }
{ aparecido }
procedure swap(var a,b: integer); { Intercambia dos datos }
var
tmp: integer;
begin
tmp := a;
a := b;
b := tmp;
end;
procedure generaNumeros; { Genera números aleatorios }
begin
writeln;
writeln('Generando números...');
for i := 1 to maximo do
datos[i] := random(maxVal);
end;
procedure muestraNumeros; { Muestra los núms. almacenados }
begin
writeln;
writeln('Los números son...');
for i := 1 to maximo do
write(datos[i], ' ');
writeln;
end;
procedure Burbuja; { Ordena según burbuja }
var
cambiado: boolean;
begin
writeln;
writeln('Ordenando mediante burbuja...');
repeat
cambiado := false; { No cambia nada aún }
for i := maximo downto 2 do { De final a principio }
if datos[i] < datos[i-1] then { Si está colocado al revés }
begin
swap(datos[i], datos[i-1]); { Le da la vuelta }
cambiado := true; { Y habrá que seguir mirando }
end;
until not cambiado; { Hasta q nada se haya cambiado }
end;
function Buscar(minimo, maximo, valor: integer): integer;
{ Búsqueda binaria }
var
medio: integer;
begin
writeln('Mirando entre ', minimo, ' y ', maximo,
', de valores ', datos[minimo], ' y ', datos[maximo]);
if minimo >= maximo then { Si la anchura ya es 1 }
if datos[minimo]=valor then { y el valor es el buscado }
buscar := minimo { devolvemos su posición }
else buscar := -1 { Si es otro valor -> no está }
else { Si la anchura no es 1 }
begin
medio := round((minimo+maximo)/2); { Hallamos el centro }
if valor = datos[medio] then { Comparamos con su valor }
buscar := medio { Si acertamos, ya esta }
else if valor > datos[medio] then { Si no, }
buscar := buscar(medio+1,maximo,valor) { Miramos el lado corresp}
else
buscar := buscar(minimo,medio-1,valor)
end;
end;
{ ------------ Cuerpo del programa ------------- }
begin
randomize;
generaNumeros;
Burbuja;
muestraNumeros;
writeln('Buscando ',maxVal div 2,'...');
donde := Buscar(1,maximo, maxVal div 2);
if donde = -1 then writeln('No se ha encontrado')
else writeln('Está en la posición ',donde);
readln;
end.
(Por supuesto, esto es mejorable. Por ejemplo, en un diccionario
no tenemos sólo 2 posibilidades, sino cerca de 25 letras por las
que empezar a buscar, de modo que es más rápido todavía).