Push Swap es el primer proyecto de 42 que hace uso de los algoritmos de ordenación. Si no sabes lo que es un algoritmo o lo que es el tiempo logarítmico, te recomiendo empezar por aquí.
La idea del proyecto es sencilla: ordenar una serie de números en orden ascendente. La gracia es que no podemos ordenar estos números de cualquier manera, si no que lo tenemos que hacer en el menor número de movimientos posible. Si no fuera así nos bastaría con un simple algoritmo Bubble Short, que si has repasado tiempo logarítmico sabrás (y si no te lo cuento yo ya) tiene un tiempo logarítmico de O(n²) en el peor de los casos. Vamos, que utiliza un montón de movimientos, no bueno.
Para ello contamos con una pila de los números que queremos ordenar (a la que vamos a llamar Stack A) y otra pila vacía con la que podemos para poder ordenar todo este desastre (a la que llamaremos Stack B). Una vez que tenemos estas dos pilas o stacks, solo podemos ejecutar una serie de movimientos limitados (añadir un elemento a la lista, sacarlo de ella, rotar la lista entera...) para mover los números de un lado a otro. La lista de movimientos es la siguiente (dentro de la carpeta docs puedes encontrar más documentación sobre cada uno):
| Code | Instruction | Acción |
|---|---|---|
| sa | swap a | Intercambia los 2 primeros elementos de la pila a |
| sb | swap b | Intercambia los 2 primeros elementos de la pila b |
| ss | swap a + swap b | Realiza sa y sb al mismo tiempo |
| pa | push a | Mueve el primer elemento de la pila b al tope de la pila a |
| pb | push b | Mueve el primer elemento de la pila a al tope de la pila b |
| ra | rotate a | Desplaza todos los elementos de la pila a una posición hacia arriba |
| rb | rotate b | Desplaza todos los elementos de la pila b una posición hacia arriba |
| rr | rotate a + b | Realiza ra y rb al mismo tiempo |
| rra | reverse rotate a | Desplaza todos los elementos de la pila a una posición hacia abajo |
| rrb | reverse rotate b | Desplaza todos los elementos de la pila b una posición hacia abajo |
| rrr | reverse rotate a + b | Realiza rra y rrb al mismo tiempo |
Teniendo en cuenta que nuestros movimientos están limitados, la clave de este ejercicio no es solo articular las diferentes acciones que se pueden realizar desde cada una de las pilas, sino implementar un algoritmo que sea capaz de ordenar los números de una manera eficiente.
Hay varios que puedes utilizar, como Ksort o Radix. En mi caso he implementado un algoritmo turco, denominado así porque, al igual que el "automata" del mismo nombre, el programa calcula de manera manual el coste del mejor movimiento antes de realizarlo. Vamos, que calcula una a una todas las posibilidades antes de ordenar un número.
Descarga el respositorio y haz make.
git clone git@github.com:AlexGreenfield/so_long.git && make
Ejecuta push_swap con los números que quieras organizar como argumentos. El resultado será los movimientos necesarios para poder ordenar esos números utilizando las dos pilas. Por ejemplo, para ordenar 3 números, basta con hacer un par movimientos simples: una rotación del stack a y un intercambio de los dos primeros números.
./push_swap 3 2 1
ra
sa
Si quieres contar el número total de movimientos, utiliza wc -l
./push_swap 3 2 1 | wc -l
2Sobre el proceso de Push Swap
- push_swap TUTORIAL! (todo lo básico del proyecto y el algoritmo Turco muy bien explicado)
- push_swap : a performant sorting algorithm using 2 stacks (100-630 moves | 500-5470 moves) (Turco)
Sobre listas enlazadas
Sobre algoritmos y complejidad logarítmica
Sobre el proceso de Push Swap