Algoritmo de ordenación de cuatro elementos con aplicación práctica con los resultados del grupo de España en el último mundial de fútbol.
El orden, en este caso, es de mayor a menor, es decir el primero es el que mas puntos tiene y el último el que menos, como siempre se establece una clasificación de este tipo.
Para establecer el orden final hago, en un primer paso, comparaciones entre cada dos elementos de la lista, primero con segundo, tercero con cuarto, y si la lista tuviese mas de cuatro elementos, quinto con sexto, etc..
En un segundo paso comparo segundo con tercero, cuarto con quinto, etc. En el ejemplo, como solo tenemos cuatro elementos cierro las comparaciones comparando cuarto con primero, o último con primero, cosa que no podría hacer si el número de elementos de la lista fuese impar . El tercer paso es igual al primer paso, primero con segundo,etc.
La pregunta es ¿ Cuantos pasos hay que dar para ordenar n elementos?
En principio parece que el caso mas desfavorable es cuando en la lista original el elemento que al final del ordenamiento estará primero, está el último. Este elemento ascenderá al primer puesto, en nuestro caso, (n=4, número par) en tres pasos (de cuarto a tercero, de tercero a segundo y de segundo a primero), pero no es el caso mas desfavorable. El caso mas desfavorable es aquel caso en que el primero está el último y el segundo está penúltimo. En este caso, al terminar el primer paso, el que terminará segundo, está el último. Este elemento necesita N-2 pasos mas para ir a su sitio, el segundo. Si no hacemos, o no podemos hacer, la comparación entre último y primero, cosa que sucede si N es impar, este elemento sigue necesitando N-2 pasos mas para llegar a su sitio, pero no participa en el segundo paso, con lo que para que suba a su sitio necesita N-1 pasos a partir del segundo paso. Es decir necesitamos N pasos si N es impar y N-1 pasos si N es par, para ordenar, con este algoritmo, N elementos.
Si N fuese impar y empezamos comparando primero y segundo, tercero y cuarto, el quinto elemento no participaría en el primer paso. Si este elemento debe llegar al primer lugar, necesita N-1 pasos mas para hacerlo. Como no ha participado en el primer paso, necesitamos N pasos para asegurarnos de que el ordenamiento se hace correctamente. Si empezamos comparando segundo con tercero, cuarto con quinto, etc el que no participa en el primer paso es el primer elemento, que si es el que ira al último lugar necesita N-1 pasos mas para hacerlo, en total N pasos.
En la hoja pruebas del libro excel puede verse este proceso para para cuatro elementos.
El ejemplo de uso de este algoritmo, su puesta en práctica, es, como ya dije, el grupo de España del último mundial de futbol. Antes de empezar vamos a establecer los requisitos de la aplicacion:
- Todo partido, de la lista de partidos a celebrar, presenta un 0-0 antes de comenzar.
- Si un partido no ha comenzado, pese a estar como 0-0, no suma puntos a la clasificación.
- Todo partido empezado suma puntos en la clasificación, y si hubiera variaciones en el resultado, se deben recoger en la clasificación, pero se debe incrementar el contador de partidos jugados.
- Debe ser posible saber la clasificación de los equipos al final de una jornada anterior a la actual. Esto significa que en estos momentos, meses después del fin del mundial, podemas saber la clasificación al final de la primera, segunda o tercera jornada.
- En caso de empate a puntos la clasificación se resolvera por la mayor diferencia entre goles marcados y goles recibidos, y en caso de continuar el empate se resolverá por el mayor número de goles marcados
