Animaciones de recursión

Les dejamos animaciones de recursión:

Animación 1

Pueden ver la animación del problema de las Torres de Hanoi:  El problema consiste en tres barras verticales A,B,C y n discos de diferentes tamaños, apilados inicialmente en la barra A y se desea pasar los discos a la barra C, conservando su orden. Las reglas son:

1.- Se moverá un solo disco cada vez.

2.- Un disco no puede situarse sobre otro más pequeño.

3.- Se utilizará la barra B como pila auxiliar.

hanoi

Ver animación

 

 

 

Animación 2

Les dejamos el método de ordenación Quick sort se utiliza para ordenar vectores.

El algoritmo trabaja de la siguiente forma:

  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
  • La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  • Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

En la animación pueden probar el algoritmo con números aleatorios y también ver como funciona si el vector estuviera ordenado (en forma ascendente o descendente). El algoritmo que se muestra está escrito en java, pero puede entenderse su funcionamiento, se utilizan dos for y un if , van las variables utilizadas en cada for.

Ver animación Quick Sort.