Este proyecto ha sido creado como parte del currículo de 42 por ceboyero, gbenaven.
Ordenar datos en un stack, con un conjunto limitado de instrucciones, usando el menor número posible de operaciones.
| Login | Contribución |
|---|---|
| ceboyero | Parsing, algoritmo simple, benchmark |
| gbenaven | Operaciones de stack, algoritmos medium, complex y adaptive |
push_swap es un proyecto de ordenación algorítmica con restricciones. El objetivo es ordenar una lista de enteros en el stack a usando únicamente dos stacks (a y b) y un conjunto limitado de operaciones, generando la secuencia de instrucciones más corta posible.
El proyecto obliga a implementar cuatro estrategias de ordenación de distinta complejidad y a seleccionar la más adecuada según el nivel de desorden de la entrada. Esto permite explorar de forma práctica la complejidad algorítmica (notación Big-O) y la diferencia real de rendimiento entre algoritmos.
make # compilar push_swap
make clean # eliminar archivos objeto
make fclean # eliminar objetos + binario
make re # recompilar desde cero./push_swap 4 67 3 87 23
./push_swap --simple 5 4 3 2 1
./push_swap --medium 5 4 3 2 1
./push_swap --complex 5 4 3 2 1
./push_swap --adaptive 5 4 3 2 1 # comportamiento por defecto| Flag | Algoritmo | Complejidad |
|---|---|---|
--simple |
Selection sort | O(n²) |
--medium |
Chunk sort | O(n √n) |
--complex |
Quicksort con dos stacks | O(n log n) |
--adaptive |
Adaptativo según índice de desorden (por defecto) | variable |
./push_swap --bench --adaptive 4 67 3 87 23 2>/dev/null # solo métricas
./push_swap --bench --adaptive 4 67 3 87 23 >/dev/null # solo operacionesLa salida del modo benchmark va a stderr e incluye:
- Índice de desorden (% con dos decimales)
- Nombre de la estrategia y su complejidad teórica
- Número total de operaciones
- Conteo por tipo de operación: sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr
El programa imprime Error\n en stderr y termina en caso de:
- Argumentos no enteros
- Desbordamiento de entero (fuera de
INT_MIN/INT_MAX) - Valores duplicados
| Operación | Descripción |
|---|---|
sa |
Intercambia los dos primeros elementos del stack a |
sb |
Intercambia los dos primeros elementos del stack b |
ss |
sa y sb simultáneamente |
pa |
Mueve el primero de b al principio de a |
pb |
Mueve el primero de a al principio de b |
ra |
Rota a hacia arriba (el primero pasa a ser el último) |
rb |
Rota b hacia arriba |
rr |
ra y rb simultáneamente |
rra |
Rota a hacia abajo (el último pasa a ser el primero) |
rrb |
Rota b hacia abajo |
rrr |
rra y rrb simultáneamente |
desorden = errores / total_pares
donde:
total_pares = n * (n - 1) / 2
errores = número de pares (i, j) con i < j pero a[i] > a[j]
0.0→ ya ordenado1.0→ completamente invertido
Busca el mínimo en a, lo sube al tope con rotaciones (ra/rra) y lo pushea a b. Con 3 elementos restantes usa sort_three. Finalmente devuelve todo con pa.
Complejidad: O(n²) — hasta n rotaciones por cada uno de los n elementos.
Espacio: O(1) extra.
Divide el rango de valores en chunks de tamaño √n * 2. Por cada chunk empuja los elementos de a a b, rotando en b para mantener los mayores arriba. Una vez vacío a, devuelve el máximo de b repetidamente.
¿Por qué √n chunks? Cada pasada cuesta O(n) y hay √n pasadas → O(n √n) total.
Espacio: O(1) extra.
Elige un pivote (mediana aproximada) y divide: menores a b, resto rota en a. Se aplica recursivamente alternando quicksort_a / quicksort_b. Casos base (≤ 3 elementos) con sort_three.
Complejidad: O(n log n) con buena elección de pivote.
Espacio: O(log n) en pila de llamadas.
| Rango de desorden | Estrategia | Complejidad |
|---|---|---|
| desorden < 0.2 | Selection sort | O(n) |
| 0.2 ≤ desorden < 0.5 | Chunk sort | O(n √n) |
| desorden ≥ 0.5 | Quicksort | O(n log n) |
Justificación de umbrales:
- 0.2 — Con tan pocas inversiones, el selection sort localiza el mínimo con muy pocas rotaciones, comportándose cerca de O(n).
- 0.5 — Con alto desorden, el quicksort garantiza O(n log n) sin depender de la distribución.
- Entre 0.2 y 0.5 — El chunk sort aprovecha el orden parcial sin el overhead de la recursión.
| Entrada | Mínimo | Buen rendimiento | Excelente |
|---|---|---|---|
| 100 números | < 2000 ops | < 1500 ops | < 700 ops |
| 500 números | < 12000 ops | < 8000 ops | < 5500 ops |
- Knuth, D. E. — The Art of Computer Programming, Vol. 3: Sorting and Searching. Base teórica sobre complejidad y algoritmos de ordenación.
- Visualgo — Sorting Algorithms — Visualización interactiva de algoritmos de ordenación.
- Wikipedia — Quicksort — Descripción del algoritmo y estrategias de elección de pivote.
- Push_swap visualizer — Herramienta para visualizar y depurar las operaciones generadas.
Durante el desarrollo se utilizó Claude (Anthropic) como apoyo en:
- Diseño del README: estructuración y redacción del documento a partir del contenido elaborado por el equipo.
- Revisión de lógica algorítmica: consultas para verificar la corrección de los algoritmos antes de probarlos.
- Depuración conceptual: ayuda para identificar casos borde en stacks pequeños y en el cálculo del índice de desorden.
En todos los casos, el código fue escrito, revisado y comprendido íntegramente por ambos integrantes.