« Volver al inicio

A mí siempre me explicaron que un ordenador es una caja tonta. Más tonta de lo que creemos, por mucho que sepa realizar cálculos de los que a lo mejor no somos capaces de realizar ni siquiera a mano. Un ordenador es tonto porque siempre tenemos que indicarle cómo solucionar determinados problemas ya que no sabe hacerlo por sí solo.

Por ejemplo, un ordenador, a pesar de tener ese nombre, no ordena nada por sí solo. Cuando hacemos un programa donde almacenemos varios datos en un array, necesitamos indicar al programa cómo lo tiene que ordenar, y para eso se diseñaron los algoritmos de ordenación.

Vamos a imaginarnos que tenemos este array:

int[] numeros =

Si quisiéramos ordenarlo de mayor a menor, podemos hacerlo manualmente. Pero, ¿y si en lugar de un array de 9 elementos (índices de 0 a 9), lo fuera de 1000? Entonces tenemos que pedírselo al ordenador en el programa, pero, repito, un ordenador no sabe ordenar.

En los apuntes se habla de tres algoritmos de ordenación muy básicos: burbuja, intercambio e inserción. Estos tres tienen un comportamiento diferente, siendo importante que cada uno de ellos es más eficiente que otro, es decir, unos tardan más que otros en completarse.

Se busca que un algoritmo de ordenación (igual que cualquier otro tipo de algoritmo) tenga que resolver el problema empleando el menor tiempo posible. ¿Has probado ordenar una carpeta tuya llena de canciones por nombre de Artista o por tamaño? ¿A que tarda un tiempo en hacerlo? Pues eso es porque el sistema operativo está aplicando un algoritmo de ordenación sobre un array, que es una lista de tus archivos en la carpeta.

Burbuja

El algoritmo de “burbuja” es el algoritmo más simple que existe, y creo que actualmente sólo tiene fines académicos. Es decir, no se emplea en casos reales, sino únicamente para poder explicar cómo funciona un algoritmo de ordenación.

Para explicar paso a paso cómo funciona este algoritmo, vamos a usar de ejemplo el array definido más arriba, para ordenarlo de menor a mayor: $$a = \lbrace 72, 31, 8, 42, 20, 23, 75, 61, 84, 13, 58 \rbrace$$

Para poder llevar a cabo el algoritmo, necesitamos el tamaño de dicho array en una variable que llamaremos n: $$ n = 10 $$

const int n = numeros.Length

Luego tenemos que llamar a un bucle for para poder recorrer el array de izquierda a derecha:

for(int i = 0; i < n; i++) {
	...
}

Dentro, tendremos que comparar el primer elemento con el siguiente, es decir el índice i del array con el índice i+1 del mismo, de forma que, si detectamos que el número de la izquierda en la iteración actual, es mayor que el de la derecha, tendremos que intercambiar la posición de dicho par para que el valor mayor quede lo más a la derecha posible. Usaremos una variable auxiliar, aux, para poder completar los intercambios de valor. Dejaremos el código así de momento:

for(int i = 0; i < n; i++) {
	if(numeros[i] > numeros[i+1]) {
		aux = numeros[i];
		numeros[i] = numeros[i+1];
		numeros[i+1] = aux;
	}
}

Probamos nuestro código paso por paso:

Cuando i = 0:

En la primera iteración vemos que el valor del array numeros en la posición 0 (numeros[0]) es mayor que (numeros[1]), por lo que tendremos que conmutar ambos valores, y seguir haciendo lo mismo hasta el final del array.

Cuando i = 1:

Aquí pasa lo mismo, siempre que veamos un número en la posición actual mayor que el de la posición siguiente, tenemos que intercambiarlos ya que queremos que el número esté lo más a la derecha posible.

Cuando i = 2:

Cuando i = 3:

Cuando i = 4:

A estas alturas ya nos habremos dado cuenta de que tenemos un primer problema, y es que algunos números siguen quedándose desordenados. Después del 31 va el 8, luego el 42, luego otra vez el 20… cuando habíamos quedado en mover lo más a la derecha posible los números más grandes. ¿Cómo lo gestionamos?

Para empezar, vamos a conocer qué son las tortugas y qué son las liebres en los arrays cuando los estamos ordenando. Las tortugas son los valores que hacen que el algoritmo tarde más en completarse, es decir, los más pequeños que están cerca del final del array, mientras que las liebres son los valores más grandes que están al principio de la lista. Esto es así porque estamos ordenando de menor a mayor. En caso contrario, las tortugas serían los valores más pequeños al principio y las liebres los números más grandes al final.

Al final la cuestión es que en el algoritmo de burbuja tenemos que apartar a las tortugas lo más a la izquierda posible a base de dejar que las liebres se pongan por delante para llegar a la línea de meta, es decir al final del array, y se quedarán ahí.

Con sólo una pasada del algoritmo (con un sólo iterador de i=0 a i<n) no será suficiente porque nuestro array podrá quedar todavía desordenado al finalizar el bucle. Para solucionar este problema, tenemos que realizar varias pasadas y quitar de en medio al resto de tortugas que entorpezcan el camino al resto de liebres que quieran llegar a meta.

¿Quién será la primera liebre en llegar a meta? En este caso será 84, pues es el valor más grande de todo el array y que se quedará al final del mismo:

Cuando i = 9:

Pero también se nos acaba de plantear otro segundo problema, y es que cuando llegamos a i = 9, dentro del bucle intentaremos acceder a numeros[i + 1], que es numeros[10], y ese índice no existe en el array, porque recordemos que en un array de 10 elementos, se cuenta desde el índice 0 hasta el índice 9, por lo que nos dará error en tiempo de ejecución cuando dentro del for se intenta acceder a numeros[10], que está fuera del rango del array.

Tenemos que hacer entonces un cambio en nuestro prototipo: en lugar de buscar desde i = 0 hasta i < n, tenemos que hacerlo que recorra el array hasta i < (n-1):

for(int i = 0; i < n - 1; i++) {
	if(numeros[i] > numeros[i+1]) {
		aux = numeros[i];
		numeros[i] = numeros[i+1];
		numeros[i+1] = aux;
	}
}

Ahora sí que funcionará como se esperaba:

Cuando i = 9 (fin):

El número más grande, que es 84, ya está al final del array. Pero el programa se termina aquí y nos deja con el resto del array desordenado. Vamos de nuevo a tratar de resolver el primer problema y pensemos: ¿cómo hago que el algoritmo se repita hasta completarse? Exacto, con un bucle más. Cuando tengamos que repetir una operación, normalmente es porque hay que meterlo dentro de un bucle.

Lo primero que más de uno pensaría en esta situación sería: pues vale, vamos a meter un bucle for que recorra de j=0 a j<n-1 y cambiamos el código de dentro para que recorra el array en base a lo que vale j en cada iteración:

for(int i = 0; i < n - 1; i++) {		// Pasadas
	for(int j = 0; j < n - 1; j++) {	// Carreras
		if(numeros[i] > numeros[j+1]) {
			aux = numeros[j];
			numeros[j] = numeros[j+1];
			numeros[j+1] = aux;
		}
	}
}

Ahora el bucle j actuará exactamente igual que nuestro bucle i de antes: por cada valor de j, recorremos el array elemento por elemento para poder llevar a cabo la carrera de liebres y tortugas (de ahí que hemos comentado esa línea con “carreras”. El bucle exterior quedará para contar las veces que necesitamos repetir esas carreras, las que llamamos como “pasadas”.

Hemos decidido de momento realizar prácticamente tantas pasadas como elementos de array haya, y que en cada pasada, los corredores sean todos los elementos del array. Esto está bien… pero va a alargar el algoritmo más de la cuenta. Lo que nos faltaba ya si dijimos antes que este algoritmo era muy lento por diseño, ¿no?

Recordemos que en nuestro array, nuestro número más grande, que es el 84, ya ha llegado a la meta y por tanto tiene el oro asegurado. ¿Va a tener que repetir la carrera por ganar? Pues no, por lo tanto, ese número se va a quedar ahí durante el resto del programa por ser el más grande de todos. Esto significa que, para las próximas pasadas, no necesitamos recorrer de nuevo todo el array, sino más bien llegar hasta el penúltimo corredor. Y en la próxima repetición de carrera, hasta el antepenúltimo. Y así sucesivamente.

Cuando i = 0, recorrer hasta j = 8 (si j llega a 9, se termina el bucle):

Cuando i = 1, recorrer hasta j = 7

Cuando i = 2, recorrer hasta j = 6:

Cuando i = 3, recorrer hasta j = 5:

¿Cómo conseguimos eso? Si nos damos cuenta, por cada iteración de i, nos basta con llegar hasta la posición de j donde sea menor que n - i (a medida que incrementa i, disminuye el recorrido de j). Así que tenemos que corregir el bucle j de forma que recorra, por cada iteración de i, hasta la última liebre que haya llegado a meta, es decir, hasta n - i. Pero como no queremos repetir el error de antes saliéndonos del rango del array, lo haremos hasta (n - i) - 1:

for(int i = 0; i < n - 1; i++) {		// Pasadas
	for(int j = 0; j < n - i - 1; j++) {	// Carreras
		if(numeros[i] > numeros[j+1]) {
			aux = numeros[j];
			numeros[j] = numeros[j+1];
			numeros[j+1] = aux;
		}
	}
}

Simulador de métodos de ordenación

Existen muchos simuladores visuales (y auditivos) de algoritmos de ordenación que te demuestran cómo se resuelven paso por paso cada algoritmo de ordenación conocido.

En este caso os presentaré el primer simulador de algoritmos de ordenación que he conocido: Sorting Demo de QuickBASIC 4.5, uno de los programas que incluía este compilador.

El programa incluye algoritmos como el de burbuja, el de inserción directa y el de intercambio directo. Por cada algoritmo que ejecutes, te pondrá en marcha un cronómetro para medir cuánto tiempo se ha tomado en completar el proceso, y así poder compararlo con el del resto de algoritmos. Te darás cuenta de lo lentos que son los algoritmos de inserción y de burbuja en comparación con el de intercambio.

Para poder trabajar con la máquina virtual, necesitas navegar desde el ordenador o con un teclado desde tablet/móvil. Luego puedes probar a visualizar cada uno de los algoritmos con cualquiera de estos atajos:

• B = Burbuja
• I = Inserción
• C = Intercambio

Además, también contiene otros algoritmos que no hemos visto, pero que también son interesantes de conocer:

• M = Algoritmo de montículos
• S = Algoritmo de Shell
• R = Algoritmo de ordenación rápida