Algoritmos de ordenación
Los algoritmos de ordenación son aquellos que se preocupan por ordenar los elementos de un vector. Para ordenar los elementos de un vector hay que decidir dos cosas: por qué campo vamos a ordenar, y que querrá decir que un vector está ordenado.
Por ejemplo, podemos tener un vector cuyas componentes sean registros que contengan datos sobre personas (nombre, apellidos, teléfono, etc). Tenemos varias posibilidades: decidir ordenar por nombre, por apellidos, por teléfono... Además, si ordenamos por nombre, será de la A a la Z o de la Z a la A; igual si ordenamos por apellidos, mientras que si ordenamos por teléfono podemos querer hacerlo de forma ascendente o descendente.
Si nuestro vector es, por contra, numérico, tenemos menos cosas que decidir, ya que al no tratarse de una estructura compleja hay un único campo por el que ordenar. Aún así, tendremos que decidir si consideraremos que el vector está ordenado de forma ascendente o descendente.
Vamos a estudiar los dos algoritmos más sencillos de ordenación. No son los más eficientes, pero sirven para ofrecer una primera idea de cómo realizar la tarea de ordenación. Para aprender sobre algoritmos más eficientes podemos buscar información adicional en la web (Google es siempre un buen aliado).
Algoritmo de selección
El método de selección se basa en la siguiente idea: tenemos un vector inicialmente desordenado. Buscamos el elemento más pequeño dentro del vector y lo comparamos con el elemento de la primera posición. Si el elemento de la primera posición es mayor que el mínimo del vector, entonces intercambiamos los elementos.
Ahora ya tenemos en la primera posición el elemento más pequeño. Nos olvidamos de él, y buscamos, dentro del subvector [2..N] (N el número de elementos del vector) el elemento más pequeño. Comparamos este mínimo con el elemento de la primera posición del subvector. Si el elemento de la primera posición del subvector es mayor que el mínimo del subvector [2..N], intercambiamos los elementos.
Procedemos de forma análoga hasta terminar de recorrer el vector.
Vamos a ver un ejemplo que aclarará cómo funciona este método. Supongamos que tenemos el vector formado por los elementos [5, 4, 3, 2, 1] y queremos ordenarlo de forma ascendente. Empezamos buscando el valor mínimo del vector: el 1. El elemento de la primera posición es el 5. Como 5>1, intercambiamos los elementos 1 y 5, quedando el vector como sigue:
[1, 4, 3, 2, 5]
Ya tenemos el 1 bien colocado. Ahora examinamos el subvector [2..5] (los elementos de las posiciones 2 a 5, es decir, [4, 3, 2, 5]). El mínimo dentro de este subvector es el 2, mientras que el primer elemento del subvector es el 4. Como 4>2, intercambiamos los elementos, quedando el vector como sigue:
[1, 2, 3, 4, 5]
Ya tenemos el 1 y el 2 bien colocados. Ahora examinamos el subvector [3..5] (los elementos de las posiciones 3 a 5, es decir, [3, 4, 5]). El mínimo dentro de este subvector es el 3, y el primer elemento del subvector es el 3. Como coinciden, no realizamos ningún intercambio, quedando el vector como sigue:
[1, 2, 3, 4, 5]
Ya tenemos el 1, el 2 y el 3 bien colocados. Examinamos el subvector [4..5] (los elementos de las posiciones 4 a 5, es decir, [4, 5]). El mínimo dentro de este subvector es el 4, y el primer elemento del subvector es el 4. Como coinciden, no realizamos ningún intercambio, quedando el vector como sigue:
[1, 2, 3, 4, 5]
Y ya no es necesario seguir, porque el subvector que nos quedaría por comprobar sólo tiene un elemento, que seguro que es el último.
Suponiendo que tenemos un vector de enteros, el algoritmo quedaría como sigue:
VARIABLES
v: Vector[1..N] de Entero;
i, j, min, posMin, aux: Entero;
FIN VARIABLES
desde i = 1 hasta N-1 hacer
min = v[i];
posMin = i;
desde j = i hasta N hacer
si v[j] < min entonces
min = v[j];
posMin = j;
fin si
fin desde
aux = v[i];
v[i] = v[posMin];
v[posMin] = aux;
fin desde
Algoritmo de la burbuja
La idea de este algoritmo consiste en ir comparando elementos adyacentes e intercambiarlos si el orden no es correcto. Vamos a ver un ejemplo que nos mostrará cómo exactamente.
Tenemos el vector [3, 1, 5, 4, 2]. Empezamos comparando entre sí la primera pareja: 3 y 1. Como 3>1, los intercambiamos, quedando el vector:
[1, 3, 5, 4, 2]
Ahora comparamos la siguiente pareja: 3 y 5. Como 3<5, no es necesario intercambiarlos, quedando el vector:
[1, 3, 5, 4, 2]
Comparamos la siguiente pareja: 5 y 4. Como 5>4, los intercambiamos, quedando el vector:
[1, 3, 4, 5, 2]
Comparamos la última pareja: 5 y 2. Como 5>2, los intercambiamos, quedando el vector:
[1, 3, 4, 2, 5]
¿Está ya el vector ordenado? No, como puede comprobarse. ¿Qué hemos hecho con este proceso, entonces? Pues hemos conseguido "empujar" el elemento más grande del vector a la última posición, de manera que este elemento ya sabemos que está ordenado, y ahora hemos de repetir el proceso, pero no ya con todo el vector, sino sólo con el subvector [1..4]. Vamos a ir viendo cómo se mueven los elementos en esta segunda vuelta:
Inicialmente: [1, 3, 4, 2, 5]
[1, 3, 4, 2, 5] (no se mueven porque 1<3)
[1, 3, 4, 2, 5] (no se mueven porque 3<4)
[1, 3, 2, 4, 5] (los intercambiamos porque 4>2)
(no comparamos 4 con 5 porque ya sabemos que 5 está bien colocado)
Ya hemos conseguido "empujar" el segundo elemento más grande del vector a la penúltima posición. Ahora repetimos el mismo proceso, pero para el subvector [1..3]:
Inicialmente: [1, 3, 2, 4, 5]
[1, 3, 2, 4, 5] (no se mueven porque 1<3)
[1, 2, 3, 4, 5] (los intercambiamos porque 3>2)
(no comparamos 3 con 4 porque ya sabemos que 4 está bien colocado)
Ya hemos "empujado" el tercer elemento más grande del vector a su posición correcta. Repetimos el proceso, pero para el subvector[1..2]:
Inicialmente: [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5] (no se mueven porque 1<2)
(no comparamos 2 con 3 porque ya sabemos que 3 está bien colocado)
Y ya hemos terminado, puesto que el subvector que queda es de un único elemento que, por fuerza, tiene que estar bien colocado, ya que hemos "empujado" a los mayores que el a la posición correcta.
El algoritmo, suponiendo que estamos tratando con un vector numérico (de enteros, por ejemplo), sería:
VARIABLES
v: Vector[1..N] de Entero;
i, j, aux: Entero;
FIN VARIABLES
desde i = 1 hasta N hacer
desde j = 1 hasta N - i hacer
si v[j] > v[j+1] entonces
aux = v[j];
v[j] = v[j+1];
v[j+1] = aux;
fin desde
fin desde
Tutoriales
