Su finalidad es organizar ciertos datos (normalmente arrays o
ficheros) en un orden creciente o decreciente mediante una regla prefijada
(numérica, alfabética...). Atendiendo al tipo de elemento que se
quiera ordenar puede ser:
- Ordenación interna: Los datos se encuentran en memoria
(ya sean arrays, listas, etc) y son de acceso aleatorio o directo (se puede
acceder a un determinado campo sin pasar por los anteriores).
- Ordenación externa: Los datos están en un dispositivo
de almacenamiento externo (ficheros) y su ordenación es más lenta
que la interna.
Los métodos de ordenación interna se aplican
principalmente a arrays unidimensionales. Los principales algoritmos de ordenación
interna son:
Selección: Este método consiste en buscar el elemento
más pequeño del array y ponerlo en primera posición; luego, entre
los restantes, se busca el elemento más pequeño y se coloca en segudo
lugar, y así sucesivamente hasta colocar el último elemento. Por ejemplo,
si tenemos el array {40,21,4,9,10,35}, los pasos a seguir son:
{4,21,40,9,10,35} <-- Se coloca el 4, el más
pequeño, en primera posición : se cambia el 4 por el 40.
{4,9,40,21,10,35} <-- Se coloca el 9, en segunda posición: se cambia el 9 por el 21.
{4,9,10,21,40,35} <-- Se coloca el 10, en tercera posición: se cambia el 10 por el 40.
{4,9,10,21,40,35} <-- Se coloca el 21, en tercera posición: ya está colocado.
{4,9,10,21,35,40} <-- Se coloca el 35, en tercera posición: se cambia el 35 por el 40.
Si el array tiene N elementos, el número de comprobaciones
que hay que hacer es de N*(N-1)/2, luego el tiempo de ejecución está
en O(n2)
var
lista: array[1..N] of byte;
aux, i, j, menor: byte;
BEGIN
for i:= 1 to N-1 do
begin
menor:= i;
for j:= i+1 to N do
if (lista [j+1]<lista[j]) then
begin
if (lista[j]<lista[menor]) then {si el elemento j es menor que el menor}
menor:=j; {pasa a ser el menor}
aux:= lista[i]; {se intercambian los elemento}
lista[i]:=lista[menor]; {de las posiciones i y menor}
lista[menor]:=aux; {usando la variable auxiliar}
end;
end;
END.
Burbuja: Consiste en comparar pares de elementos adyacentes e
intercambiarlos entre sí hasta que estén todos ordenados. Con el array
anterior, {40,21,4,9,10,35}:
Primera pasada:
{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.
Segunda pasada:
{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.
{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.
Ya están ordenados, pero para comprobarlo habría que acabar
esta segunda comprobación y hacer una tercera.
Si el array tiene N elementos, para estar seguro de que el
array está ordenado, hay que hacer N-1 pasadas, por lo que habría
que hacer (N-1)*(N-i-1) comparaciones, para cada i desde 1 hasta N-1. El número
de comparaciones es, por tanto, N(N-1)/2, lo que nos deja un tiempo de ejecución,
al igual que en la selección, en O(n2).
var
lista: array[1..N] of byte;
aux, i, j: byte;
BEGIN
{Dar valores a los elementos del array}
for i:= 1 to N do
for j:= 1 to N-i do
if (lista [j+1]<lista[j]) then
begin
aux:= lista[j+1];
lista[j+1]:=lista[j];
lista[j]:=aux;
end;
END.
Inserción directa: En este método lo que
se hace es tener una sublista ordenada de elementos del array e ir insertando
el resto en el lugar adecuado para que la sublista no pierda el orden. La
sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista
entera queda ordenada. Para el ejemplo {40,21,4,9,10,35}, se tiene:
{40,21,4,9,10,35} <-- La primera sublista ordenada es {40}.
Insertamos el 21:
{40,40,4,9,10,35} <-- aux=21;
{21,40,4,9,10,35} <-- Ahora la sublista ordenada es {21,40}.
Insertamos el 4:
{21,40,40,9,10,35} <-- aux=4;
{21,21,40,9,10,35} <-- aux=4;
{4,21,40,9,10,35} <-- Ahora la sublista ordenada es {4,21,40}.
Insertamos el 9:
{4,21,40,40,10,35} <-- aux=9;
{4,21,21,40,10,35} <-- aux=9;
{4,9,21,40,10,35} <-- Ahora la sublista ordenada es {4,9,21,40}.
Insertamos el 10:
{4,9,21,40,40,35} <-- aux=10;
{4,9,21,21,40,35} <-- aux=10;
{4,9,10,21,40,35} <-- Ahora la sublista ordenada es {4,9,10,21,40}.
Y por último insertamos el 35:
{4,9,10,21,40,40} <-- aux=35;
{4,9,10,21,35,40} <-- El array está ordenado.
En el peor de los casos, el número de comparaciones
que hay que realizar es de N*(N+1)/2-1, lo que nos deja un tiempo de ejecución
en O(n2). En el mejor caso (cuando la lista ya estaba ordenada),
el número de comparaciones es N-2. Todas ellas son falsas, con lo que
no se produce ningún intercambio. El tiempo de ejecución está
en O(n).
El caso medio dependerá de cómo están
inicialmente distribuidos los elementos. Vemos que cuanto más ordenada
esté inicialmente más se acerca a O(n) y cuanto más desordenada,
más se acerca a O(n2).
El peor caso es igual que en los métodos de burbuja
y selección, pero el mejor caso es lineal, algo que no ocurría
en éstos, con lo que para ciertas entradas podemos tener ahorros en
tiempo de ejecución.
var
lista: array[1..N] of byte;
i, j, aux: byte;
encontrado: boolean;
BEGIN
{Dar valores a los elementos del array}
for i:= 2 to N do
begin
aux:= lista[i]; {se intenta añadir el elemento i}
encontrado:=false;
j:=i-1;
while not(encontrado) and (j>=1) do {se recorre la sublista de atras a adelante
para buscar la nueva posicion del elemento i}
begin
if (aux>lista[j]) then {si se encuentra la posición}
begin
lista[j+1]:=aux; {se coloca}
encontrado:=true; {y se sale del bucle para colocar el siguiente número}
end
else {si no, se sigue buscando}
begin
lista[j+1]:=lista[j];
dec(j);
end;
end;
if (j=0) then lista[1]:= aux; {si se han mirado todas las posiciones y no se ha
encontrado, es que es la primera posicion}
end;
END.
Inserción binaria: Es el mismo método
que la inserción directa, excepto que la búsqueda del orden
de un elemento en la sublista ordenada se realiza mediante una búsqueda
binaria (ver algoritmos de búsqueda), lo
que en principio supone un ahorro de tiempo. No obstante, dado que para la
inserción sigue siendo necesario un desplazamiento de los elementos,
el ahorro, en la mayoría de los casos, no se produce, si bien hay compiladores
que realizan optimizaciones que lo hacen ligeramente más rápido.
Shell: Es una mejora del método de inserción directa, utilizado
cuando el array tiene un gran número de elementos. En este método no se compara a cada
elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto
número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial
es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta
que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la
mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así
sucesivamente hasta que el salto vale 1.
Por ejemplo, lo pasos para ordenar el array {40,21,4,9,10,35} mediante el
método de Shell serían:
Salto=3:
Primera pasada:
{9,21,4,40,10,35} <-- se intercambian el 40 y el 9.
{9,10,4,40,21,35} <-- se intercambian el 21 y el 10.
Salto=1:
Primera pasada:
{9,4,10,40,21,35} <-- se intercambian el 10 y el 4.
{9,4,10,21,40,35} <-- se intercambian el 40 y el 21.
{9,4,10,21,35,40} <-- se intercambian el 35 y el 40.
Segunda pasada:
{4,9,10,21,35,40} <-- se intercambian el 4 y el 9.
Con sólo 6 intercambios se ha ordenado el array, cuando
por inserción se necesitaban muchos más.
var
lista: array[1..N] of byte;
aux, i, salto, cambios: byte;
BEGIN
salto:= N div 2;
while not(salto=0) do {el salto va desde N/2 hasta 1}
begin
cambios:=1;
while not(cambios=0) do {mientras se intercambien elementos}
begin
cambios:=0;
for i:= (salto+1) to N do {se pasa una vez}
begin
if (lista[i-salto]>lista[i]) then {y se reordenan si no lo estan}
begin
aux:=lista[i];
lista[i]:=lista[i-salto];
lista[i-salto]:=aux;
inc(cambios);
end;
end;
end;
salto:= salto div 2;
end;
END.
Ordenación rápida (quicksort): Este método se basa en la táctica
"divide y vencerás" (ver sección divide y vencerás), que consiste en
ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se
toma un valor del array como pivote, y se mueven todos los elementos menores que este
pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo
método a cada una de las dos partes en las que queda dividido el array.
Normalmente se toma como pivote el primer elemento de array, y se realizan dos
búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha
a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se
intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.Por
ejemplo, para dividir el array {21,40,4,9,10,35}, los pasos serían:
{21,40,4,9,10,35} <-- se toma como pivote el 21.
La búsqueda de izquierda a derecha encuantra el valor 40, mayor que pivote, y la búsqueda de
derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian:
{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el
valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote
en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:
{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4}
y el {40,35}, y se repetiría el mismo proceso.
Intercalación: no es propiamente un método
de ordenación, consiste en la unión de dos arrays ordenados
de modo que la unión esté también ordenada. Para ello,
basta con recorrer los arrays de izquierda a derecha e ir cogiendo el menor
de los dos elementos, de forma que sólo aumenta el contador del array
del que sale el elemento siguiente para el array-suma. Si quisiéramos
sumar los arrays {1,2,4} y {3,5,6}, los pasos serían:
Inicialmente: i1=0, i2=0, is=0.
Primer elemento: mínimo entre 1 y 3 = 1. Suma={1}. i1=1, i2=0, is=1.
Segundo elemento: mínimo entre 2 y 3 = 2. Suma={1,2}. i1=2, i2=0, is=2.
Tercer elemento: mínimo entre 4 y 3 = 3. Suma={1,2,3}. i1=2, i2=1, is=3.
Cuarto elemento: mínimo entre 4 y 5 = 4. Suma={1,2,3,4}. i1=3, i2=1, is=4.
Como no quedan elementos del primer array, basta con poner los elementos que quedan del
segundo array en la suma:
Suma={1,2,3,4}+{5,6}={1,2,3,4,5,6}
var
i1,i2,is: byte;
lista1: array[1..N1] of byte;
lista2: array[1..N2] of byte;
suma: array[1..N1+N2] of byte;
BEGIN
i1:=1;
i2:=1;
is:=1;
while (i1<=N1) and (i2<=N2) do
begin
if (lista1[i1]<lista2[i2]) then
begin
suma[is]:=lista1[i1];
inc(i1);
end
else
begin
suma[is]:=lista2[i2];
inc(i2);
end;
inc(is);
end;
if (i1<N1) then {se termina de añadir el array que no haya llegado al final}
for i:=i1 to N1 do
begin
suma[is]:=lista1[i];
inc(is);
end
else
begin
for i:=i2 to N2 do
begin
suma[is]:=lista2[i];
inc(is);
end;
end;
END.
Fusión: Consta de dos partes, una parte de intercalación
de listas y otra de divide y vencerás.
- Primera parte: ¿Cómo intercalar dos listas
ordenadas en una sola lista ordenada de forma eficiente?
Suponemos que se tienen estas dos
listas de enteros ordenadas ascendentemente:
lista 1: 1 -> 3 -> 5
-> 6 -> 8 -> 9
lista 2: 0 -> 2 -> 6 -> 7 -> 10
Tras mezclarlas queda:
lista: 0 -> 1 -> 2 -> 3
-> 5 -> 6 -> 6 -> 7 -> 8 -> 9 -> 10
Esto se puede realizar mediante un
único recorrido de cada lista, mediante dos punteros que recorren cada
una. En el ejemplo anterior se insertan en este orden -salvo los dos 6 que
puede variar según la implementación-: 0 (lista 2), el 1 (lista
1), el 2 (lista 2), el 3, 5 y 6 (lista 1), el 6 y 7 (lista 2), el 8 y 9 (lista
1), y por llegar al final de la lista 1, se introduce directamente todo lo
que quede de la lista 2, que es el 10.
En la siguiente implementación no se crea una nueva lista realmente,
sólo se modifican los enlaces destruyendo las dos listas y fusionándolas
en una sola. Se emplea un centinela que apunta a sí mismo y que contiene
como clave el valor más grande posible. El último elemento de
cada lista apuntará al centinela, incluso si la lista está vacía.
struct lista
{
int clave;
struct lista *sig;
};
struct lista *centinela;
centinela = (struct lista *) malloc(sizeof(struct lista));
centinela->sig = centinela;
centinela->clave = INT_MAX;
...
struct lista *fusion(struct lista *l1, struct lista *l2)
{
struct lista *inic, *c;
if (l1->clave < l2->clave) { inic = l1; l1 = l1->sig; }
else { inic = l2; l2 = l2->sig; }
c = inic;
while (l1 != centinela && l2 != centinela) {
if (l1->clave < l2->clave) {
c->sig = l1; l1 = l1->sig;
}
else {
c->sig = l2; l2 = l2->sig;
}
c = c->sig;
}
if (l1 != centinela) c->sig = l1;
else if (l2 != centinela) c->sig = l2;
return inic;
}
- Segunda parte: divide y vencerás.
Se separa la lista original en dos trozos del mismo tamaño (salvo listas
de longitud impar) que se ordenan recursivamente, y una vez ordenados se fusionan
obteniendo una lista ordenada. Como todo algoritmo basado en divide y vencerás
tiene un caso base y un caso recursivo.
* Caso base: cuando la lista
tiene 1 ó 0 elementos (0 se da si se trata de ordenar una lista vacía).
Se devuelve la lista tal cual está.
* Caso recursivo: cuando la
longitud de la lista es de al menos 2 elementos. Se divide la lista
en dos trozos del mismo tamaño que se ordenan recursivamente. Una vez
ordenado cada trozo, se fusionan y se devuelve
la lista resultante.
El esquema es el siguiente:
Ordenar(lista L)
inicio
si tamaño de L es 1 o 0 entonces
devolver L
si tamaño de L es >= 2 entonces
separar L en dos trozos: L1 y L2.
L1 = Ordenar(L1)
L2 = Ordenar(L2)
L = Fusionar(L1, L2)
devolver L
fin
El algoritmo funciona y termina porque llega un momento en
el que se obtienen listas de 2 ó 3 elementos que se dividen en dos
listas de un elemento (1+1=2) y en dos listas de uno y dos elementos (1+2=3,
la lista de 2 elementos se volverá a dividir), respectivamente. Por
tanto se vuelve siempre de la recursión con listas ordenadas (pues
tienen a lo sumo un elemento) que hacen que el algoritmo de fusión
reciba siempre listas ordenadas.
Se incluye un ejemplo explicativo
donde cada sublista lleva una etiqueta identificativa.
Dada: 3 -> 2 -> 1 -> 6 -> 9 -> 0 -> 7 -> 4 -> 3 ->
8 (lista original)
se divide en:
3 -> 2 -> 1 -> 6 -> 9 (lista 1)
0 -> 7 -> 4 -> 3 -> 8 (lista 2)
· se ordena recursivamente cada lista:
· 3 -> 2 -> 1 -> 6 -> 9 (lista 1)
· · se divide en:
· · 3 -> 2 -> 1 (lista 11)
· · 6 -> 9 (lista 12)
· · se ordena recursivamente cada lista:
· · 3 -> 2 -> 1 (lista 11)
· · · se divide en:
· · · 3 -> 2 (lista 111)
· · · 1 (lista 112)
· · · se ordena recursivamente cada lista:
· · · 3 -> 2 (lista 111)
· · · se divide en:
· · · 3 (lista 1111, que no se divide, caso base). Se devuelve 3
· · · 2 (lista 1112, que no se divide, caso base). Se devuelve 2
· · · se fusionan 1111-1112 y queda:
· · · 2 -> 3. Se devuelve 2 -> 3
· · · 1 (lista 112)
· · · 1 (lista 1121, que no se divide, caso base). Se devuelve 1
· · · se fusionan 111-112 y queda:
· · · 1 -> 2 -> 3 (lista 11). Se devuelve 1 -> 2 -> 3
· · 6 -> 9 (lista 12)
· · · se divide en:
· · · 6 (lista 121, que no se divide, caso base). Se devuelve 6
· · · 9 (lista 122, que no se divide, caso base). Se devuelve 9
· · · se fusionan 121-122 y queda:
· · · 6 -> 9 (lista 12). Se devuelve 6 -> 9
· · se fusionan 11-12 y queda:
· · 1 -> 2 -> 3 -> 6 -> 9. Se devuelve 1 -> 2 -> 3 -> 6 -> 9
· 0 -> 7 -> 4 -> 3 -> 8 (lista 2)
· ... tras repetir el mismo procedimiento se devuelve 0 -> 3 -> 4 -> 7 -> 8
· se fusionan 1-2 y queda:
· 0 -> 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9, que se devuelve y se termina.
La implementación propuesta
emplea un centinela sobre la lista inicial que apunte hacia sí mismo
y que además contiene el máximo valor de un entero. La lista
dispone de cabecera y centinela, pero obsérvese como se elimina durante
la ordenación.
#include <stdlib.h>
#include <limits.h>
struct lista
{
int clave;
struct lista *sig;
};
/* lista con cabecera y centinela */
struct listacc
{
struct lista *cabecera,
*centinela;
};
/* centinela declarado como variable global */
struct lista *centinela;
/* fusiona dos listas */
struct lista *fusion(struct lista *l1, struct lista *l2)
{
struct lista *inic, *c;
if (l1->clave < l2->clave) { inic = l1; l1 = l1->sig; }
else { inic = l2; l2 = l2->sig; }
c = inic;
while (l1 != centinela && l2 != centinela) {
if (l1->clave < l2->clave) {
c->sig = l1; l1 = l1->sig;
}
else {
c->sig = l2; l2 = l2->sig;
}
c = c->sig;
}
if (l1 != centinela) c->sig = l1;
else if (l2 != centinela) c->sig = l2;
return inic;
}
/* algoritmo de ordenación por fusión mediante divide y vencerás */
struct lista *ordenfusion(struct lista *l)
{
struct lista *l1, *l2, *parte1, *parte2;
/* caso base: 1 ó 0 elementos */
if (l->sig == centinela) return l;
/* caso recursivo */
/* avanza hasta la mitad de la lista */
l1 = l; l2 = l1->sig->sig;
while (l2 != centinela) {
l1 = l1->sig;
l2 = l2->sig->sig;
}
/* la parte en dos */
l2 = l1->sig;
l1->sig = centinela;
/* ordena recursivamente cada parte */
parte1 = ordenfusion(l);
parte2 = ordenfusion(l2);
/* mezcla y devuelve la lista mezclada */
l = fusion(parte1, parte2);
return l;
}
/* operaciones de lista */
void crearLCC(struct listacc *LCC)
{
LCC->cabecera = (struct lista *) malloc(sizeof(struct lista));
LCC->centinela = (struct lista *) malloc(sizeof(struct lista));
LCC->cabecera->sig = LCC->centinela;
LCC->centinela->sig = LCC->centinela;
}
/* inserta un elemento al comienzo de la lista */
void insertarPrimero(struct listacc LCC, int elem)
{
struct lista *nuevo;
nuevo = (struct lista *) malloc(sizeof(struct lista));
nuevo->clave = elem;
nuevo->sig = LCC.cabecera->sig;
LCC.cabecera->sig = nuevo;
}
int main(void)
{
struct listacc LCC;
crearLCC(&LCC);
centinela = LCC.centinela;
centinela->clave = INT_MAX;
insertarPrimero(LCC, 8);
insertarPrimero(LCC, 3);
insertarPrimero(LCC, 4);
insertarPrimero(LCC, 7);
insertarPrimero(LCC, 0);
insertarPrimero(LCC, 9);
insertarPrimero(LCC, 6);
insertarPrimero(LCC, 1);
insertarPrimero(LCC, 2);
insertarPrimero(LCC, 3);
LCC.cabecera = ordenfusion(LCC.cabecera->sig);
return 0;
}
Este es un buen algoritmo de ordenación,
pues no requiere espacio para una nueva lista y sólo las operaciones
recursivas consumen algo de memoria. Es por tanto un algoritmo ideal
para ordenar listas.
La complejidad es la misma en todos
los casos, ya que no influye cómo esté ordenada la lista inicial
-esto es, no existe ni mejor ni peor caso-, puesto que la intercalación
de dos listas ordenadas siempre se realiza de una única pasada. La
complejidad es proporcional a N·logN, característica de los
algoritmos "Divide y Vencerás". Para hacer más eficiente
el algoritmo es mejor realizar un primer recorrido sobre toda la lista para
contar el número de elementos y añadir como parámetro
a la función dicho número.
