Graham Scan y Quicksort

Seguramente, el principal frente de batalla del desarrollo de la informática hoy en día sean los videojuegos.

Como programadores (en potencia o no), a más de uno le haría ilusión crear su propio juego, y que la gente disfrutara con el.
En el desarrollo de un juego, es muy importante tener un amplio conocimiento sobre ciertas disciplinas, ya que independientemente del nivel de desarrollo que se quiera realizar (Diseñar un motor de juego o utilizar otro de terceros, por ejemplo) pueden ayudar enormemente a la optimización del programa.

Directamente relacionada con la informática gráfica está la geometría computacional, la cual estudia el desarrollo y optimización de algoritmos para la resolución de problemas geométricos.
Muchos de los cálculos tratados en la geometría computacional se basan total o parcialmente en algoritmos de ordenación.

Un ejemplo clásico es el cálculo de la envolvente convexa de un conjunto de puntos mediante el Algoritmo de Graham (http://es.wikipedia.org/wiki/M%C3%A9todo_de_Graham).


En el algoritmo de Graham, la mayoría de la carga computacional se la lleva el paso previo de ordenación. Por lo tanto, la eficiencia del algoritmo será directamente proporcional a la eficiencia del método de ordenación utilizado.
En mi caso Quicksort (http://es.wikipedia.org/wiki/Quicksort).

Ésta es una captura de mi implementación del Algoritmo de Graham, en concreto para el caso de un conjunto de 20.000 puntos:

Como indica el resultado, el tiempo total de cálculo ha sido 3140,0044 milisegundos y el tiempo de ordenación 3130,0043 milisegundos, es decir el 99.68%.