Este proyecto ha sido creado como parte del currículo de 42 por scamlett y lupalomi.

push_swap

Descripción

push_swap ordena una lista de enteros usando dos pilas (a y b) y solo 11 operaciones permitidas (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr).

El objetivo es generar una secuencia válida de movimientos que deje a ordenada en ascendente con el menor número de operaciones posible.

Esta implementación cumple con:

1. Parsing estricto (enteros válidos sin duplicados, errores por stderr).
2. Cuatro estrategias integradas con selector por flags (--simple, --medium, --complex, --adaptive).
3. Modo --bench con métricas detalladas por stderr.

Instrucciones

Compilar

make

Ejemplos de pruebas

./push_swap 2 1 3 6 5 8
./push_swap --simple 5 4 3 2 1
./push_swap --medium 4 67 3 87 23
./push_swap --complex 4 67 3 87 23
./push_swap --adaptive 4 67 3 87 23
./push_swap --bench --adaptive 4 67 3 87 23
./push_swap --adaptive 0 one 2 3     # Error
./push_swap --simple 3 2 3           # Error (duplicado)

Comprobación con checker_linux

ARG="4 67 3 87 23"
./push_swap --complex $ARG | ./checker_linux $ARG

Flujo de ejecución

1. Parseo de flags y números.
2. Validación de rango y duplicados.
3. Cálculo de índice de desorden.
4. Selección de estrategia.
5. Emisión de operaciones por stdout.
6. En --bench, emisión de métricas por stderr.

Algoritmos implementados

1) Estrategia simple --simple (O(n²))

Archivo: minimum_extraction.c

Metodo: Se busca el minimo en a, se rota a hasta colocarlo arriba y se empuja a b. Se repite hasta vaciar a y luego se devuelve todo a a con pa.

Justificacion: Es el enfoque mas directo y facil de razonar. Funciona bien en listas pequenas o con poco desorden, pero es ineficiente para inputs grandes y/o desordenados.

2) Estrategia intermedia --medium (O(n*sqrt(n)))

Archivo: chunks.c

Metodo: Se asigna un indice a cada nodo y se trabaja por "ventanas" de tamano aprox. $\sqrt{n}$. Se localiza un elemento dentro del rango actual, se rota a para traerlo a la cabeza y se empuja a b. Si el indice es muy bajo se rota b para mantener los mayores mas arriba. Cuando a queda vacia, se devuelven los elementos de b a a sacando siempre el maximo.

Justificacion: Reduce el numero de rotaciones frente minimum_extraction, pero sin la complejidad completa de radix_sort. Es un buen compromiso entre simplicidad y rendimiento.

3) Estrategia compleja --complex (O(n*log(n)))

Archivo: radix_sort.c

Metodo: Se asigna a cada nodo un indice segun su orden relativo en el stack. En cada pasada se mira el bit i del indice; si es 1 se rota a (ra), si es 0 se empuja a b (pb). Al final de la pasada se devuelve todo a a (pa). Se repite por cada bit hasta cubrir el indice mayor.

Justificacion: El método es robusto y escala bien con inputs grandes y/o desordenados.

4) Estrategia adaptativa --adaptive (por defecto)

Elige según desorden inicial:

1. desorden < 0.2: minimum_extraction.c
2. 0.2 <= desorden < 0.5: chunks.c
3. desorden >= 0.5: radix_sort.c

Índice de desorden

Archivo: disorder.c

El desorden corresponde a un número entre 0 y 1 que refleja lo lejos que el stack a se encuentra de estar ordenado al comienzo del programa.

Si todos los números están en orden, el índice de desorden será 0. Cuantos más errores haya, mayor será el índice de desorden, acercándose al valor 1, que refleja el desorden absoluto.

Se ha adaptado el pseudocódigo que aparece en el subject para ajustarse a las variables y los parámetros que empleamos.

Pseudocódigo original:

function compute_disorder(stack a):
    mistakes = 0
    total_pairs = 0
    for i from 0 to size(a)-1:
        for j from i+1 to size(a)-1:
            total_pairs += 1
            if a[i] > a[j]:
                mistakes += 1
    return mistakes / total_pairs

Función adaptada a nuestros parámetros/variables y en C:

float	disorder(t_stack *stack)
{
	t_node	*node1;
	t_node	*node2;
	float	mistakes;
	float	total_pairs;

	mistakes = 0;
	total_pairs = 0;
	if (!stack || !stack->head)
		return (0);
	node1 = stack->head;
	while (node1)
	{
		node2 = node1->next;
		while (node2)
		{
			total_pairs++;
			if (node1->value > node2->value)
				mistakes++;
			node2 = node2->next;
		}
		node1 = node1->next;
	}
	if (total_pairs == 0)
		return (0);
	return (mistakes / total_pairs);
}

Justificación de umbrales

Se usa el indice de desorden para clasificar la entrada en tres regimens: bajo, medio y alto.

Valores bajos (<0,2) suelen implicar pocas inversiones; en esos casos un metodo lineal con pocas rotaciones es suficiente.

Entre 0,2 y 0,5 aumenta la dispersion: trabajar por chunks de tamaño $\sqrt{n}$ reduce rotaciones sin el coste fijo de radix.

Por encima de 0,5 la lista esta muy desordenada y radix ofrece rendimiento estable.

Modo benchmark (--bench)

Archivo: benchmark.c

Muestra por stderr:

1. Desorden inicial en porcentaje con dos decimales.
2. Nombre de estrategia efectiva y complejidad declarada.
3. Total de operaciones.
4. Conteo por operación (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr).

Bonus

Nota: La parte bonus ha usado como inspiración y para resolver dudas el algoritmo creado por 42Yerevan. Observando ambos algoritmos es fácil notar que son similares pero diferentes.

La parte bonus consiste en un checker que, al ejecutarse, recibe el stack a como valor. Debe recibirlo como un string o como argumentos separados. De cualquier otro modo, dará error. Si se introducen flags como --bench o --medium, el programa mostrará Error en el stderr.

Es muy similar al programa principal, pero con la particularidad de que, en lugar de ordenar el algoritmo, es el propio usuario el que debe introducir los propios comandos de movimiento para ir ordenando el stack. Una vez se haya terminado de introducir movimientos, se debe usar la combinación de teclas Control + D, lo que romperá el ciclo de la función get_next_line y determinará si se encuentra bien ordenado o no mostrando en stdout un OK o un KO. Si se introduce una instrucción no válida el programa mostrará Error en el stderr.

Recursos

1. Documentación de 42 sobre push_swap y checker.
2. Tutoriales sobre los algoritmos seleccionados:

• https://es.wikipedia.org/wiki/Ordenamiento_Radix
• https://www.geeksforgeeks.org/c/c-program-for-radix-sort/

3. Big-O Cheat Sheet.

Se utilizó IA como apoyo para estructurar README.md y aclarar dudas.

Contribución

• lupalomi: implementación de parsing, algoritmo simple e intermedio, selector de estrategia, disorder.c, reverse_rotate.c, bonus checker.
• scamlett: implementación algoritmo complejo, modo --bench, push.c, swap.c, rotate.c, disorder.c, integración de libft, formateo README.md y comentarios.

Diario de contribuciones

Susana 04/05:

• creo esqueleto de archivos
• implemento función grado de desorden de array
• creo struct de nodo

Susana 05/05:

• añado libft para poder usar ft_printf
• reimplemento lstlast de libft en utils.c para poder usarlo en nuestro struct de nodo. Se tiene que reimplementar porque libft usa void * content, y nuestro nodo usa int value.
• implemento funciones swap, push, rotate y reverse

Luis 07/05 - 10/05:

• Implementación de funciones estáticas en el archivo 'push_swap.c': Creación e inicialización de pilas de números.
• Implementación de la función 'ft_strcmp' que compara dos cadenas de texto completamente.
• Manejo de flags dentro de la variable t_stack
• Manejo de errores dentro de la entrada: Actualmente, se permite el uso de dos flags de estrategia, aplicandose únicamente la última puesta (Esto lo debemos hablar porque se puede manejar como error, aunque no parece que sea obligatorio).
• Liberación de recursos al cerrar el programa

Luis 13/05:

• Implementación de un nuevo parser: Ahora se aceptan y gestionan correctamente cadenas de números en un mismo string y números separados, PERO NO UNA COMBINACIÓN DE AMBOS (El ejercicio tampoco dice nada al respecto).

Luis 14/05:

• Implementación del algoritmo simple minimum extraction: Consiste en buscar el minimo y ordenar la lista de manera inversa en el stack b. Al hacer esto, haciendo recursivamente push B, logramos conseguir la lista ordenada. Solo funciona con la flag --simple o si el disorder es de 0,20 (20%)
• Corrección de las funciones de movimientos. Todas usaban los nodos como referencia en lugar de los propios stacks. Suele hacer entre 300 - 500 movimientos.

Luis 15/05:

• Implementación del algoritmo medio basado en chunks: Consiste en asignar un índice a cada uno de los números según la posición que deberían tener estándo ordenados (índices de menor a mayor). Una vez asignados, se crea una ventana de índices cuyo tamaño viene dado por la raíz cuadrada de la cantidad total de números pasados. Posteriormente, se procede a pasar los números marcados a la pila B (en caso de ser necesario, se aplican rb para ordenar la pila de mayor a menor) y se repite el proceso sucesivamente, hasta lograr una lista ordenada en B de mayor a menor para pasarla ordenada de menor a mayor en A. La idea de este algoritmo es la misma que la del algoritmo simple con la diferencia de que aquí se hacen grupos. Solo funciona con la flag --medium o si el disorder es mayor a 0,20 (20%) e inferior a 0,50 (50%).
• Corrección de la norminette

Susana 21/05:

• Corrijo spelling (maximum, minimum)
• Limpio disorder.c
• Implemento radix sort y añado a strategy selector
• TODO: --bench e implementar tests

Susana 22/05:

• Añado .gitignore
• Corrijo spelling (adaptative -> adaptive)
• Corrijo radix sort
• Implemento benchmark mode
• Ajusto benchmark mode para igualar output de ejemplos en subject
• Realizo performance tests
• Añado comentarios a funciones
• Corrección con norminette
• TODO: mejorar rendimiento de algoritmos (si es necesario), añadir más comentarios

Luis 24/05

• Implementación de la parte bonus.

Susana 24/05:

• Formateo de README. Elijo español como idioma para explicar y defender proyecto de forma más natural.
• Añado más comentarios a funciones.