Algoritmo

Comparación de algoritmos

Normalmente hay más de una forma de resolver un problema. Puede haber muchas recetas diferentes para hacer un determinado plato que parece diferente pero que acaba sabiendo igual cuando todo está dicho y hecho. Lo mismo ocurre con los algoritmos. Sin embargo, algunas de estas formas serán mejores que otras. Si una receta necesita muchos ingredientes complicados que no tienes, no es tan buena como una receta sencilla. Cuando consideramos los algoritmos como una forma de resolver problemas, a menudo queremos saber cuánto tiempo le llevaría a un ordenador resolver el problema utilizando un algoritmo concreto. Cuando escribimos algoritmos, nos gusta que nuestro algoritmo tarde lo menos posible para poder resolver nuestro problema lo más rápido posible.

En la cocina, algunas recetas son más difíciles de hacer que otras, porque requieren más tiempo para terminarlas o tienen más cosas que controlar. Lo mismo ocurre con los algoritmos, y los algoritmos son mejores cuando son más fáciles de hacer para el ordenador. Lo que mide la dificultad de un algoritmo se llama complejidad. Cuando nos preguntamos por la complejidad de un algoritmo, a menudo queremos saber cuánto tardará un ordenador en resolver el problema que queremos que resuelva.

Clasificación

Este es un ejemplo de un algoritmo para clasificar cartas con colores en montones del mismo color:

1. Recoge todas las cartas.
2. Elige una carta de tu mano y mira el color de la carta.
3. Si ya hay un montón de cartas de ese color, pon esta carta en ese montón.
4. Si no hay un montón de cartas de ese color, haz un nuevo montón sólo de este color de carta.
5. Si todavía hay una carta en tu mano, vuelve al segundo paso.
6. Si no queda ninguna carta en la mano, las cartas están ordenadas. Has terminado.

Clasificación por números

Estos son ejemplos de algoritmos para clasificar una pila de tarjetas con muchos números diferentes, de manera que los números estén en orden.

Los jugadores comienzan con una pila de cartas que no han sido clasificadas.

Primer algoritmo

Este algoritmo recorre la pila de cartas, de una en una. Esta carta se compara con la siguiente de la pila. Tenga en cuenta que esta posición sólo cambia en el paso 6. Este algoritmo se llama ordenación de burbujas. Es lento.

1. Si la pila de cartas está vacía, o sólo contiene una carta, está ordenada; has terminado.
2. Coge la pila de cartas. Mira la primera carta (la de arriba) de la pila.
3. La carta que estás mirando es la carta A. La posición en la que se encuentra la carta A actualmente, es en la pila P.
4. Si no hay más cartas en la pila después de la carta A, vaya al paso 8.
5. La siguiente carta de la pila es la carta B.
6. Si la carta B tiene un número menor que la carta A, intercambia las posiciones de las cartas A y B. Recuerda que has hecho esto. Cuando intercambies las cartas, no cambies la posición P.
7. Si hay otra carta en la pila después de la posición P, mírala; vuelve al paso 3.
8. Si no has cambiado la posición de ninguna carta en la última tirada, has terminado; la pila de cartas está ordenada.
9. De lo contrario, vuelva al paso 2.

Ejemplo paso a paso

Tomemos una pila de tarjetas con los números "5 1 4 2 8", y ordenémosla de menor a mayor número utilizando este algoritmo. En cada paso, el algoritmo compara los elementos escritos en negrita. La parte superior de la pila de tarjetas está en el lado izquierdo.

Primera pasada:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 2 8 ) Aquí, el algoritmo compara los dos primeros elementos, y los intercambia.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )(
1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )( 1 4
2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Estos elementos ya están ordenados, por lo que el algoritmo no los intercambia.
Segundo paso:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )(
1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )( 1
2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Ahora, la pila de cartas ya
 está ordenada, pero nuestro algoritmo no lo sabe. El algoritmo necesita una pasada completa sin ningún intercambio para saber que está ordenada.
Tercera pasada:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to }
( 1 2 4 5 8 )
Finalmente, el array está ordenado, y el algoritmo puede detenerse.

Historia

Este es un algoritmo de ordenación fácil de entender. Los informáticos lo llamaron Bubble sort, porque los elementos más pequeños subirán a la cima, cambiando su posición en cada pasada. Por desgracia, el algoritmo no es muy bueno, porque necesita mucho tiempo (muchas pasadas por la pila de cartas) para ordenarlas.

Segundo algoritmo

Este algoritmo utiliza otra idea. A veces, la resolución de un problema es difícil, pero se puede cambiar el problema para que esté hecho de problemas más simples que sean más fáciles de resolver. Esto se llama recursión. Es más difícil de entender que el primer ejemplo, pero dará un mejor algoritmo.

Idea básica

1. Si la pila no tiene cartas, o sólo tiene una carta, está ordenada, y has terminado.
2. Divide la pila de cartas en dos mitades de aproximadamente el mismo tamaño. Si hay un número impar de cartas, uno de los dos montones tendrá una carta más que el otro.
3. Ordena cada una de las dos pilas utilizando este algoritmo (Para cada pila, empieza por el elemento 1 de esta lista).
4. Combine las dos pilas ordenadas, como se describe a continuación.
5. El resultado es una pila de tarjetas ordenadas. Has terminado.

Fusión de dos pilas

Esto funciona con dos pilas de cartas. Una de ellas se llama A, la otra se llama B. Hay una tercera pila que está vacía al principio, llamada C. Al final, contendrá el resultado.

1. Si la pila A o la pila B están vacías, pon todas las cartas de la pila que no esté vacía encima de la pila C; ya has terminado, la pila C es el resultado de la fusión. (Nota: toma toda la pila y ponla sobre la pila C; si lo haces carta por carta cambiará el orden y no funcionará como debería).
2. Mira las cartas superiores de la pila A y de la pila B. Pon la que tenga el número más bajo encima de la pila C. Si la pila C no tenía cartas, ahora tendrá una.
3. Si en la pila A o en la pila B quedan cartas, vuelve al paso 1 para ordenarlas.

Historia

John von Neumann desarrolló este algoritmo en 1945. No lo llamó ordenación por números, sino Mergesort. Es un algoritmo muy bueno para ordenar, en comparación con otros.

Tercer algoritmo

El primer algoritmo tarda mucho más tiempo en ordenar las cartas que el segundo, pero se puede mejorar. Si se observa la ordenación por burbujas, se puede observar que las cartas con números altos se mueven desde la parte superior de la pila con bastante rapidez, pero las cartas con números bajos en la parte inferior de la pila tardan mucho tiempo en subir (moverse a la parte superior). Para mejorar el primer algoritmo, esta es la idea:

En lugar de comparar dos cartas contiguas, al principio se elige una carta "especial". Todas las demás cartas se comparan con ella.

1. Empezamos con una pila A. Habrá otras dos pilas B y C, que se crearán más tarde.
2. Si la pila A no tiene cartas, o sólo tiene una carta, hemos terminado de clasificar.
3. Se elige una carta de la pila A, si es posible al azar. Esto se llama pivote.
4. Todas las cartas restantes de la pila A se comparan con este pivote. Las cartas con un número menor van al montón B, las que tienen un número igual o mayor van al montón C.
5. Si hay alguna carta en los montones B o C, estos montones deben ser ordenados con el mismo algoritmo (Se empieza por la posición 1 de esta lista tanto para el montón B como para el montón C, sucesivamente).
6. Hecho. La pila de cartas ordenada tiene primero la pila ordenada B, luego el pivote y luego la pila ordenada C.

Historia

Este algoritmo fue desarrollado por C. A. R. Hoare en 1960. Es uno de los algoritmos de ordenación más utilizados en la actualidad. Se llama Quicksort.

Animación que muestra cómo funciona una clasificación de burbujas


Ordenación de 7 números mediante el segundo algoritmo de ordenación por números (Mergesort)


El tercer algoritmo para ordenar las cartas. El elemento con la barra roja se elige como pivote. Al principio es el elemento de la derecha. Este algoritmo se llama Quicksort.

Reunir los algoritmos

Si los jugadores tienen cartas con colores y números, pueden ordenarlas por color y número si hacen el algoritmo de "ordenar por colores", luego hacen el algoritmo de "ordenar por números" a cada pila de color, y luego juntan las pilas.

Los algoritmos de ordenación por números son más difíciles de hacer que el algoritmo de ordenación por colores, porque pueden tener que repetir los pasos muchas veces. Se podría decir que la ordenación por números es más compleja.

Páginas relacionadas

• El algoritmo euclidiano se descubrió hace más de 2000 años. Es capaz de encontrar el máximo común divisor de dos números.