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