Titulo: push_swap
Subtitulo: Complexity, big-O, Algoritmos de ordenacion y muchos dolores de cabeza
Bages: 42, C, Makefile, Short-algorithms, Valgrind
Overview: “Este fue mi cuarto proyecto de 42 y está centrado en la complejidad algorítmica, la notación O(n) y los algoritmos de ordenación numérica.
El objetivo consiste en desarrollar un algoritmo capaz de ordenar un stack de números inicialmente desordenados y aleatorios utilizando únicamente un segundo stack como apoyo y un conjunto de movimientos muy restrictivo para manipular los elementos.
La dificultad principal del proyecto no es solo conseguir que los números queden ordenados, sino hacerlo de la forma más eficiente posible. Para evaluar la solución, el número total de movimientos realizados debe mantenerse dentro de unos rangos específicos, lo que obliga a optimizar el algoritmo y analizar cuidadosamente su complejidad y rendimiento.
Key features:
Requirementes:
Build:
Run
Check_results:
Resources:
Secciones adicionales
Objetivo y restricciones del proyecto.
En esta sección hay una entradilla en la que se dice que para completar este proyecto te dejan usar dos stacks. Puedes elegir la estructura de datos que quieras para simularlos.
Inicialmente te dan una secuencia de datos en el argumento de tu programa. Tienes que parsearla y comprobar que los números de esa secuencia cumplan las siguientes condiciones: que solo sean números, que solo sean integers, que no haya duplicados.
Tienes que colocarlos en tu estructura de datos y empezar a movelrlos para ordenarlos
Para ordenar los nuemeros te dejas solo usar una serie de movientos:
sa (swap a): Swap the first 2 elements at the top of the stack a. Does nothing if there is only one or none.sb (swap b) : Swap the first 2 elements at the top of the stack b. Does nothing if there is only one or none.ss : sa and sb at the same time.pa (push a): Takes the first element on top of b and puts it on a. Does nothing if b is empty.pb (push b): Takes the first element on top of a and puts it on b. Does nothing if a is empty.ra (rotate a): Shifts all the elements of the stack a up by one position. The first element becomes the last.rb (rotate b) : Shifts all the elements of the stack b one position upwards. The first element becomes the last one.rr : ra and rb at the same time.rra (reverse rotate a): Shifts all elements of the stack down one position. the stack a. The last element becomes the first.rrb (reverse rotate b): Shifts all the elements of the stack b one position downwards. the stack b. The last element becomes the first.rrr : rra and rrb at the same time.El objetivo es que, durante la ejecución del programa, cada vez que realizas un movimiento para ordenar los números, tienes que informar por pantalla de que este movimiento ha sido realizado. Cada moviemnto relizado couesta un puneto. Menos los descuentos.
El objetivo final es que, al terminar el programa, la secuencia de números esté totalmente ordenada y que el numero de movimientos que hayas hecho usado para hacerlo este dentro de unos baremos:
Además, tienes que cumplir los siguientes benchmarks: para 100 números aleatorios, el programa debe ordenarlos en menos de 700 operaciones, y para 500 números aleatorios, debe ordenarlos en menos de 5500 operaciones.
La clave de las restrciciones del problema, los movimientos y entender que la clave es saber sescoger el algritmo y aislar la definicion de complejidad
Analizando los moviemetos que nos dan,te puedes dar cuenta de que las inserciones de elementos entre los stacks noestan permitidas. Es decir nopudens esoger un numero de el medio de un stack, y colocarlo directamente en cualquier posisicon del otro stack, tampocomp puedes elegir en que posicion concreta de un stack quierres colocar cualquier elementeto. La movilidad de los numeros esta en los extremos de los stacks. Si quieseses simular una insercion porque tu porgram lo necesita, tendraias que desplazar cada uno de los elementos que hay por encima o debajo de el, para llegar al extermo del stack y poder usarlo, teniendo en cuenta que cada ovimieto cuesta 1 punto, esto se vuelev carisimo e ineficiente.
A continuación, se incluye la lista de movimientos que puede haber en el subject, y en esta lista de movimientos te das cuenta de que los únicos movimientos permitidos son aquellos que no están basados en inserciones. Solo puedes moverte por los extremos de los stacks, tanto para colocar los números hacia abajo como para pasarlos de un stack a otro.