Cursus M1 — push_swap

Ordenar enteros con dos pilas y once movimientos, imprimiendo los movimientos y no los números. En la versión 42next, además, hay que medir el desorden de la entrada y tener cuatro estrategias, una por clase de complejidad: O(n²), O(n√n), O(n log n) y una adaptativa que elige según lo desordenada que llegue la lista.

De qué va el proyecto — Te dan una pila a con enteros sin repetir, una pila b vacía y once operaciones (sa, pb, ra, rra…). El programa escribe por stdout la lista de operaciones que deja a ordenada de menor a mayor, y el checker_linux del enunciado las reproduce y responde OK o KO. No se puntúa el tiempo de CPU sino cuántas operaciones imprimes: para 100 números aleatorios hay que bajar de 2000 (excelente, menos de 700) y para 500, de 12000 (excelente, menos de 5500). La versión 42next añade el índice de desorden, las cuatro estrategias forzables con --simple, --medium, --complex y --adaptive, y un modo --bench con estadísticas por stderr. Se hace en pareja: según el README, xalara se encargó del parseo, la normalización, el desorden, el bench y los algoritmos, y gabgalla de las operaciones de pila (push.c). Funciones autorizadas: read, write, malloc, free, exit y la libft (las pilas son listas t_list de la libft).

La página sigue el código por capas, de abajo arriba: primero los datos y los movimientos, luego cómo entra la entrada, después las dos ideas que lo preparan todo (rangos y desorden) y al final las estrategias.

GGlosario de teoría

La página usa palabras que vienen de la teoría de algoritmos, de las matemáticas y de cómo C guarda los números. Aquí está cada una explicada desde cero y con un ejemplo sacado del propio push_swap. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Complejidad y coste

Complejidad y notación O grande (Big-O)

La complejidad de un algoritmo es cómo crece su coste cuando crece la entrada. No dice cuántas operaciones exactas hace con 100 números, sino qué pasa si le das el doble o cinco veces más. La notación O grande lo escribe en corto: O(f(n)) significa «crece, como mucho, al ritmo de f(n)», donde n es el tamaño de la entrada (aquí, cuántos números hay que ordenar). Cada «ritmo» es una clase de complejidad: O(n), O(n log n), O(n²)…

Se ignoran dos cosas a propósito: las constantes (n²/8 y 5·n² son los dos O(n²)) y los términos pequeños (n² + 2n es O(n²), porque con n grande el 2n no pinta nada). Por eso dos algoritmos de la misma clase pueden dar cifras muy distintas, y uno de clase «peor» puede ganar con n pequeño.

En push_swap el coste que importa son las operaciones impresas. La tabla compara cuánto vale cada función con lo medido en la sección 12:

Clasen = 100n = 500crecemedido 100medido 500crece
O(n²), --simple10 000250 000×25~1443~32476×22.5
O(n√n), --medium1 00011 180×11.2~571~5061×8.9
O(n log n), --complex6644 483×6.810846784×6.3

Las cifras absolutas no coinciden (las constantes no salen en la O), pero el crecimiento sí se parece: al multiplicar n por 5, --simple multiplica sus operaciones por más de 20 y el radix por poco más de 6. Con --simple se puede incluso afinar la cuenta: a va encogiendo y cada búsqueda cuesta de media un cuarto de lo que queda, así que salen unas n²/8 rotaciones más n pb y n pa: 1250 + 200 = 1450 para 100 y 31 250 + 1000 = 32 250 para 500, muy cerca de lo medido.

De dónde viene: la O la usó el matemático alemán Paul Bachmann en 1894 y la difundió Edmund Landau, por eso también se llama notación de Bachmann–Landau; la O es de «orden». Donald Knuth la asentó en el análisis de algoritmos en los años setenta.

O(n): coste lineal

El coste crece en proporción a n: el doble de números, el doble de trabajo. Es lo típico de recorrer una lista una vez, haciendo una cantidad fija de trabajo por elemento.

En push_swap son O(n) is_sorted (mira cada pareja de vecinos una vez), stack_pos y copy_values. Y entre las estrategias, sort_low cuando hay pocos elementos fuera de sitio: con 500 números casi ordenados hizo 918 operaciones, menos de dos por número. Por debajo de O(n) no se puede ordenar: como mínimo hay que mirar cada número una vez.

O(n²): coste cuadrático

El coste crece con el cuadrado de n: el doble de números, cuatro veces el trabajo; cinco veces más números, veinticinco veces más. Suele salir de un bucle dentro de otro: para cada elemento, se recorren todos (o casi todos) los demás.

En push_swap: --simple (para cada número, hasta n/2 rotaciones para subirlo), rank_of llamada n veces (250 000 comparaciones con 500 números), compute_disorder (todas las parejas) y lis_lengths. Las tres últimas son O(n²) de CPU, no de operaciones, y por eso no importan (ver «coste de cálculo» más abajo). El --simple sí lo es en operaciones: ~1443 con 100 números pasa el corte de 2000, pero ~32476 con 500 queda lejísimos de 12 000.

O(n log n)

n multiplicado por log n. Como log n crece muy despacio (con 100 números, log₂ n ≈ 6.6; con 500, ≈ 9), es «un poco más que lineal». Es la clase de los buenos algoritmos de ordenación de uso general (mergesort, heapsort, quicksort de media), y se demuestra que ningún algoritmo que ordene solo comparando parejas puede bajar de ahí en el peor caso.

En push_swap es el radix de --complex, que no compara, y su log n tiene otro origen: hace ⌈log₂ n⌉ pasadas (una por bit del mayor rango) y cada una cuesta entre n y 2n operaciones. 7 pasadas para 100 números (1084 operaciones) y 9 para 500 (6784).

O(n√n)

n multiplicado por la raíz cuadrada de n; también se escribe O(n1.5) u O(n sqrt n), como en el comentario de disorder_regime. Queda entre las dos anteriores: √100 = 10 y √500 ≈ 22.4, así que n√n vale 1000 y unos 11 180.

En push_swap es la clase de --medium, y sale de elegir bien el tamaño k de los tramos. En la versión clásica por bloques hay dos costes que tiran en sentidos contrarios: cada número espera hasta k rotaciones (n·k en total, crece con k) y por cada uno de los n/k tramos se recorre a (n·n/k, decrece con k). Se igualan en k = √n, y entonces los dos valen n√n. El código usa 1.5·√n: tramos de 15 con 100 números y de 33 con 500. Lo medido (~571 y ~5061) queda por debajo de n√n porque la constante real es menor que 1.

log₂ n y ⌈ ⌉ (redondeo hacia arriba)

log₂ n es cuántas veces hay que multiplicar 2 por sí mismo para llegar a n o, al revés, cuántas veces se puede partir n por la mitad hasta llegar a 1. log₂ 8 = 3 porque 2·2·2 = 8. Si n no es potencia de 2 sale con decimales: log₂ 100 ≈ 6.64.

⌈x⌉ es el techo de x: redondearlo hacia arriba al entero. ⌈6.64⌉ = 7. Su pareja es el suelo, ⌊x⌋, que redondea hacia abajo, que es lo que hace la división entera con positivos y lo que devuelve isqrt con la raíz.

Juntos, ⌈log₂ n⌉ es cuántos bits hacen falta para escribir los números de 0 a n − 1, y eso es justo el número de pasadas del radix:

n      n − 1 en binario    ⌈log₂ n⌉ = pasadas
4      11                  2
100    1100011             7
500    111110011           9

Por eso log n crece tan despacio: con 512 números siguen bastando 9 pasadas, con 513 hacen falta 10, y la siguiente pasada de más no llega hasta los 1025.

De dónde viene: los símbolos ⌈ ⌉ y ⌊ ⌋ los propuso Kenneth Iverson en 1962, en su libro A Programming Language.

Peor caso, cota y garantía

El coste de un algoritmo suele depender de la entrada concreta, no solo de su tamaño. El peor caso es la entrada de ese tamaño que más le cuesta, y el mejor caso, la que menos. Una cota es un límite que se puede asegurar: «nunca más de tanto». Cuando se dice sin más que un algoritmo «es O(n log n)», normalmente se habla de su peor caso, y eso es una garantía: pase lo que pase, no se dispara.

El radix de push_swap es el ejemplo extremo: su mejor y su peor caso son el mismo. Tras normalizar siempre ordena una permutación de 0..n-1, y en cada pasada hace un ra o un pb por número y un pa por cada uno con ese bit a 0, cantidades que no dependen del orden: 1084 operaciones con 100 números, siempre. Por eso el README dice que da «una cota garantizada». sort_low, en cambio, tiene un mejor caso buenísimo (3 operaciones con 10 0 1 … 9) y uno malo si el desorden es alto; por eso la adaptativa solo lo usa por debajo de 0.2.

Coste de cálculo frente a coste puntuado

Un programa gasta tiempo de CPU (comparaciones, recorridos, malloc) y, en push_swap, además imprime operaciones. Solo lo segundo puntúa. Por eso la página dice a menudo «O(n²) de CPU, que da igual»: rank_of hace 250 000 comparaciones con 500 números y lis_lengths 124 750, en un instante y sin imprimir nada. Al revés, una sola operación impresa de más sí cuenta.

Es la razón de decisiones que en otro programa serían raras: ft_lstlast en cada ra, ft_lstsize en cada rotate_to_top, o una LIS en O(n²) habiendo una en O(n log n).

Búsqueda lineal

Buscar un valor mirando los elementos uno a uno desde el principio hasta encontrarlo o llegar al final. Cuesta O(n) en el peor caso (cuando está al final o no está). Es lo único que se puede hacer en una lista enlazada o en datos sin ordenar; en un array ordenado existe la búsqueda binaria, que descarta la mitad en cada paso y cuesta O(log n).

En push_swap, stack_pos(a, 2) con a: 3 0 2 1 mira el 3, el 0 y el 2 y devuelve 2; con un valor que no está recorre los cuatro y devuelve −1. insert_pos es otra búsqueda lineal, la del mínimo de una clave.

Algoritmos de ordenación

Algoritmo adaptativo

Un algoritmo de ordenación es adaptativo si trabaja menos cuanto más ordenada llega la entrada: aprovecha el orden que ya hay en vez de tratar todas las entradas igual. La ordenación por inserción y Timsort lo son; el radix no, porque hace sus pasadas completas aunque la lista llegue casi ordenada.

En push_swap la palabra tiene dos sentidos que conviene separar. sort_low es adaptativo en el sentido clásico: con 500 números y 25 intercambios entre vecinos hizo 918 operaciones, frente a las 6784 fijas del radix. Y --adaptive se adapta de otra forma: mide el desorden antes de empezar y elige uno de tres métodos (sección 12).

Ordenación por selección

En cada paso se busca el menor de lo que queda sin ordenar y se pone en su sitio definitivo; luego el siguiente menor, y así hasta el final. El nombre viene de ahí: en cada vuelta selecciona el mínimo. Son n búsquedas de hasta n elementos: O(n²).

--simple es una selección adaptada a pilas: el menor que queda en a es siempre el rango next (0, 1, 2…), se sube por el camino corto y se pasa a b con pb. Con 5 4 3 2 1 son 12 operaciones (traza en la sección 08).

Ordenación por inserción

Se mantiene una parte ya ordenada y los demás se van metiendo uno a uno en su hueco, como quien ordena las cartas que tiene en la mano. En el peor caso es O(n²), pero si casi todo está ya en orden apenas hay que insertar nada: es el ejemplo clásico de algoritmo adaptativo.

sort_low es eso: la parte ordenada es la LIS, que se queda en a, y los demás vuelven desde b uno a uno al hueco que calcula insert_pos. Con 0 1 3 2 4 solo hay que reinsertar el 2: 8 operaciones.

Ordenación de burbuja

Se recorre la lista comparando cada pareja de vecinos y se intercambian si están al revés; se repite hasta que una pasada no cambia nada. Es O(n²). El nombre viene de que los grandes van «subiendo» hacia el final como burbujas.

No se usa en push_swap, pero sale en la sección 06 por una propiedad: el número de intercambios que hace la burbuja es exactamente el número de inversiones. 3 2 1 tiene 3 y la burbuja la ordena con 3 intercambios:

3 2 1  →  2 3 1  →  2 1 3  →  1 2 3
Inversión (el «mistake»)

En una secuencia, una inversión es una pareja de posiciones i < j cuyos valores están al revés: a[i] > a[j]. No hace falta que sean vecinos. Una lista ordenada tiene 0; una al revés del todo tiene invertidas todas sus parejas, n(n − 1)/2.

Es lo que el enunciado llama mistakes, y pairs es el total de parejas. Con 1 3 2 las parejas son (1, 3), (1, 2) y (3, 2), y solo (3, 2) está al revés: mistakes = 1, pairs = 3, 33.33 %. Con 500 números hay 124 750 parejas, y en una lista al azar cada una tiene la misma probabilidad de estar bien que al revés: por eso el desorden de una entrada aleatoria ronda el 0.5.

Mide lo lejos que está una lista de estar ordenada de forma muy concreta: es el número de intercambios entre vecinos que hacen falta para ordenarla (los de la burbuja).

Radix sort (ordenación por base)

Un algoritmo que no compara números entre sí: los reparte según sus cifras, una posición cada vez. En base 10 serían diez montones (los que acaban en 0, en 1…); en base 2, solo dos, según el bit sea 0 o 1. Tras pasar por todas las posiciones, la lista queda ordenada. Radix es «raíz» en latín, y en matemáticas es otro nombre de la base de numeración.

En push_swap es --complex, en base 2: los de bit 0 van a b (pb), los de bit 1 al fondo de a (ra), y después todo vuelve con pa. Siempre 1084 operaciones con 100 números y 6784 con 500. Necesita números no negativos y pequeños, que es lo que da la normalización.

De dónde viene: es anterior a los ordenadores. Las máquinas de tarjetas perforadas, que arrancan con las tabuladoras de Herman Hollerith para el censo de Estados Unidos de 1890, ordenaban así: una columna por pasada, repartiendo las tarjetas en casillas según el dígito perforado.

LSD y MSD (cifra menos y más significativa)

LSD son las siglas de least significant digit, la cifra menos significativa: la de las unidades, la que menos pesa en el valor. Un radix LSD empieza por esa cifra y avanza hacia la izquierda; uno MSD (most significant digit) empieza por la que más pesa. En binario, la cifra de menos peso es el bit 0, el de más a la derecha.

El de push_swap es LSD. Con 2 0 3 1 la primera pasada separa pares (2, 0) de impares (3, 1), y la segunda, los menores que 2 (0, 1) de los demás. Lo curioso del LSD es que la última pasada, la del bit que más pesa, es la que decide el orden final; las anteriores solo ordenan lo que queda empatado en los bits altos, y para que ese trabajo no se pierda hace falta que el reparto sea estable.

Estabilidad

Un algoritmo de ordenación es estable si dos elementos que considera iguales salen en el mismo orden en que entraron. Con números distintos parece no importar, pero en el radix sí: en cada pasada solo se mira un bit, y todos los que lo tienen igual son «iguales» para esa pasada.

En el radix de push_swap, pb invierte el orden al apilar en b y los pa lo vuelven a invertir, así que cada grupo conserva su orden: en 2 0 3 1, el 2 y el 0 (los dos con el bit 0 a 0) salen como 2 0, igual que entraron. Si no fuera estable, la segunda pasada estropearía lo que ordenó la primera. Está explicado con la traza en la sección 09.

Chunks, tramos y ventana deslizante

Chunk es «trozo» en inglés. La idea es repartir los valores por intervalos (los más pequeños, los siguientes…) y tratar cada intervalo como un bloque, sin ordenar todavía dentro de él. Es pariente del bucket sort, que reparte los valores en cubos por intervalos y luego ordena cada cubo.

--medium no usa bloques fijos sino una ventana deslizante: un intervalo de rangos [0, i + range] cuyo borde sube uno con cada pb. Con 100 números range vale 15 y con 500, 33 (1.5·√n). Con 5 1 8 3 0 7 2 6 4 y range = 4, el 5 no entra al principio (5 > 0 + 4) y espera con un ra; el 1 sí entra.

Timsort

El algoritmo de ordenación de Python, que Java usa también para ordenar objetos. Lo diseñó Tim Peters para Python en 2002. Busca en la entrada los tramos que ya vienen ordenados (en inglés, runs) y los va fusionando, de modo que con datos casi ordenados trabaja muy poco: es adaptativo.

En la página sale como ejemplo de la misma idea que --adaptive: mirar la forma de la entrada antes de decidir. push_swap no lo usa.

Clave de comparación

El valor por el que se compara al ordenar o al buscar un mínimo. No tiene por qué ser el dato tal cual: se puede transformar para que una sola comparación exprese varios criterios a la vez.

insert_pos busca «el menor de los mayores que v y, si no hay, el menor de todos». Con a = 5 1 2 4 y v = 3 las claves son 5, 1 + INT_MAX, 2 + INT_MAX y 4, y un único mínimo da el 4, en la posición 3 (lo detalla el desplegable de insert_pos).

Secuencias y matemáticas

Rango, normalización y compresión de coordenadas

El rango de un número dentro de un conjunto es el puesto que ocuparía si se ordenaran: cuántos son menores que él. Normalizar es sustituir cada número por su rango. Con valores distintos, los rangos son exactamente 0, 1, …, n − 1.

entrada   42   -7   100   5
rangos     2    0     3   1

Funciona porque el orden relativo no cambia: 42 > 5 y también 2 > 1, así que ordenar los rangos es ordenar los números. En programación competitiva la misma técnica se llama compresión de coordenadas: cambiar valores enormes o dispersos por posiciones pequeñas y seguidas cuando solo importa su orden. Todo en la sección 05.

Ojo: en la sección 04, «el rango» es otra cosa, el intervalo de valores que cabe en un int (de INT_MIN a INT_MAX).

Permutación

Una ordenación concreta de un conjunto de elementos, sin que se repita ni falte ninguno. 2 0 3 1 es una permutación de 0..3, y 0 1 2 3 es otra (la ordenada). Con n elementos hay n! permutaciones (n·(n − 1)·…·1): con 5, 120.

Tras la normalización, toda entrada de push_swap es una permutación de 0..n-1, y ordenar es llevarla a 0 1 2 … n-1. De ahí salen certezas que usan las estrategias: el mayor de b es su tamaño menos uno, y el radix hace siempre las mismas operaciones para un mismo n.

Transitividad

Una relación es transitiva si de «a con b» y «b con c» se deduce «a con c». El ≤ lo es: si a ≤ b y b ≤ c, entonces a ≤ c.

Por eso is_sorted solo compara vecinos: en 0 1 3 4, saber que 0 < 1, 1 < 3 y 3 < 4 basta para saber que 0 < 4 sin compararlos, y la comprobación es O(n) en vez de O(n²). Más en el desplegable de is_sorted.

Subsecuencia frente a subcadena

Una subsecuencia se obtiene quitando elementos de una secuencia sin cambiar el orden de los que quedan; no tienen por qué ser seguidos. Una subcadena (o subarray) sí exige que sean consecutivos.

secuencia      0 1 3 2 4
subsecuencia   0 1 3 4      (se quita el 2)
subcadena      1 3 2        (tres seguidos)
ninguna        0 3 1        (cambia el orden)
Subsecuencia creciente más larga (LIS)

De todas las subsecuencias en las que cada número es mayor que el anterior, la que tiene más elementos. LIS son las siglas en inglés: longest increasing subsequence. Puede haber varias del mismo largo.

En 0 1 3 2 4 hay dos de largo 4, 0 1 3 4 y 0 1 2 4, y lis_lengths se queda con la primera. sort_low deja quietos los de la LIS (ya están en orden entre sí) y solo mueve el resto, aquí el 2. Cuantos menos queden fuera, menos operaciones.

Se calcula con programación dinámica en O(n²). Existe un método en O(n log n), pero aquí no aporta nada porque el tiempo de CPU no puntúa.

Programación dinámica

Una técnica para resolver un problema construyendo su respuesta a partir de las respuestas de versiones más pequeñas del mismo problema, que se calculan una sola vez y se guardan en una tabla para reutilizarlas. Sirve cuando el problema grande se descompone en subproblemas que se repiten.

En lis_lengths, len[i] (el largo de la mejor subsecuencia creciente que acaba en i) se calcula con los len[j] anteriores, ya guardados: el mayor len[j] + 1 entre los j < i con vals[j] < vals[i]. Con 1 0 2 4 3 5 la tabla sale 1 1 2 3 3 4.

De dónde viene: el nombre lo puso Richard Bellman en los años cincuenta. «Programación» no tiene que ver con escribir código: significaba planificar, como cuando se programa un calendario. Según contó él mismo en su autobiografía, eligió «dinámica» porque sonaba bien y era imposible usarla en sentido peyorativo.

Multiplicar en cruz

Para comparar dos fracciones con denominadores positivos no hace falta dividir: a/b < c/d es lo mismo que a·d < c·b. Se multiplican los dos lados por b·d, que al ser positivo no cambia el sentido de la desigualdad.

disorder_regime lo usa para no tocar un float: mistakes / pairs < 1/5 pasa a mistakes * 5 < pairs. Con 1 2 3 5 4 (1 de 10): 5 < 10, régimen bajo. Y es exacto: con 2 1 4 3 5 (2 de 10, justo 0.2) da 10 < 10, falso, sin ninguna duda de redondeo.

División entera, truncar y redondear

En C, dividir dos enteros da un entero: la parte decimal se tira (se trunca). 7 / 2 da 3 y 2 / 3 da 0. Con positivos equivale a redondear hacia abajo; con negativos, C trunca hacia el cero (-7 / 2 da −3).

En push_swap marca detalles: size / 2 con 5 da 2 en rotate_to_top, e isqrt(n) * 3 / 2 tiene que multiplicar antes de dividir, porque 3 / 2 solo daría 1. Para redondear al más cercano en vez de truncar se suma medio divisor antes de dividir: put_disorder hace (20 000 + 1) / 3 = 6667 y no 6666, y por eso imprime 66.67 %.

Bits y representación de números

Binario, bit y peso de un bit

El ordenador guarda los enteros en base 2, solo con las cifras 0 y 1, que se llaman bits. Cada posición vale el doble que la de su derecha (1, 2, 4, 8…), igual que en decimal cada una vale diez veces más. El peso de un bit es lo que vale su posición: el bit 0, el de más a la derecha, es el de menos peso (vale 1); el de más a la izquierda, el de más peso.

 6 = 110       = 4 + 2
99 = 1100011   = 64 + 32 + 2 + 1

El bit 0 dice si el número es par (0) o impar (1). Un int ocupa 32 bits en los ordenadores de 42 y en casi todos los actuales. El radix de push_swap lee los bits de los rangos: 2 0 3 1 en binario es 10 00 11 01.

Operadores de bits

Operadores de C que trabajan sobre los bits de un entero en vez de sobre su valor: & (AND: 1 donde los dos tienen 1), | (OR), ^ (XOR), ~ (NOT), y << y >>, que desplazan los bits a la izquierda o a la derecha. No hay que confundir & y | con && y ||, que son lógicos.

El radix solo usa dos: (n >> bit) & 1 da el bit número bit de n. Está explicado a fondo, con tablas, en el desplegable Qué hacen >> y & 1.

Máscara de bits

Un número que se combina con otro mediante & para quedarse solo con algunos de sus bits y apagar el resto, como una plantilla con agujeros: donde la máscara tiene 1, el bit pasa; donde tiene 0, sale 0.

En el radix la máscara es 1 (…0001): x & 1 deja solo el bit 0. 6 & 1 da 0 (par: pb) y 3 & 1 da 1 (impar: ra).

Complemento a dos y bit de signo

La forma en que casi todos los ordenadores guardan los enteros negativos. Para obtener −x se invierten todos los bits de x y se suma 1. El bit de más peso hace de bit de signo: 0 en los positivos y 1 en los negativos. Con 8 bits, para que se lea mejor:

 7 = 00000111
-7 = 11111001    (se invierten: 11111000, y + 1)
-1 = 11111111

Lo bueno es que la suma funciona igual con positivos y negativos. Lo malo, para un radix, es que leído bit a bit un negativo parece enorme: −7 tiene el bit alto a 1 y el radix lo pondría detrás de todos los positivos. Es una de las razones para normalizar antes (desplegable de los bits). También explica la asimetría del int, de −2147483648 a 2147483647: el 0 ocupa uno de los sitios con el bit de signo a 0.

Precedencia y asociatividad

La precedencia decide qué operador se aplica primero cuando no hay paréntesis, como en 2 + 3 · 4 = 14. La asociatividad decide el orden entre operadores del mismo nivel: % y / van de izquierda a derecha, así que p % 100 / 10 es (p % 100) / 10.

Con los operadores de bits hay trampas: & va después de ==, así que n & 1 == 0 se lee n & (1 == 0). Lo cuenta el final del desplegable de los bits.

Desbordamiento (overflow)

Pasa cuando el resultado de una operación no cabe en su tipo: un int va de −2147483648 (INT_MIN) a 2147483647 (INT_MAX), y INT_MAX + 1 no tiene dónde guardarse. Con enteros con signo, en C eso es comportamiento indefinido.

push_swap lo esquiva en tres sitios: to_int acumula en un long y comprueba el rango en cada dígito, así que 2147483648 se rechaza antes de desbordar; insert_pos suma INT_MAX en un long; y mistakes y pairs son long (124 750 parejas con 500 números, que put_disorder multiplica por 10 000).

Comportamiento indefinido

Situaciones en las que el estándar de C no dice qué debe pasar, y el compilador puede hacer cualquier cosa: dar el resultado «esperado», otro distinto, colgarse, o cambiar según se compile con o sin optimizaciones. No es un error que se detecte: el programa compila y a veces parece funcionar. Ejemplos: desbordar un int con signo, leer a través de un puntero NULL o usar memoria ya liberada.

Por eso to_int comprueba el rango antes de que el número se salga del int, no después, y por eso insert_pos calcula 1 + INT_MAX en un long.

Dependiente de la implementación

Más suave que lo indefinido: el estándar deja elegir a cada compilador, pero el compilador tiene que hacer algo concreto y documentarlo. El programa es válido, pero puede comportarse distinto en otra máquina u otro compilador.

El caso de la página: desplazar a la derecha un negativo con >>. Lo habitual es que entren unos por la izquierda y se conserve el signo (-8 >> 1 da −4), pero C no lo garantiza. Con los rangos de push_swap, que nunca son negativos, la duda no existe.

Coma flotante

La forma de guardar números con decimales (float, double): un número fijo de cifras binarias y un exponente, como la notación científica. Muchos decimales sencillos no tienen representación exacta en binario, igual que 1/3 no la tiene en decimal: por eso 0.1 + 0.2 no da exactamente 0.3.

push_swap no usa ni un float. El desorden se compara multiplicando en cruz y el porcentaje se imprime con punto fijo, así que un desorden de 2 de 10 es exactamente el umbral 0.2 y no 0.19999…

Aritmética de punto fijo

Trabajar con decimales usando solo enteros: se elige una unidad pequeña y se cuenta en esa unidad. En vez de 12.34 euros, 1234 céntimos. Sumar y comparar es exacto; para mostrarlo se separa con / y %.

put_disorder cuenta el desorden en centésimas de porcentaje: p = 3333 significa 33.33 %. p / 100 = 33 es la parte entera y p % 100 = 33 los decimales, que se escriben cifra a cifra para no perder ceros (p = 2 sale 0.02% y no 0.2%).

ASCII y UTF-8

ASCII es la tabla clásica que asigna a cada carácter un número de 0 a 127: letras sin tilde, cifras, signos y caracteres de control, cada uno en un byte. UTF-8 es la codificación que se usa hoy para todo lo demás (ñ, tildes, símbolos): cada carácter ocupa de 1 a 4 bytes, y los de ASCII ocupan uno y valen lo mismo, así que un texto ASCII ya es UTF-8 válido.

En --bench, ² ocupa 2 bytes y √ ocupa 3. ft_putendl_fd los escribe byte a byte sin saber nada de caracteres, y es la terminal la que los junta y los dibuja.

De dónde viene: UTF-8 lo diseñaron Ken Thompson y Rob Pike en 1992.

Estructuras de datos, C y sistema

Pila (LIFO)

Una estructura de datos en la que solo se toca el elemento de arriba, la cima: se mete encima (push) y se saca de encima (pop), como en una pila de platos. Se dice que es LIFO, last in, first out: el último en entrar es el primero en salir.

Las pilas de push_swap son algo más: pa y pb son push y pop puros, pero ra y rra permiten llevar el fondo a la cima, cosa que una pila de verdad no deja. En la práctica, a y b se comportan como un anillo. Están hechas con listas de la libft y el primer nodo es la cima.

Lista enlazada

Una secuencia hecha de nodos sueltos en memoria, cada uno con su dato y un puntero al siguiente; el último apunta a NULL. Es simple si cada nodo solo conoce al siguiente (como la t_list de la libft) y doble si también conoce al anterior.

Frente a un array, meter o sacar al principio es inmediato (por eso pb no hace malloc, solo mueve punteros), pero llegar a la posición i exige recorrer i nodos. Por eso reverse_rotate tiene que buscar el penúltimo y sort_low copia la pila a un array con copy_values antes de calcular la LIS, que necesita acceder por índice.

Anillo (lista circular)

Una secuencia en la que después del último vuelve el primero, como las horas de un reloj: no hay principio ni final fijos, solo desde dónde se mira. Una variante muy usada es el buffer circular, un array que se recorre dando la vuelta.

Con ra y rra, cada pila de push_swap se comporta como un anillo: el fondo está a un rra de la cima, y la distancia a cualquier posición es el mínimo de ir por arriba o por abajo (rotate_to_top). Por eso tras push_non_lis la pila 5 1 2 4 cuenta como ordenada: leída como anillo es 1 2 4 5. Y durante un instante, dentro de rotate, la lista es un anillo de verdad: el último apunta al primero hasta que se corta.

Aritmética de punteros

Sumar un entero a un puntero lo avanza ese número de elementos, no de bytes: si p apunta a un int, p + 1 apunta al int siguiente (4 bytes más allá). Solo tiene sentido dentro de un mismo bloque de memoria, como un array.

lis_keep reserva 2n enteros de una vez y hace prev = len + n, la mitad del bloque. Está dibujado en el desplegable de lis_keep.

Recursión

Una función es recursiva si se llama a sí misma con un problema más pequeño, hasta llegar a un caso que se resuelve sin volver a llamarse (el caso base). Cada llamada pendiente ocupa un trozo de la pila de llamadas, una zona de memoria del programa que no tiene nada que ver con las pilas a y b, y con demasiadas llamadas se agota: es el famoso stack overflow, el desbordamiento de pila.

La ft_lstclear de esta libft es recursiva: antes de liberar un nodo se llama a sí misma con el siguiente, así que con a: 3 → 2 → 1 se anidan tres llamadas y los nodos se liberan del último al primero. El caso base es el último nodo, que no tiene siguiente. Con 500 nodos son 500 llamadas anidadas, sin problema; con millones podría agotar la pila de llamadas.

Evaluación en cortocircuito

&& y || evalúan de izquierda a derecha y se paran en cuanto saben el resultado: en A && B, si A es falso, B ni se evalúa (el resultado será falso igualmente); en A || B, si A es verdadero, tampoco. Así se pueden escribir condiciones en las que la segunda parte solo es segura si la primera se cumple.

is_sorted hace while (s && s->next): s->next solo se lee si s no es NULL. swap hace if (!s || !s->next) por la misma razón, con ||.

Terminador nulo

En C una cadena es una fila de char que acaba en el byte '\0' (valor 0). No se guarda la longitud: el final se sabe porque ahí está el cero. "--simple" ocupa 9 bytes, no 8.

parse_flag compara con ft_strncmp(s, "--simple", 9): el noveno byte es ese '\0', y así --simplex no cuela. En cambio, el write(2, "Error\n", 6) de error_exit escribe 6 bytes: el '\0' no se manda.

Fuga de memoria y valgrind

Una fuga (leak) es memoria reservada con malloc que el programa ya no puede liberar porque no queda ningún puntero hacia ella. El sistema la recupera al acabar el proceso, pero mientras tanto se pierde, y en 42 cuenta como error. Valgrind es una herramienta que ejecuta el programa vigilando cada malloc y cada free, y al final avisa de lo que no se liberó.

push_swap reserva dos bloques por número (el int y el nodo) y los libera todos en free_ps, también al salir por error. Un ejemplo de cómo se perdería memoria: en push, si tmp->next = *dest se hiciera antes de avanzar *src, el resto de a se quedaría sin nadie que lo apuntase.

Descriptores de fichero, stdout, stderr y tuberías

Un descriptor de fichero (fd) es el número con el que un programa se refiere a algo en lo que puede leer o escribir. Todo proceso empieza con tres abiertos: el 0 es la entrada estándar (stdin), el 1 la salida estándar (stdout) y el 2 la salida de errores (stderr). Por defecto los tres van a la terminal, pero se pueden redirigir cada uno por su lado.

Una tubería (|) conecta el stdout de un programa con el stdin del siguiente: en ./push_swap 3 2 1 | ./checker_linux 3 2 1, el checker lee las operaciones. Como push_swap escribe el Error y todo el --bench por el fd 2, nada de eso le llega al checker; y con > /dev/null se tira el stdout y en pantalla queda solo el bench.

Estado de salida

El número que un programa devuelve al sistema al terminar, con el return de main o con exit(n). Por convenio, 0 significa «todo bien» y cualquier otro valor, error. En la shell se consulta con echo $?.

error_exit acaba con exit(1): ./push_swap 3 2 abc; echo $? imprime Error y luego 1.

Excepciones

En lenguajes como C++, Java o Python, un error se puede «lanzar» desde dentro de una función y «capturar» varias llamadas más arriba, saltándose todo lo de en medio. C no tiene ese mecanismo: cada función tiene que devolver algo que diga si fue bien, y quien la llama tiene que mirarlo y pasarlo hacia arriba.

Es lo que hace el parseo: to_int, add_number, add_words y parse_args devuelven 1 o 0, y ese 0 sube hasta main, que llama a error_exit.

Despachador y tabla de dispatch

Un despachador es un trozo de código que, según un valor, decide a qué función llamar. Una tabla de dispatch hace lo mismo con un array de punteros a función indexado por ese valor: tabla[valor](args).

run_strategy es un despachador hecho con if/else (la Norma no permite switch): según ps->strategy llama a sort_simple, sort_medium, sort_complex o sort_adaptive. El enum t_op, que vale de 0 a 10, usa la misma idea como índice de los contadores.

Máquina de estados

Un modelo en el que un sistema está siempre en uno de un número finito de estados y pasa de uno a otro según lo que recibe: un semáforo (verde, ámbar, rojo) o un lector que va carácter a carácter (esperando el signo, leyendo dígitos, error). Es habitual numerar los estados con un enum.

push_swap no tiene una explícita, pero to_int se le parece: primero un signo opcional, luego solo dígitos, y cualquier otra cosa lleva al error. Sale en la sección 01 como uno de los usos típicos de los enum.

Otros

Pseudocódigo

Una descripción de un algoritmo a medio camino entre el lenguaje natural y un lenguaje de programación: deja ver la idea sin atarse a los detalles de ninguno en concreto.

El enunciado da el cálculo del desorden en pseudocódigo («para cada par i < j…»), y compute_disorder es su traducción a C con dos punteros que recorren la lista.

Empírico

Que sale de probar y medir, no de una demostración. Viene del griego empeiría, «experiencia».

El factor 1.5 de isqrt(ps->size) * 3 / 2 es empírico: la teoría dice que el tramo debe ser del orden de √n, pero no qué constante va delante, y esa se ajusta probando. Las cifras de la página (~571, ~5061…) también son empíricas: medias de 10 entradas aleatorias.

Programación competitiva

Concursos en los que se resuelven problemas de algoritmia contra el reloj y con límites de tiempo de ejecución y de memoria: olimpiadas de informática, el ICPC universitario o webs como Codeforces. De ahí vienen los nombres de muchos trucos, como la compresión de coordenadas.

01El modelo de datos

Fichero: push_swap.hTipos: t_ps, t_op, t_strategy

Todo el estado del programa cabe en una struct que se pasa por puntero a todas las funciones (las variables globales están prohibidas):

typedef struct s_ps
{
	t_list		*a;
	t_list		*b;
	int			size;
	long		mistakes;
	long		pairs;
	t_strategy	strategy;
	int			strategy_set;
	int			bench;
	int			count[11];
}	t_ps;

Las pilas son listas de la libft: el primer nodo es la cima y cada content es un int * reservado con malloc. Un detalle que cambia cómo se lee todo lo demás: tras normalize() esos enteros ya no son los números de la entrada sino sus rangos 0..size-1 (sección 05).

Los dos enums están pensados para ahorrarse código:

typedef enum e_strategy
{
	ADAPTIVE,
	SIMPLE,
	MEDIUM,
	COMPLEX
}	t_strategy;

typedef enum e_op
{
	SA, SB, SS, PA, PB, RA, RB, RR, RRA, RRB, RRR
}	t_op;

ADAPTIVE va primero para valer 0: así el ft_bzero de main ya deja puesta la estrategia por defecto. Y cada valor de t_op es el índice de su contador: ps->count[RA]++ cuenta un ra, y --bench solo tiene que recorrer el array.

Qué te obliga a aprender — A diseñar el estado antes que el algoritmo. Meterlo todo en una struct es la forma de vivir sin globales: cada función recibe el contexto entero y no hay estado escondido. Y el enum como índice de array es un patrón que reaparece en mil sitios (tablas de dispatch, contadores, estados de una máquina): un nombre legible que por debajo es un entero de 0 a N-1. El void *content de la libft obliga además a recordar en cada lectura qué hay detrás: *(int *)n->content sale en casi todos los ficheros.

02Las 11 operaciones

Ficheros: swap.c, push.c, rotate.c, rotate_reverse.cAutor de push.c: gabgalla
OperaciónEfecto
sa / sb / ssintercambia los dos primeros de a / b / ambas
pa / pbpasa la cima de b a a / la de a a b
ra / rb / rrrota hacia arriba: la cima pasa al fondo
rra / rrb / rrrrota hacia abajo: el fondo pasa a la cima

Los cuatro ficheros siguen el mismo patrón: una función static que solo mueve punteros y, encima, las públicas, que la llaman, suman su contador y escriben su nombre:

static void	push(t_list **dest, t_list **src)
{
	t_list	*tmp;

	if (!*src)
		return ;
	tmp = *src;
	*src = (*src)->next;
	tmp->next = *dest;
	*dest = tmp;
}

void	pb(t_ps *ps)
{
	push(&ps->b, &ps->a);
	ps->count[PB]++;
	ft_putendl_fd("pb", 1);
}

push mueve el nodo entero, sin malloc ni free; el swap ni siquiera mueve nodos; rotate engancha la cima detrás de ft_lstlast, y reverse_rotate tiene que buscar el penúltimo. Cada una tiene su desplegable con los punteros dibujados antes y después.

Dos reglas que comentan los propios ficheros: las dobles (ss, rr, rrr) mueven las dos pilas pero cuentan y escriben una operación; y con 0 o 1 nodos la operación no hace nada, pero se escribe y se cuenta igual. El header lo deja dicho: los algoritmos solo mueven las pilas a través de estas once funciones.

Cómo funciona swap
/*
** Intercambia los dos primeros. No se mueven los nodos: se intercambian
** sus content (los int*), que es lo mismo y mas sencillo.
**     [1]->[2]->[3]  =>  [2]->[1]->[3]
*/
static void	swap(t_list *s)
{
	void	*tmp;

	if (!s || !s->next)
		return ;
	tmp = s->content;
	s->content = s->next->content;
	s->next->content = tmp;
}

Se cambian los contenidos, no los nodos

Los nodos se quedan donde están y en el mismo orden; lo que se intercambia son sus content, los punteros a los int. Es el intercambio de siempre con una variable auxiliar, solo que con void *: no se copian los números ni hace falta saber qué tipo hay detrás.

antes
  s ──▶ [nodo1] ──▶ [nodo2] ──▶ [nodo3] ──▶ NULL
           │           │           │
           ▼           ▼           ▼
           1           2           3

tmp = s->content;                  tmp ──▶ 1
s->content = s->next->content;     nodo1 ──▶ 2   (ahora 2 está en los dos nodos)
s->next->content = tmp;            nodo2 ──▶ 1

después
  s ──▶ [nodo1] ──▶ [nodo2] ──▶ [nodo3] ──▶ NULL
           │           │           │
           ▼           ▼           ▼
           2           1           3

Por qué recibe t_list * y no t_list **

Las otras tres funciones static reciben la dirección de la cabeza (&ps->a) porque la cima pasa a ser otro nodo y hay que cambiar el propio ps->a. Aquí no: el primer nodo sigue siendo el primero y solo cambia lo que guarda dentro. Con una copia del puntero (swap(ps->a)) basta.

Casos límite

  • Pila vacía (s == NULL) o de un solo nodo (s->next == NULL): no hay dos que intercambiar y vuelve sin tocar nada. sa se escribe y se cuenta igual.
  • El orden de la condición importa: || se para en el primer verdadero, así que s->next solo se lee cuando ya se sabe que s no es NULL.

Dónde se usa

Ojo: ninguna estrategia llama a sa, sb ni ss (tampoco a rr ni a rrr), así que en --bench esos contadores salen siempre a 0. Existen porque el enunciado define las once y el checker las entiende. Se nota con listas cortas: 2 1 sale como ra pb pa y no como sa (sección 12).

Cómo funciona push

El código es el de arriba. Su comentario en push.c lo resume así:

/*
** Saca la cima de src y la pone como cima de dest, moviendo el nodo
** entero (sin malloc ni free):
**     src  [x]->[y]->...        src  [y]->...
**     dest [z]->...        =>   dest [x]->[z]->...
** pa: de b a a.  pb: de a a b.  Si src esta vacia no hace nada.
*/

Las cuatro líneas, una a una

Un pb con a = x y w y b = z, es decir, push(&ps->b, &ps->a):

antes
  a ──▶ [x] ──▶ [y] ──▶ [w] ──▶ NULL
  b ──▶ [z] ──▶ NULL

tmp = *src;             tmp ──▶ [x]
*src = (*src)->next;    a ──▶ [y] ──▶ [w] ──▶ NULL
                        ([x] sigue apuntando a [y], pero ya no es de a)
tmp->next = *dest;      tmp ──▶ [x] ──▶ [z] ──▶ NULL
*dest = tmp;            b ──▶ [x] ──▶ [z] ──▶ NULL

después
  a ──▶ [y] ──▶ [w] ──▶ NULL
  b ──▶ [x] ──▶ [z] ──▶ NULL

El orden no es casual: *src avanza antes de tocar tmp->next. Si se hiciera al revés, tmp->next = *dest borraría el único enlace a [y] y el resto de a se perdería (y con él, su memoria).

Por qué t_list **

Las dos cabezas cambian: a pasa a empezar en [y] y b en [x]. Si push recibiera t_list *, cambiaría copias locales y ps->a y ps->b seguirían igual. Con la dirección de cada cabeza, *src = … y *dest = … escriben en la struct. Los parámetros van en orden destino, origen, como en memcpy: pa es push(&ps->a, &ps->b) y pb al revés.

Casos límite

  • src vacía: no hay nada que mover y vuelve sin tocar nada (el pa/pb se escribe y se cuenta igual).
  • dest vacía: no necesita trato especial. *dest es NULL, así que tmp->next = NULL y el nodo queda solo en su nueva pila. Es lo que pasa en cada primer pb.

Como se mueven nodos ya reservados, la memoria total no cambia en toda la ejecución: los mismos size nodos van y vienen, y free_ps los libera al final estén en la pila que estén.

Cómo funciona rotate
/*
** La cima pasa al fondo y todos suben un puesto:
**     [1]->[2]->[3]  =>  [2]->[3]->[1]
** Se guarda el segundo (la nueva cima), se engancha el primero detras del
** ultimo y se corta su next. ft_lstlast recorre la lista entera; da igual,
** porque solo se puntua el numero de operaciones.
*/
static void	rotate(t_list **s)
{
	t_list	*tmp;

	if (!*s || !(*s)->next)
		return ;
	tmp = (*s)->next;
	ft_lstlast(*s)->next = *s;
	(*s)->next = NULL;
	*s = tmp;
}

Paso a paso

antes
  *s ──▶ [1] ──▶ [2] ──▶ [3] ──▶ NULL

tmp = (*s)->next;            tmp ──▶ [2]
ft_lstlast(*s)->next = *s;   [3]->next = [1]: durante un instante es un anillo
                             *s ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [1] ──▶ …
(*s)->next = NULL;           se corta el anillo por detrás del 1
                             tmp ──▶ [2] ──▶ [3] ──▶ [1] ──▶ NULL
*s = tmp;

después
  *s ──▶ [2] ──▶ [3] ──▶ [1] ──▶ NULL

Por qué en este orden

  • tmp se guarda primero porque (*s)->next se va a poner a NULL y sin él no habría forma de llegar a la nueva cima.
  • ft_lstlast se llama antes de cortar. Si se cortara primero, [1] quedaría como una lista de un nodo, ft_lstlast(*s) devolvería el propio [1] y se engancharía a sí mismo: el nodo se perdería del resto.

Casos límite

Con pila vacía o de un nodo vuelve sin hacer nada, y aquí el chequeo de (*s)->next no es solo un atajo. Sin él, con un único nodo [1]: tmp = NULL, [1]->next = [1], luego [1]->next = NULL y *s = NULL. La pila se quedaría vacía y el nodo, sin nadie que lo apunte.

Con dos nodos, [1]→[2] pasa a [2]→[1]: el mismo resultado que un swap.

Cómo funciona reverse_rotate
/*
** Lo contrario de rotate: el fondo pasa a la cima.
**     [1]->[2]->[3]  =>  [3]->[1]->[2]
** Hay que encontrar el penultimo (pen: el que cumple pen->next->next ==
** NULL), porque su next pasa a ser NULL; el ultimo se engancha delante de
** la cima y se convierte en la nueva cima.
*/
static void	reverse_rotate(t_list **s)
{
	t_list	*pen;
	t_list	*last;

	if (!*s || !(*s)->next)
		return ;
	pen = *s;
	while (pen->next->next)
		pen = pen->next;
	last = pen->next;
	pen->next = NULL;
	last->next = *s;
	*s = last;
}

Por qué hace falta el penúltimo

La lista es simple: cada nodo sabe quién va detrás, pero no quién va delante. El último pasa a la cima, y el que se queda como nuevo fondo, con next = NULL, es el penúltimo. Con ft_lstlast no basta: da el último, pero no quién lo apunta. Por eso se busca a mano el nodo cuyo siguiente es el último, que es el que cumple pen->next->next == NULL.

Paso a paso

antes
  *s ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ NULL

pen = [1]   [1]->next->next = [3]     sigue
pen = [2]   [2]->next->next = [4]     sigue
pen = [3]   [3]->next->next = NULL    para: pen es el penúltimo

last = pen->next;     last ──▶ [4]
pen->next = NULL;     *s ──▶ [1] ──▶ [2] ──▶ [3] ──▶ NULL
last->next = *s;      last ──▶ [4] ──▶ [1] ──▶ [2] ──▶ [3] ──▶ NULL
*s = last;

después
  *s ──▶ [4] ──▶ [1] ──▶ [2] ──▶ [3] ──▶ NULL

Casos límite

  • Pila vacía o de un nodo: vuelve sin hacer nada. Además es lo que hace seguro el bucle: leer pen->next->next exige que pen->next exista, y con dos nodos o más existe siempre.
  • Dos nodos: el bucle no da ninguna vuelta ([1]->next->next ya es NULL), pen = [1], last = [2], y queda [2]→[1]. Con dos nodos ra, rra y sa dan lo mismo.

Recorrer hasta el penúltimo cuesta O(n) de CPU en cada rra, igual que el ft_lstlast de rotate. Da igual, porque solo cuenta que sea una operación impresa.

Qué te obliga a aprender — A separar el mecanismo (mover punteros) de la contabilidad (contar e imprimir). Como cada operación pública imprime y cuenta, es imposible que un algoritmo haga un movimiento "gratis" que el checker no vea, y el contador de --bench siempre coincide con lo que sale por stdout. De paso repasa todo C12: t_list ** para cambiar la cabeza, el caso del penúltimo y los casos límite de lista vacía o de un solo nodo.

03main y el flujo

Fichero: push_swap.cFunciones: main, run_strategy, error_exit, free_ps, free_split
int	main(int argc, char **argv)
{
	t_ps	ps;

	if (argc < 2)
		return (0);
	ft_bzero(&ps, sizeof(t_ps));
	ps.strategy = ADAPTIVE;
	if (!parse_args(&ps, argc - 1, argv + 1))
		error_exit(&ps);
	if (!ps.a)
		return (0);
	compute_disorder(&ps);
	if (ps.mistakes > 0)
		run_strategy(&ps);
	if (ps.bench)
		print_bench(&ps);
	free_ps(&ps);
	return (0);
}

Se lee como el guion del enunciado: sin argumentos no se hace nada (no es un error); se parsea (y ahí dentro se normaliza); si solo había flags, no hay nada que ordenar; el desorden se mide antes de mover nada; si ya está ordenada (mistakes == 0) no se imprime ninguna operación; y --bench informa al final. run_strategy es un if/else sobre ps->strategy que cae en sort_adaptive si no se forzó otra.

Cualquier entrada inválida acaba en error_exit, que libera las dos pilas, escribe Error\n por el fd 2 y sale con exit(1). Pasado por valgrind, el binario no deja fugas ni con las cuatro estrategias ni en la salida por error.

Cómo funciona run_strategy
/*
** Ejecuta la estrategia forzada por flag o, si no se paso ninguno, la
** adaptativa (que elige por su cuenta segun el desorden).
*/
void	run_strategy(t_ps *ps)
{
	if (ps->strategy == SIMPLE)
		sort_simple(ps);
	else if (ps->strategy == MEDIUM)
		sort_medium(ps);
	else if (ps->strategy == COMPLEX)
		sort_complex(ps);
	else
		sort_adaptive(ps);
}

Una cadena de if en vez de un switch

Es un despachador: mira el valor del enum y llama a una función. En otro sitio sería un switch, pero la Norma de 42 no lo permite, así que es un if/else if. El último else no pregunta por ADAPTIVE: recoge todo lo que no sea una de las tres forzadas, y eso es la adaptativa.

De dónde sale ps->strategy

Argumentosps->strategySe ejecuta
ningún flagADAPTIVE (0, por el ft_bzero)sort_adaptive
--adaptiveADAPTIVEsort_adaptive
--simpleSIMPLEsort_simple
--mediumMEDIUMsort_medium
--complexCOMPLEXsort_complex

Lo fija parse_flag durante el parseo. Ojo: main hace ps.strategy = ADAPTIVE justo después del ft_bzero, que ya lo había dejado a 0. Es redundante (el header explica que ADAPTIVE va primero justo para no necesitarlo), pero no hace daño y deja la intención escrita.

Cuándo no se llama

main solo la llama si ps.mistakes > 0. Así ninguna estrategia recibe nunca una pila vacía ni ya ordenada, y todas pueden dar por hecho que hay al menos dos números y al menos una pareja al revés.

Cómo funciona error_exit
/*
** Cualquier entrada invalida acaba aqui: el enunciado pide "Error\n" por
** stderr. Se libera antes de salir para no dejar leaks.
*/
void	error_exit(t_ps *ps)
{
	free_ps(ps);
	write(2, "Error\n", 6);
	exit(1);
}

Tres pasos

  1. free_ps(ps): libera lo que se haya leído hasta el fallo. Al acabar el proceso el sistema recupera la memoria de todos modos, pero valgrind la señalaría y en 42 cuenta como fuga.
  2. write(2, "Error\n", 6): el mensaje exacto que pide el enunciado, por stderr. El 6 son los bytes E r r o r \n, sin el '\0'.
  3. exit(1): termina el programa con un estado distinto de 0. exit no vuelve, así que quien la llama no necesita nada detrás.
$ ./push_swap 3 2 abc; echo $?
Error
1

Por qué se puede llamar en cualquier momento

Solo se llama desde main cuando parse_args devuelve 0, y en ese momento todo está en un estado que free_ps sabe limpiar: ps se puso a cero con ft_bzero, así que a y b son NULL o listas válidas. En ./push_swap 3 x 1, el 3 ya está en a cuando falla la x, y se libera aquí. Lo que no está en ps (el array de ft_split, el int del número malo) ya lo han liberado add_words y add_number antes de devolver 0.

Cómo funciona free_ps
/*
** Libera las dos pilas: los nodos y el int* de cada uno (por eso se pasa
** free como funcion para el content).
*/
void	free_ps(t_ps *ps)
{
	ft_lstclear(&ps->a, free);
	ft_lstclear(&ps->b, free);
}

Dos reservas por número

Cada número ocupa dos bloques de malloc: el int (en add_number) y el nodo que lo apunta (en ft_lstnew). ft_lstclear recibe una función para borrar el contenido y, por cada nodo, la llama con su content y después libera el nodo. Como el contenido es un simple int *, esa función es el propio free: su tipo, void (*)(void *), es justo el que pide el parámetro.

a ──▶ [nodo] ──▶ [nodo] ──▶ NULL
        │          │
        ▼          ▼
       int        int        → 4 free: 2 int (del) + 2 nodos

después: ps->a == NULL

Detalles

  • Libera las dos pilas aunque al terminar bien b esté vacía (y en un error, también): con *lst == NULL, ft_lstclear no hace nada, y así no hay que pensar en qué estado quedó cada una.
  • ft_lstclear deja la cabeza a NULL, de modo que llamar dos veces a free_ps no daría un doble free.
  • La ft_lstclear de esta libft es recursiva: una llamada por nodo. Con los tamaños de push_swap (500) no es problema.
Cómo funciona free_split
/* Libera lo que devuelve ft_split: cada palabra y luego el array. */
void	free_split(char **words)
{
	int	i;

	i = 0;
	while (words[i])
		free(words[i++]);
	free(words);
}

La forma de lo que devuelve ft_split

ft_split hace un malloc para el array de punteros y otro por cada palabra, y marca el final con un NULL. Hay que liberar en ese orden: primero cada palabra (mientras aún se puede leer el array) y luego el array.

ft_split("3 2 1", ' ')

words ──▶ [ * | * | * | NULL ]
            │   │   │
            ▼   ▼   ▼
           "3" "2" "1"          → 4 free: 3 palabras + el array

Casos límite

  • "" o " ": ft_split devuelve un array con solo el NULL. El bucle no da ninguna vuelta y se libera el array, que también era memoria reservada.
  • words == NULL (falló el malloc de ft_split): aquí fallaría al leer words[0], pero no llega a pasar porque add_words lo comprueba antes.

Está en push_swap.c y declarada en el header, aunque solo la usa add_words, en parse.c.

Qué te obliga a aprender — A que main cuente la historia del programa en diez líneas y delegue el resto. Y a pensar en el camino de error tanto como en el bueno: un exit a mitad del parseo no libera nada por sí solo, así que toda salida pasa por un único punto que limpia antes de irse. Es la misma disciplina que pedirá cualquier programa con recursos (ficheros, sockets, hilos).

04Parseo

Fichero: parse.cCadena: parse_args → add_words → add_number → to_int / parse_flag

Todas las funciones devuelven 1 si va bien y 0 si hay error, y el 0 sube hasta main. Lo más delicado es el atoi estricto:

static int	to_int(char *s, int *out)
{
	long	n;
	int		sign;

	sign = 1;
	if (*s == '-')
		sign = -1;
	if (*s == '+' || *s == '-')
		s++;
	if (!*s)
		return (0);
	n = 0;
	while (*s)
	{
		if (!ft_isdigit(*s))
			return (0);
		n = n * 10 + (*s++ - '0');
		if (n * sign > INT_MAX || n * sign < INT_MIN)
			return (0);
	}
	*out = (int)(n * sign);
	return (1);
}

Signo opcional y luego solo dígitos, al menos uno (- o + solos son Error). n es long y el rango se comprueba en cada dígito, así que 2147483648 falla en el último y nunca llega a desbordar. A diferencia del atoi de la libc, aquí no se salta nada: "12abc" es Error, no 12.

Cómo funciona to_int

El código es el de arriba. Su comentario:

/*
** Un atoi estricto: signo opcional y despues solo digitos, al menos uno
** ("-" o "+" solos son Error). n es long para poder comprobar el overflow
** en cada digito, antes de que se salga del int: con 2147483648 la
** comprobacion falla en el ultimo digito y se devuelve Error.
** El resultado va a *out; el return dice si era valido.
*/

Dos salidas: el número y si era válido

El return solo dice sí o no, y el número se escribe en *out. Con un único valor de retorno no se podría distinguir el 0 de un "0" válido del de un error. *out solo se escribe al final, cuando ya se sabe que todo era correcto.

El signo

Dos if seguidos: el primero apunta el signo y el segundo se salta el carácter, sea + o -. Solo se acepta uno: con "+-5" se salta el +, queda "-5" y el - ya no es un dígito, así que es Error. Después, if (!*s) rechaza que tras el signo no quede nada ("+", "-").

Los dos límites del int

n acumula el valor sin signo y el rango se comprueba con el signo ya aplicado, n * sign. Hace falta así porque los límites no son simétricos: INT_MAX es 2147483647 pero INT_MIN es −2147483648. Los dos últimos dígitos de cada caso:

"-2147483648"   sign = -1
   n = 214748364     n * sign = -214748364     bien
   n = 2147483648    n * sign = -2147483648    no es < INT_MIN: bien
   *out = INT_MIN

"2147483648"    sign = 1
   n = 214748364     n * sign = 214748364      bien
   n = 2147483648    n * sign = 2147483648     > INT_MAX: return (0)

Comprobar solo n > INT_MAX rechazaría el INT_MIN, que es un número válido. Y como se comprueba en cada dígito, n nunca pasa de unos once dígitos aunque la entrada tenga veinte: "99999999999999999999" se rechaza en el undécimo y el long no llega a desbordar.

Casos límite, comprobados

"+5"                      5
"-0"                      0     (y "-0 0" es un duplicado: Error)
"00000000000000000001"    1     (los ceros no suman, n no crece)
"+"  "-"  "+-5"  "12abc"  Error
"99999999999999999999"    Error

Los flags se reconocen con ft_strncmp comparando longitud + 1:

	if (ft_strncmp(s, "--bench", 8) == 0)
	...
	if (ft_strncmp(s, "--simple", 9) == 0)
		st = SIMPLE;

El byte de más es el '\0': con 9 se compara también el final de "--simple", así que --simplex no cuela. --bench se puede repetir; un segundo flag de estrategia es Error (strategy_set), y cualquier otro argumento que empiece por -- también.

Cómo funciona parse_flag
/*
** Reconoce un flag. Las comparaciones usan longitud + 1 para meter el '\0'
** en la comparacion: asi "--simplex" no cuela como "--simple".
** --bench se puede repetir sin problema; la estrategia solo se puede fijar
** una vez (strategy_set), un segundo flag de estrategia es Error.
** Cualquier otro "--algo" tambien es Error.
*/
static int	parse_flag(t_ps *ps, char *s)
{
	t_strategy	st;

	if (ft_strncmp(s, "--bench", 8) == 0)
	{
		ps->bench = 1;
		return (1);
	}
	if (ft_strncmp(s, "--simple", 9) == 0)
		st = SIMPLE;
	else if (ft_strncmp(s, "--medium", 9) == 0)
		st = MEDIUM;
	else if (ft_strncmp(s, "--complex", 10) == 0)
		st = COMPLEX;
	else if (ft_strncmp(s, "--adaptive", 11) == 0)
		st = ADAPTIVE;
	else
		return (0);
	if (ps->strategy_set)
		return (0);
	ps->strategy = st;
	ps->strategy_set = 1;
	return (1);
}

Cómo se llega aquí

parse_args manda a parse_flag todo argumento cuyos dos primeros caracteres sean --. Un número negativo como -5 solo tiene un guion y va a add_words; --5 sí llega aquí, no coincide con nada y es Error.

Cada n es la longitud del flag más uno

FlagLetrasn
--bench78
--simple, --medium89
--complex910
--adaptive1011

El byte de más compara el '\0' del literal con lo que haya en esa posición del argumento. Así la coincidencia tiene que ser exacta por los dos lados:

"--simplex" contra "--simple", n = 9:  los 8 primeros iguales, el 9.º 'x' ≠ '\0'  → distinto
"--sim"     contra "--simple", n = 9:  en el 6.º '\0' ≠ 'p'                     → distinto
"--simple"  contra "--simple", n = 9:  los 9 iguales, '\0' incluido              → 0

El orden de las comprobaciones

  • --bench va primero y vuelve enseguida sin mirar strategy_set: por eso se puede repetir.
  • Las cuatro ramas de estrategia solo deciden el valor de st; la comprobación de strategy_set y la asignación están una sola vez al final, en vez de repetidas en cada rama.
  • --adaptive también marca strategy_set, aunque su valor sea el de por defecto: --adaptive --simple es Error, igual que --simple --simple.
./push_swap --bench --bench 2 1      ra pb pa  (y el bench una vez)
./push_swap --benchx 2 1             Error
./push_swap --adaptive --adaptive 2 1  Error
./push_swap --5 1                    Error

Y un argumento puede traer varios números: add_words lo parte con ft_split(arg, ' '), así que ./push_swap "3 2 1" vale lo mismo que ./push_swap 3 2 1. Un argumento sin palabras ("" o " ") da words[0] == NULL y es Error. Cada número se añade con ft_lstadd_back, de modo que el primero de la línea de comandos queda en la cima, como pide el enunciado. Los duplicados no se miran aquí: los detecta normalize.

Cómo funciona add_words
/*
** Un argumento puede llevar varios numeros: "3 2 1" vale lo mismo que
** 3 2 1. Se parte por espacios y se anade cada palabra.
** Un argumento sin palabras ("" o "   ") da words[0] == NULL -> Error.
** Se para en el primer numero malo (ok a 0) y se libera el split siempre.
*/
static int	add_words(t_ps *ps, char *arg)
{
	char	**words;
	int		ok;
	int		i;

	words = ft_split(arg, ' ');
	if (!words)
		return (0);
	ok = (words[0] != NULL);
	i = 0;
	while (ok && words[i])
		ok = add_number(ps, words[i++]);
	free_split(words);
	return (ok);
}

Paso a paso

arg = "3 2 1"
words = { "3", "2", "1", NULL }
ok = 1                  (hay al menos una palabra)
add_number("3")  → 1    a: 3
add_number("2")  → 1    a: 3 2
add_number("1")  → 1    a: 3 2 1
free_split(words)
return (1)

La variable ok

Hace dos papeles. Empieza como «¿hay alguna palabra?» (words[0] != NULL), y luego guarda el resultado del último add_number. El bucle sigue mientras ok sea 1 y queden palabras, de modo que se para en el primer número malo:

./push_swap 3 x 1
  "3"  → a: 3
  "x"  → add_number devuelve 0, ok = 0, el bucle acaba
  "1"  → ni se mira
  → Error (el 3 que ya estaba en a lo libera error_exit)

Lo importante es que no hay un return en medio: se sale del bucle, se pasa siempre por free_split y solo después se devuelve ok. Así el array de ft_split se libera tanto si todo fue bien como si no.

Casos límite

  • "" o " ": words = { NULL }, ok = 0 desde el principio, se libera y es Error.
  • ft_split devuelve NULL (falló un malloc): return 0 directamente, porque no hay nada que liberar.
  • Se pueden mezclar: ./push_swap "3 2" 1 da exactamente las mismas operaciones que ./push_swap 3 2 1.
Cómo funciona add_number
/*
** Convierte una palabra y la mete al final de a (asi el primer numero de
** la linea de comandos queda en la cima). Se reserva el int primero y se
** libera si la palabra no es un numero o falla ft_lstnew.
** Los duplicados no se miran aqui sino en normalize().
*/
static int	add_number(t_ps *ps, char *word)
{
	int		*value;
	t_list	*node;

	value = malloc(sizeof(int));
	if (!value)
		return (0);
	node = NULL;
	if (to_int(word, value))
		node = ft_lstnew(value);
	if (!node)
	{
		free(value);
		return (0);
	}
	ft_lstadd_back(&ps->a, node);
	ps->size++;
	return (1);
}

El int se reserva antes de convertir

to_int escribe directamente en *value, el int que acabará siendo el content del nodo. Así no hay que copiar el número de una variable local a la memoria reservada.

Una sola salida para los dos fallos

node empieza a NULL y solo deja de serlo si to_int va bien y ft_lstnew consigue su malloc. Con un único if (!node) se cubren los dos casos, y en los dos hay que hacer lo mismo: liberar el int, que nadie más apunta, y devolver 0.

Qué pasanodeResultado
falla el malloc del int(no llega)return 0
to_int rechaza la palabraNULLfree(value), return 0
falla ft_lstnewNULLfree(value), return 0
todo biennodo nuevoal final de a, size++, return 1

Ojo: un fallo de memoria acaba en el mismo camino que una entrada inválida, así que también imprime Error.

Al final, no al principio

ft_lstadd_back deja los números en el orden de la línea de comandos: con 5 1 8, a queda 5 → 1 → 8, con el 5 en la cima, que es lo que pide el enunciado. Con ft_lstadd_front la pila saldría al revés. El precio es que ft_lstadd_back recorre la lista entera cada vez (O(n²) para leer n números), que con 500 no se nota.

ps->size cuenta los números leídos y es el tamaño que usan luego copy_values, normalize, el radix y push_non_lis.

Lo comprobado al ejecutarlo:

./push_swap --simplex 3 2 1          Error
./push_swap --simple --medium 2 1    Error
./push_swap 2147483648               Error
./push_swap 1 01                     Error   (duplicado: los dos valen 1)
./push_swap -0 0                     Error   (ídem)
./push_swap ""                       Error
./push_swap 3 -- 1                   Error   ("--" es un flag desconocido)
./push_swap 2147483647 -2147483648   ra pb pa
./push_swap --bench                  (nada: solo flags)
./push_swap 1 2 3                    (nada: ya ordenada)

Como el separador es solo el espacio, "3<TAB>2" es una única palabra con un tabulador dentro y da Error.

Qué te obliga a aprender — Que validar es más difícil que calcular. Hay que decidir qué es exactamente "un entero" (¿+5? sí; ¿-? no; ¿01? sí, pero es el 1) y detectar el desbordamiento antes de que ocurra, porque después ya es comportamiento indefinido. El truco de len + 1 en strncmp es una lección pequeña sobre por qué el terminador nulo forma parte de la cadena. Y la cadena de funciones que devuelven 0/1 es el manejo de errores de C sin excepciones.

05Normalización a rangos

Fichero: index.cFunciones: normalize, rank_of, copy_values

La idea clave del proyecto. Justo después de leer, cada número se sustituye por su rango: cuántos números de la entrada son menores que él.

entrada   42   -7   100   5
rangos     2    0     3   1
static int	rank_of(int *vals, int size, int i)
{
	int	rank;
	int	j;

	rank = 0;
	j = 0;
	while (j < size)
	{
		if (j != i && vals[j] == vals[i])
			return (-1);
		if (vals[j] < vals[i])
			rank++;
		j++;
	}
	return (rank);
}

normalize copia primero la pila a un array con copy_values, porque va pisando los content con los rangos y cada rango tiene que calcularse con los valores originales. Si rank_of encuentra un igual en otra posición devuelve -1: es un duplicado, y así la detección de duplicados sale gratis del mismo bucle. Es O(n²) en tiempo de cálculo, que da igual: aquí solo puntúan las operaciones.

Cómo funciona copy_values
/*
** Copia la pila a un array. Hace falta porque normalize() va pisando los
** content con los rangos y cada rango se tiene que calcular con los
** valores originales. Tambien la usa sort_low para calcular la LIS.
*/
int	*copy_values(t_ps *ps)
{
	int		*vals;
	t_list	*n;
	int		i;

	vals = malloc(sizeof(int) * ps->size);
	if (!vals)
		return (NULL);
	n = ps->a;
	i = 0;
	while (n)
	{
		vals[i++] = *(int *)n->content;
		n = n->next;
	}
	return (vals);
}

De lista a array

Reserva size enteros y recorre a de la cima al fondo copiando cada número. La posición en el array es la posición en la pila: vals[0] es la cima.

a: 42 → -7 → 100 → 5 → NULL
vals = { 42, -7, 100, 5 }

Son números copiados, no punteros a los content. Eso es lo que la hace útil en normalize: cuando el bucle escribe el rango del 42 en el primer nodo, vals[0] sigue valiendo 42 y los rangos de los siguientes se calculan contra los valores de verdad.

Por qué es pública

Es la única de index.c que se usa fuera: sort_low la llama para tener los rangos en un array y calcular la LIS con acceso por índice, que en una lista sería un recorrido cada vez. Quien la llama tiene que hacer el free.

Casos límite

  • Si falla malloc devuelve NULL: normalize devuelve 0 (y el programa acaba en Error) y sort_low cambia a sort_medium.
  • Ojo: reserva ps->size y no ft_lstsize(ps->a), así que solo es correcta mientras todos los números están en a. Se cumple en las dos llamadas (durante el parseo y al principio de sort_low, antes de mover nada); si se llamara con nodos en b, las últimas casillas del array quedarían sin rellenar.
Cómo funciona rank_of

El código es el de arriba. Recibe el array completo y el índice i del valor del que se quiere el rango, y lo compara con todos los demás.

Traza con 42 -7 100 5

Para i = 0 (el 42):

j = 0   vals[0] = 42    es él mismo: ni duplicado ni menor
j = 1   vals[1] = -7    -7 < 42     rank = 1
j = 2   vals[2] = 100   no
j = 3   vals[3] = 5     5 < 42      rank = 2
return (2)

Y así con cada uno:

ivalormenores que élrango
042−7, 52
1−7ninguno0
210042, −7, 53
35−71

Por qué salen exactamente 0..n-1

Si no hay repetidos, el k-ésimo menor tiene exactamente k números por debajo: el menor tiene 0, el siguiente 1… y el mayor, n − 1. Cada rango sale una sola vez y no queda ningún hueco, así que el resultado es una permutación de 0..n-1.

Los duplicados, en el mismo bucle

Si dos valores fueran iguales, los dos tendrían el mismo rango y la permutación se rompería. rank_of lo detecta al vuelo: si encuentra otro igual en una posición distinta devuelve -1, que no es un rango posible.

./push_swap 1 01      vals = { 1, 1 }
  i = 0, j = 1:  j != i y vals[1] == vals[0]  →  return (-1)  →  Error

El j != i es imprescindible: sin él, cada valor se encontraría a sí mismo y todo sería «duplicado». Se comprueba antes que el <, así que en cuanto aparece un igual la función sale sin seguir contando.

Coste

Una llamada recorre los n valores y normalize la llama n veces: n² comparaciones, 250 000 para 500 números. Es instantáneo, y no imprime ni una operación.

El orden relativo no cambia, así que ordenar los rangos es ordenar los números, y el desorden sale idéntico. Lo que se gana es que los valores pasan a ser exactamente 0..n-1, y de eso viven todas las estrategias:

Qué te obliga a aprender — A transformar el problema antes de resolverlo. Los valores concretos no importan, solo su orden; quitarlos de en medio convierte "ordenar enteros cualesquiera" en "ordenar una permutación de 0..n-1", que es un problema mucho más amable. Es la misma idea que la compresión de coordenadas de la programación competitiva, y la que hace posible usar radix sin preocuparse de signos ni de rangos enormes.

06El índice de desorden

Fichero: index.cFunciones: compute_disorder, disorder_regime

El enunciado da el pseudocódigo: para cada par (i, j) con i antes que j, se suma uno a pairs, y si a[i] > a[j] (están al revés) uno a mistakes. Desorden = mistakes / pairs, entre 0 (ordenada) y 1 (al revés del todo).

3 2 1       pairs 3,  mistakes 3  -> 100 %
1 3 2       pairs 3,  mistakes 1  ->  33.33 %
1 2 3 5 4   pairs 10, mistakes 1  ->  10 %

compute_disorder lo calcula con dos punteros que recorren la lista, pero no divide: guarda los dos enteros. La decisión de régimen multiplica en vez de dividir, y así no aparece ni un float en todo el programa:

int	disorder_regime(t_ps *ps)
{
	if (ps->mistakes * 5 < ps->pairs)
		return (0);
	if (ps->mistakes * 2 < ps->pairs)
		return (1);
	return (2);
}

mistakes * 5 < pairs es lo mismo que mistakes / pairs < 0.2 (sin redondeos), y * 2 es el umbral de 0.5. mistakes y pairs son long, así que estas multiplicaciones no desbordan (con 500 números hay 124750 pares).

Cómo funciona disorder_regime

El código es el de arriba. Su comentario resume la equivalencia:

/*
** Que regimen pide el enunciado segun el desorden d = mistakes / pairs,
** multiplicando en vez de dividir para no usar float:
**
**     mistakes * 5 < pairs   <=>  d < 0.2    -> 0  (metodo O(n))
**     mistakes * 2 < pairs   <=>  d < 0.5    -> 1  (metodo O(n sqrt n))
**     si no                       d >= 0.5   -> 2  (metodo O(n log n))
*/

Por qué multiplicar es lo mismo que dividir

Partiendo de d < 0.2 y multiplicando los dos lados por 5 · pairs, que es positivo y no cambia el sentido de la desigualdad:

mistakes / pairs < 1/5
mistakes · 5     < pairs

Con 0.5 = 1/2 sale mistakes · 2 < pairs. Las dos versiones son exactas con enteros: no hay ni redondeo ni división entera que trunque.

El orden de los if

Primero se prueba el umbral más bajo. Si no se cumple, ya se sabe que d ≥ 0.2 y basta con mirar si es menor que 0.5; si tampoco, queda d ≥ 0.5.

Entradamistakespairs·5 < pairs·2 < pairsRégimen
1 2 3 5 41105 < 10 sí—0 (low)
1 3 2135 < 3 no2 < 3 sí1 (medium)
3 2 13315 < 3 no6 < 3 no2 (complex)

Los bordes exactos

Como las comparaciones son estrictas, un desorden de exactamente 0.2 ya no es «bajo» y uno de exactamente 0.5 ya es «alto», tal como lo plantea el enunciado (d < 0.2, d ≥ 0.5). Comprobado con --bench:

2 1 4 3 5   mistakes 2, pairs 10   10 < 10 no, 4 < 10 sí   20.00%  Adaptive / O(n√n)
1 4 3 2     mistakes 3, pairs 6    15 < 6 no,  6 < 6 no    50.00%  Adaptive / O(n log n)

Quién la llama

sort_adaptive, para elegir método, y put_strategy, para decir en --bench cuál se usó. Las dos leen los mismos mistakes y pairs, medidos una sola vez antes de mover nada, así que siempre coinciden.

Ojo con pairs == 0 (un solo número): 0 < 0 es falso las dos veces y devuelve 2. A sort_adaptive no llega nunca (con mistakes == 0 no se ordena nada), pero ./push_swap --bench 5 imprime Adaptive / O(n log n), y con una lista ya ordenada de dos o más números imprime Adaptive / O(n), aunque en ninguno de los dos casos se haya ejecutado ningún método.

Qué te obliga a aprender — Que "contar inversiones" es una medida de lo lejos que está una permutación de estar ordenada (es justo el número de intercambios entre vecinos que haría el burbuja). Y el truco de comparar fracciones multiplicando en cruz: con enteros, a/b < c/d es a·d < c·b, exacto y sin la imprecisión de la coma flotante.

07stack_utils

Fichero: stack_utils.cFunciones: stack_pos, rotate_to_top_a/b

Dos herramientas que comparten casi todas las estrategias. stack_pos devuelve la posición de un valor (0 = cima, −1 si no está); como las pilas guardan rangos, buscar "el 3" es buscar el cuarto menor. Y la pieza más usada de todo el proyecto:

void	rotate_to_top_a(t_ps *ps, int pos)
{
	int	size;

	size = ft_lstsize(ps->a);
	if (pos <= size / 2)
		while (pos-- > 0)
			ra(ps);
	else
		while (pos++ < size)
			rra(ps);
}

Subir a la cima el nodo de la posición pos por el camino corto: ra pos veces si está en la mitad de arriba, rra size - pos veces si está en la de abajo. Nunca cuesta más de size / 2. rotate_to_top_b es lo mismo con rb y rrb.

Cómo funciona stack_pos
/*
** Posicion del valor v en la pila (0 = cima), o -1 si no esta. Como las
** pilas tienen rangos, buscar "el 3" es buscar el cuarto menor.
*/
int	stack_pos(t_list *s, int v)
{
	int	i;

	i = 0;
	while (s)
	{
		if (*(int *)s->content == v)
			return (i);
		s = s->next;
		i++;
	}
	return (-1);
}

Una búsqueda lineal

Recorre la pila desde la cima con i contando posiciones y devuelve la primera en la que encuentra v. Si llega al final sin encontrarlo, -1, que no puede ser una posición.

a: 3 0 2 1
stack_pos(a, 2)   →  i = 0 (3), i = 1 (0), i = 2 (2)  →  2
stack_pos(a, 5)   →  recorre los cuatro sin éxito      →  -1

s es una copia del puntero, así que avanzar con s = s->next no cambia la pila de quien la llama. Una pila vacía devuelve -1 sin entrar en el bucle.

Por qué funciona tan bien con rangos

Como no hay repetidos, «la primera coincidencia» es la única. Y como los valores son 0..n-1, quien la llama sabe de antemano qué valor busca sin tener que calcular mínimos ni máximos:

  • sort_simple: stack_pos(a, next), el siguiente menor.
  • sort_medium: stack_pos(b, ft_lstsize(b) - 1), el mayor de b.
  • sort_low: stack_pos(a, 0), para dejar el 0 en la cima al final.

En los tres casos el valor está seguro en la pila, así que el -1 no llega a rotate_to_top_*. Si llegara, no haría nada: -1 <= size / 2 y while (pos-- > 0) no daría ninguna vuelta.

Cuesta O(n) de CPU y ninguna operación: solo mira.

Cómo funcionan rotate_to_top_a y rotate_to_top_b

rotate_to_top_a es la de arriba. La de b es idéntica cambiando la pila y las operaciones:

/* Lo mismo para b, con rb y rrb. */
void	rotate_to_top_b(t_ps *ps, int pos)
{
	int	size;

	size = ft_lstsize(ps->b);
	if (pos <= size / 2)
		while (pos-- > 0)
			rb(ps);
	else
		while (pos++ < size)
			rrb(ps);
}

Contar con pos-- y pos++

Los dos bucles usan el post-incremento: primero se compara el valor que tenía pos y después cambia. Así, el propio pos hace de contador sin variable extra:

pos = 3, arriba:   3 > 0 (pos→2)   2 > 0 (pos→1)   1 > 0 (pos→0)   0 > 0 no
                   → 3 vueltas = pos

pos = 3, size 5:   3 < 5 (pos→4)   4 < 5 (pos→5)   5 < 5 no
                   → 2 vueltas = size - pos

Qué hace con cada posición

possize 5 (size / 2 = 2)size 4 (size / 2 = 2)
0nadanada
1rara
2ra rara ra (empate: rra rra también serían 2)
3rra rrarra
4rra—

Con size impar, la posición del medio (size / 2, división entera) está más cerca por arriba: con 5, la 2 cuesta 2 ra frente a 3 rra. Con size par es un empate y el <= lo resuelve hacia ra. En los dos casos el coste es el mínimo de pos y size - pos, y nunca pasa de size / 2.

Un ejemplo de la traza de sort_low

a: 4 0 1 3   (size 4), el hueco del 2 está en la posición 3
3 <= 2 no  →  while (3 < 4)  →  una sola rra
a: 3 4 0 1

Casos límite

  • pos = 0: ya está en la cima, no imprime nada.
  • Pila vacía: size = 0, pos (0 o −1) cae en la primera rama y no se hace nada.
  • Calcula ft_lstsize en cada llamada, que recorre la pila: CPU, no operaciones.
Qué te obliga a aprender — Que una pila con rotaciones es en realidad un anillo: el fondo está a un rra de la cima, así que la distancia real a una posición es el mínimo de ir por arriba o por abajo. Este medio anillo de ahorro es lo que separa una estrategia que pasa el corte de una que no.

08--simple: selección, O(n²)

Fichero: sort_simple.cFunciones: sort_simple, is_sorted
void	sort_simple(t_ps *ps)
{
	int	next;

	next = 0;
	while (ps->a && !is_sorted(ps->a))
	{
		rotate_to_top_a(ps, stack_pos(ps->a, next));
		pb(ps);
		next++;
	}
	while (ps->b)
		pa(ps);
}
Cómo funciona is_sorted
/* 1 si la pila ya esta ordenada de menor (cima) a mayor. */
static int	is_sorted(t_list *s)
{
	while (s && s->next)
	{
		if (*(int *)s->content > *(int *)s->next->content)
			return (0);
		s = s->next;
	}
	return (1);
}

Mirar solo a los vecinos

Recorre la pila de la cima al fondo comparando cada nodo con el siguiente. Si encuentra una pareja al revés (el de arriba mayor que el de abajo), ya sabe que la pila no está ordenada y devuelve 0 en ese momento, sin mirar el resto. Si llega al final sin encontrar ninguna, devuelve 1.

a: 0 1 3 2 4
   0 < 1   bien
   1 < 3   bien
   3 > 2   al revés → return (0), el 4 ni se mira

Basta con comparar vecinos por la transitividad: si a ≤ b y b ≤ c, entonces a ≤ c. Si cada número es menor que el siguiente, toda la pila está en orden, y no hace falta comparar todos con todos. Por eso cuesta O(n) y no O(n²) como compute_disorder, que sí cuenta todas las parejas porque necesita saber cuánto desorden hay, no solo si lo hay.

La condición s && s->next

Hace dos cosas a la vez:

  • s: si la pila está vacía (NULL), no entra en el bucle y devuelve 1. Una pila vacía se considera ordenada.
  • s->next: hace falta un siguiente para poder comparar. Con un solo nodo tampoco entra, y un único número siempre está ordenado. Además evita leer s->next->content sobre un NULL.

El orden importa: && evalúa de izquierda a derecha y se para en el primer falso (evaluación en cortocircuito), así que s->next solo se lee cuando ya se sabe que s no es NULL.

El *(int *)s->content

En t_list, content es un void *: un puntero sin tipo, que no se puede desreferenciar tal cual. Primero se convierte a int * (porque cada nodo guarda la dirección de un int) y luego se desreferencia con * para obtener el número.

Dónde se usa

Es static: solo existe dentro de sort_simple.c. En el bucle de sort_simple sirve de salida temprana: en cuanto lo que queda en a está ordenado, deja de sacar números y pasa a devolverlos. Se llama en cada vuelta y cada llamada recorre la pila, pero no mueve nada ni escribe operaciones, así que no suma al recuento que se puntúa.

main no la usa: para saber si la entrada ya venía ordenada mira ps.mistakes > 0, que ya se ha calculado para el desorden. Las dos respuestas coinciden, porque una pila sin ninguna pareja al revés es exactamente una pila ordenada.

Ordenación por selección adaptada a pilas. Gracias a los rangos, el menor que queda en a es siempre next: se localiza, se sube por el camino corto y se pasa a b. En cuanto lo que queda en a ya está ordenado, se para. Al final b tiene los menores con el mayor arriba, así que basta con pa hasta vaciarla. Traza real con --simple 5 4 3 2 1 (rangos 4 3 2 1 0), 12 operaciones:

     a: 4 3 2 1 0     b:
rra  a: 0 4 3 2 1     b:
pb   a: 4 3 2 1       b: 0
rra  a: 1 4 3 2       b: 0
pb   a: 4 3 2         b: 1 0
rra  a: 2 4 3         b: 1 0
pb   a: 4 3           b: 2 1 0
ra   a: 3 4           b: 2 1 0
pb   a: 4             b: 3 2 1 0
pa   a: 3 4           b: 2 1 0
pa   a: 2 3 4         b: 1 0
pa   a: 1 2 3 4       b: 0
pa   a: 0 1 2 3 4     b:

Se ve cómo funciona la parada: is_sorted se comprueba al principio de cada vuelta, así que el 3 se sube (ra) y se empuja aunque tras el ra la pila 3 4 ya estuviera ordenada; en la vuelta siguiente a = 4 sí lo está y se sale.

Cada búsqueda + rotación cuesta hasta n/2 y se hace hasta n veces: O(n²). Afinando: de media la rotación cuesta un cuarto de lo que queda en a, y a va encogiendo de n a 1, así que salen unas n²/8 rotaciones más los n pb y n pa: n²/8 + 2n, que da 1450 para 100 y 32 250 para 500. Medido sobre 10 entradas aleatorias: ~1440 para 100 números y ~32500 para 500 (muy lejos de los 12000 del corte, como cabe esperar de un O(n²)).

Qué te obliga a aprender — La estrategia de referencia, y por eso la más instructiva al medirla: con 100 números pasa el corte, con 500 se dispara. Es Big-O hecho visible: la misma idea que parece razonable con poca entrada deja de servir al crecer. También enseña a buscar salidas tempranas (is_sorted) que no cambian la complejidad pero sí ahorran trabajo real.

09--complex: radix binario, O(n log n)

Fichero: sort_complex.cFunciones: sort_complex
	bit = 0;
	while ((ps->size - 1) >> bit)
	{
		i = 0;
		while (i < ps->size)
		{
			if ((*(int *)ps->a->content >> bit) & 1)
				ra(ps);
			else
				pb(ps);
			i++;
		}
		while (ps->b)
			pa(ps);
		bit++;
	}
Qué hacen >> y & 1

Todo el radix descansa en una sola expresión: (n >> bit) & 1, que significa «dame el bit número bit de n», y vale 0 o 1. Son dos operadores de bits trabajando juntos.

>>: desplazar a la derecha

n >> k corre los bits de n k posiciones hacia la derecha: los k bits de menos peso se caen por el borde y por la izquierda entran ceros. Para un número no negativo equivale a dividir entre 2k (división entera), igual que en decimal quitar la última cifra es dividir entre 10:

n = 6          110
6 >> 1  =  3    011     (6 / 2)
6 >> 2  =  1    001     (6 / 4)
6 >> 3  =  0    000     (ya no quedan bits)

Desplazar sirve para traer el bit que te interesa a la posición 0, la de más a la derecha.

& 1: quedarse con el último bit

& es el AND bit a bit: compara los dos números columna a columna y deja un 1 solo donde los dos tienen un 1. Como 1 en binario es …0001, hacer x & 1 borra todos los bits menos el último. Es una máscara:

    110   (6)            011   (3)
  & 001   (1)          & 001   (1)
  -----                -----
    000   → 0, par         001   → 1, impar

x & 1 es la forma de bits de preguntar x % 2: 1 si es impar, 0 si es par.

Juntos: leer un bit concreto

Primero se desplaza para poner el bit buscado al final y luego se enmascara para quedarse solo con él. Con n = 6 (110):

bit6 >> bit& 1en el radix
0110 = 60pb
1011 = 31ra
2001 = 11ra

En la traza de abajo, con 2 0 3 1 (en binario 10 00 11 01), la pasada del bit 0 manda a b el 2 y el 0, cuyo último bit es 0, y deja en a el 3 y el 1. La del bit 1 manda a b los que tienen el bit de las «dos unidades» a 0: el 0 y el 1.

La condición del bucle: (size - 1) >> bit

El mayor rango es size - 1. Mientras al desplazarlo quede algo distinto de 0, aún le quedan bits por mirar; cuando da 0, ya se han recorrido todos y la pila está ordenada. Así el número de pasadas es justo el número de bits del mayor rango:

size 4     mayor 3   = 11        →  2 pasadas
size 100   mayor 99  = 1100011   →  7 pasadas
size 500   mayor 499 = 111110011 →  9 pasadas

Por qué hace falta normalizar antes

Con los números originales esto no funcionaría bien. Un negativo se guarda en complemento a dos, con el bit más alto a 1, así que el radix lo trataría como el mayor de todos. Además, desplazar un negativo a la derecha depende de la implementación en C (normalmente entran unos, no ceros). Y con valores como 2147483647 harían falta 31 pasadas aunque solo hubiera dos números. Los rangos 0..n-1 son no negativos y tan pequeños como se puede: pocas pasadas y ningún caso raro.

Ojo con la precedencia: >> se evalúa antes que &, así que n >> bit & 1 ya funcionaría. Pero & va después de ==: n & 1 == 0 se lee como n & (1 == 0), que siempre da 0. Con operadores de bits, paréntesis siempre, como hace el código.

Radix LSD en base 2 sobre los rangos. En cada bit, empezando por el de menos peso, se recorre a entera: los que tienen ese bit a 0 van a b (pb) y los que lo tienen a 1 se quedan (ra). Después se devuelve todo con pa. La condición del bucle, (size - 1) >> bit, da tantas pasadas como bits tiene el mayor rango. Traza real con --complex 2 0 3 1 (dos bits, dos pasadas, 12 operaciones):

         a: 2 0 3 1    b:          bit 0: pares a b
pb       a: 0 3 1      b: 2
pb       a: 3 1        b: 0 2
ra       a: 1 3        b: 0 2
ra       a: 3 1        b: 0 2
pa       a: 0 3 1      b: 2
pa       a: 2 0 3 1    b:          (pares delante, impares detrás)
ra       a: 0 3 1 2    b:          bit 1: los < 2 a b
pb       a: 3 1 2      b: 0
ra       a: 1 2 3      b: 0
pb       a: 2 3        b: 1 0
pa       a: 1 2 3      b: 0
pa       a: 0 1 2 3    b:

La primera pasada deja la pila igual que al principio, y no es un error: en 2 0 3 1 los pares ya iban delante de los impares. Y aunque b invierte el orden al apilar, los pa lo vuelven a invertir, de modo que dentro de cada grupo se conserva el orden de llegada: el algoritmo es estable, que es justo lo que necesita un radix LSD para que, tras el último bit, a quede ordenada.

Hay ⌈log₂ n⌉ pasadas y cada una cuesta como mucho 2n operaciones. Además el número de operaciones no depende de la entrada, solo de su tamaño: 1084 para 100 números y 6784 para 500, siempre (es exactamente la cifra del ejemplo del enunciado).

Qué te obliga a aprender — Operaciones de bits (>> y & 1) usadas para algo real, y el concepto de estabilidad: sin él, el radix no funciona. También que O(n log n) es una garantía, no siempre lo mejor: radix hace sus pasadas completas aunque la lista llegue casi ordenada, y con 100 números queda por encima de los chunks. Por eso la adaptativa no lo usa para todo.

10--medium: chunks, la "mariposa", O(n√n)

Fichero: sort_medium.cFunciones: sort_medium, push_chunks, isqrt

La idea en una frase: meter todo en b medio ordenado y luego sacar siempre el mayor, que estará cerca de la cima o del fondo. Son dos fases:

  1. Ida, de a a b (push_chunks). Se recorre a con una ventana de rangos [0, i + range], donde i es cuántos van ya en b y range ≈ 1.5·√n. Por cada cima v de a:
    CondiciónQué significaAcción
    v > i + rangedemasiado grande para meterlo todavíara y mirar el siguiente
    i < v <= i + rangeestá en la ventanapb: se queda arriba de b
    v <= ien la ventana y ya pequeño para el momentopb + rb: al fondo de b
    Cada pb sube i, así que la ventana se desliza: no hay bloques fijos.
  2. Vuelta, de b a a. Con a vacía, b tiene exactamente los rangos 0..tamaño-1, así que el mayor es siempre tamaño - 1: se sube por el camino corto y pa. Como salen de mayor a menor, a se construye ordenada desde abajo (8, 7 8, 6 7 8…).

La primera fase deja b con forma de mariposa: los grandes cerca de los dos extremos y los pequeños en el centro (en la traza de abajo, 8 6 7 · 3 1 0 2 · 4 5). Gracias a eso, en la segunda fase el mayor siempre está a una o dos rotaciones de la cima.

Primera fase: pasar todo a b por tramos de unos 1.5·√n rangos.

static void	push_chunks(t_ps *ps, int range)
{
	int	i;
	int	v;

	i = 0;
	while (ps->a)
	{
		v = *(int *)ps->a->content;
		if (v <= i + range)
		{
			pb(ps);
			if (v <= i)
				rb(ps);
			i++;
		}
		else
			ra(ps);
	}
}

i cuenta cuántos van ya en b. La cima de a entra si su rango es <= i + range (está en el tramo actual); si además es <= i, es de los pequeños del tramo y se manda al fondo de b con rb; si no está en el tramo, ra y se mira el siguiente. Siempre hay alguno que entra: el menor que queda en a es <= i. La ventana avanza a medida que se empuja, así que nadie espera más de un tramo de rotaciones.

Cómo funciona push_chunks

El código es el de arriba. Su comentario:

/*
** Pasa todo a b por tramos. i cuenta cuantos van ya en b; se acepta la cima
** de a si su rango es <= i + range (esta en el tramo actual):
**   - si ademas es <= i, es de los pequenos del tramo: pb y rb, abajo de b
**   - si no, pb y se queda arriba
**   - si no esta en el tramo, ra y se mira el siguiente
** Siempre hay alguno en el tramo: el menor que queda en a es <= i. Asi b
** queda como una "mariposa": los grandes cerca de la cima, los pequenos
** abajo, y sacar el mayor cada vez es barato.
*/

Traza decisión a decisión

Con la entrada de la traza de abajo, 5 1 8 3 0 7 2 6 4 (ya son rangos) y range = 4. Cada fila es una vuelta del bucle:

cima vii + range¿entra?¿v <= i?ops
504no—ra
104sínopb
815no—ra
315sínopb
026sísípb rb
737sínopb
248sísípb rb
659sínopb
4610sísípb rb
5711sísípb rb
8812sísípb rb

16 operaciones (2 ra, 9 pb, 5 rb) y b queda 6 7 3 1 0 2 4 5 8, la que se ve al principio de la traza de la tarjeta.

Una ventana que se desliza, no tramos fijos

No se reparten los números en bloques fijos (0–3, 4–7…). El límite i + range sube uno con cada pb, así que el tramo avanza en cuanto entra alguien. Los que están por encima de la ventana esperan con ra, y los que ya quedaron por debajo (v <= i) son «pequeños para el momento» y bajan al fondo de b con rb. Los de la parte alta de la ventana se quedan arriba. De ahí la forma de mariposa: lo grande se acumula hacia los dos extremos de b y lo pequeño, en el centro.

Por qué el bucle siempre acaba

Hace falta que, por muchos ra que se hagan, alguna cima llegue a entrar. Tras i empujes, b tiene i números, así que como mucho hay i valores menores que el mínimo de a: ese mínimo es <= i y entra seguro. En el peor caso se da casi una vuelta entera de a antes de llegar a él, pero nunca se queda girando.

Casos límite

El desperdicio de la regla ya está en la tarjeta: el último elemento siempre cumple v <= i y recibe un rb que la segunda fase deshace con rrb, y un 0 que entre el primero recibe un rb sobre una b de un nodo, que no mueve nada pero cuenta.

Segunda fase: devolverlos de mayor a menor.

void	sort_medium(t_ps *ps)
{
	push_chunks(ps, isqrt(ps->size) * 3 / 2);
	while (ps->b)
	{
		rotate_to_top_b(ps, stack_pos(ps->b, ft_lstsize(ps->b) - 1));
		pa(ps);
	}
}

b contiene exactamente los rangos 0..tamaño-1, así que su mayor es ft_lstsize(ps->b) - 1; se sube por el camino corto y pa. isqrt es una raíz entera a base de probar (r + 1) * (r + 1) <= n, sin math.h. Traza real con --medium 5 1 8 3 0 7 2 6 4 (9 números, isqrt(9) * 3 / 2 = 4). Al final de la primera fase:

pb       a: 8                    b: 5 6 7 3 1 0 2 4
rb       a: 8                    b: 6 7 3 1 0 2 4 5
pb       a:                      b: 8 6 7 3 1 0 2 4 5
rb       a:                      b: 6 7 3 1 0 2 4 5 8
rrb      a:                      b: 8 6 7 3 1 0 2 4 5
pa       a: 8                    b: 6 7 3 1 0 2 4 5
rb       a: 8                    b: 7 3 1 0 2 4 5 6
pa       a: 7 8                  b: 3 1 0 2 4 5 6
rrb      a: 7 8                  b: 6 3 1 0 2 4 5
pa       a: 6 7 8                b: 3 1 0 2 4 5
...

Ahí se ve la mariposa: b queda con los grandes cerca de los dos extremos (6 7 arriba, 4 5 abajo) y los pequeños en el centro (1 0 2), así que el mayor siempre está a una o dos rotaciones de la cima. La traza enseña también un pequeño desperdicio de la regla: el último elemento (8, con i = 8) cumple v <= i, se manda al fondo con rb y el paso siguiente lo vuelve a subir con rrb. Algo parecido ocurre si el primero en entrar es el 0: su rb se hace sobre una b de un solo nodo, que no mueve nada pero cuenta (pasa con --medium 1 3 2, que sale en 9 operaciones). Son una o dos operaciones por ejecución.

Medido sobre 10 entradas aleatorias: ~570 para 100 números (por debajo de 700, nivel excelente) y ~5060 para 500 (por debajo de 5500, también excelente). Es la estrategia que mejor puntúa de las cuatro con entradas aleatorias.

Cómo funciona isqrt
/* Raiz cuadrada entera: el mayor r con r * r <= n. */
static int	isqrt(int n)
{
	int	r;

	r = 1;
	while ((r + 1) * (r + 1) <= n)
		r++;
	return (r);
}

Probar el siguiente

Empieza en 1 y sube mientras el siguiente candidato, al cuadrado, siga cabiendo en n. Se para en el último r que cumple r · r <= n, que es la raíz redondeada hacia abajo. Sin sqrt de math.h y sin decimales:

n = 9:    2·2 = 4 <= 9   r = 2
          3·3 = 9 <= 9   r = 3
          4·4 = 16 > 9   para → 3

n = 500:  … 22·22 = 484 <= 500   r = 22
          23·23 = 529 > 500       para → 22

Da unas √n vueltas: 22 para 500, nada.

El tamaño del tramo que sale

sizeisqrtisqrt * 3 / 2
2, 311
523
934
1001015
5002233

El orden de isqrt(ps->size) * 3 / 2 importa, porque todo es división entera: se multiplica primero (22 · 3 = 66) y se divide después (66 / 2 = 33). Escrito 3 / 2 * isqrt(…), el 3 / 2 daría 1 y el factor 1.5 desaparecería.

Casos límite

Ojo: como r empieza en 1, isqrt(0) devuelve 1 y no 0. Aquí no importa, porque sort_medium solo se ejecuta con al menos dos números. Y (r + 1) * (r + 1) solo desbordaría un int con n cerca de INT_MAX, muy lejos de los tamaños de push_swap.

Qué te obliga a aprender — De dónde sale un √n: si los tramos son de tamaño k, cada elemento espera hasta k rotaciones (n·k en total) y hay n/k tramos; el equilibrio está en k ≈ √n. El factor 1.5 es un ajuste empírico de esa constante. Y enseña a pensar en la forma que deja una fase para la siguiente: la mariposa no es un accidente, es lo que hace barata la vuelta.

11sort_low: LIS + inserción, O(n) con poco desorden

Fichero: sort_low.cFunciones: sort_low, lis_lengths, lis_keep, push_non_lis, insert_pos

El método de la adaptativa para desorden < 0.2. Si la lista está casi ordenada, casi todo está ya en su sitio; lo que se puede dejar quieto es la subsecuencia creciente más larga (LIS): esos elementos ya están en orden entre sí.

static void	lis_lengths(int *vals, int n, int *len, int *prev)
{
	...
		len[i] = 1;
		prev[i] = -1;
		j = 0;
		while (j < i)
		{
			if (vals[j] < vals[i] && len[j] + 1 > len[i])
			{
				len[i] = len[j] + 1;
				prev[i] = j;
			}
			j++;
		}
	...
}

La LIS clásica en O(n²): len[i] es el largo de la mejor subsecuencia creciente que acaba en i y prev[i] de dónde viene. lis_keep parte del final más largo y retrocede por prev marcando un array keep; un detalle de ahorro: len y prev van en un solo malloc de 2n y la primera mitad se reutiliza como keep. Todo esto se calcula sobre una copia y no mueve las pilas.

Cómo funciona lis_lengths
/*
** len[i] = largo de la subsecuencia creciente mas larga que acaba en i,
** prev[i] = el elemento anterior en esa subsecuencia (-1 si no hay).
** Es O(n^2) en tiempo de calculo, pero no mueve las pilas (lo que puntua
** son las operaciones).
*/
static void	lis_lengths(int *vals, int n, int *len, int *prev)
{
	int	i;
	int	j;

	i = 0;
	while (i < n)
	{
		len[i] = 1;
		prev[i] = -1;
		j = 0;
		while (j < i)
		{
			if (vals[j] < vals[i] && len[j] + 1 > len[i])
			{
				len[i] = len[j] + 1;
				prev[i] = j;
			}
			j++;
		}
		i++;
	}
}

La idea: aprovechar lo ya calculado

Una subsecuencia creciente que acaba en i es, o bien solo vals[i] (largo 1), o bien una que acaba en algún j anterior con vals[j] < vals[i], alargada con vals[i]. Como len[j] ya está calculado para todos los j < i, basta con probar cada uno y quedarse con el que dé más: len[i] = max(len[j] + 1). Eso es programación dinámica: cada respuesta se construye con respuestas más pequeñas ya guardadas. prev[i] apunta qué j dio ese máximo, para poder reconstruir la subsecuencia después.

Tabla con un ejemplo

La entrada 2 1 3 6 5 8 de la sección 13 se normaliza a 1 0 2 4 3 5:

ivals[i]lenprevpor qué
011−1no hay nada antes
101−1ningún anterior es menor que 0
2220desde el 1 (j = 0); el 0 (j = 1) también daría 2, pero no supera
3432desde el 2, que tenía len 2
4332desde el 2; el 4 no es menor que 3
5543desde el 4 (3 + 1); el 3 también daría 4, pero no supera

La condición del if

  • vals[j] < vals[i]: solo se puede alargar una subsecuencia que acabe en un número menor, si no dejaría de ser creciente.
  • len[j] + 1 > len[i]: solo se cambia si mejora. Al ser estricta, en un empate se queda el primer j que alcanzó el máximo. Por eso en la fila 5 gana el 4 y no el 3.

Coste

El bucle interno da i vueltas para cada i: 0 + 1 + … + (n − 1) = n(n − 1)/2, 124 750 comparaciones para 500 números. Es O(n²) de CPU y cero operaciones. Existe una LIS en O(n log n), pero aquí no aporta nada porque el tiempo no puntúa.

Cómo funciona lis_keep
/*
** Array keep: keep[i] = 1 si el elemento en la posicion i esta en la LIS.
** Se parte del final mas largo y se va hacia atras con prev. len y prev van
** en un solo malloc (prev es la segunda mitad) y la primera mitad se
** reutiliza como keep. NULL si falla malloc.
*/
static int	*lis_keep(int *vals, int n)
{
	int	*len;
	int	*prev;
	int	best;
	int	i;

	len = malloc(sizeof(int) * n * 2);
	if (!len)
		return (NULL);
	prev = len + n;
	lis_lengths(vals, n, len, prev);
	best = 0;
	i = 0;
	while (++i < n)
		if (len[i] > len[best])
			best = i;
	ft_bzero(len, sizeof(int) * n);
	while (best >= 0)
	{
		len[best] = 1;
		best = prev[best];
	}
	return (len);
}

1. Un malloc para dos arrays

Se reservan 2n enteros y prev = len + n apunta a la mitad: con aritmética de punteros, len + n es la dirección n enteros más allá.

len                       prev = len + n
 │                          │
 ▼                          ▼
[ len[0] … len[n-1] ][ prev[0] … prev[n-1] ]

2. Dónde acaba la LIS más larga

best empieza en 0 y el bucle mira desde i = 1 (el ++i incrementa antes de comparar). Con > estricto se queda con el primer índice de largo máximo. Siguiendo el ejemplo de 1 0 2 4 3 5:

len  = 1 1 2 3 3 4
best = 0 → 2 → 3 → 5   (en i = 1 y i = 4 no supera)

3. Reconstruir hacia atrás y marcar

A partir de aquí len ya no hace falta, así que se pone a cero con ft_bzero y se reutiliza como keep. prev está en la otra mitad y no se toca. Luego se sigue la cadena de prev desde best hasta el −1, marcando un 1 en cada posición:

prev = -1 -1 0 2 2 3

best = 5   keep[5] = 1   prev[5] = 3
best = 3   keep[3] = 1   prev[3] = 2
best = 2   keep[2] = 1   prev[2] = 0
best = 0   keep[0] = 1   prev[0] = -1  → fin

keep = 1 0 1 1 0 1     LIS: 1 2 4 5     fuera: el 0 y el 3

La cadena sale del final al principio, pero no importa: se marcan posiciones, no se escribe la subsecuencia en orden.

Un detalle con el free

Devuelve len, que es el puntero que dio malloc. Cuando sort_low hace free(keep) se libera el bloque entero de 2n, prev incluido. No se podría hacer free(prev): no es una dirección que haya devuelto malloc.

Casos límite

  • Si falla malloc devuelve NULL y sort_low pasa a sort_medium.
  • Con n = 1 el bucle de best no da vueltas y sale keep = { 1 }. No llega a pasar: sort_low solo se ejecuta con al menos una pareja al revés, es decir, con dos números o más.

Luego, push_non_lis recorre a: los de la LIS se quedan (ra) y el resto va a b (pb). Cuenta antes cuántos hay fuera (left) para parar en cuanto sale el último, sin dar la vuelta entera.

Cómo funciona push_non_lis
/*
** Recorre a desde la cima: los de la LIS se quedan (ra) y el resto va a b
** (pb). Primero cuenta cuantos no son de la LIS (left) para parar en cuanto
** ha pasado el ultimo, sin dar la vuelta entera.
*/
static void	push_non_lis(t_ps *ps, int *keep)
{
	int	left;
	int	i;

	left = 0;
	i = 0;
	while (i < ps->size)
		left += !keep[i++];
	i = 0;
	while (left > 0)
	{
		if (keep[i++])
			ra(ps);
		else
		{
			pb(ps);
			left--;
		}
	}
}

1. Contar los que sobran

!keep[i] vale 1 si keep[i] es 0 y 0 si es 1, así que left += !keep[i++] suma uno por cada elemento fuera de la LIS sin necesitar un if. Con keep = 1 0 1 1 0 1, left = 2.

2. Por qué keep[i] siempre habla de la cima

keep se calculó con las posiciones originales de a, y la pila se va moviendo. Pero en cada vuelta la cima, o pasa al fondo (ra), o se va a b (pb), y en los dos casos la nueva cima es el siguiente de la lista original. Así que la cima de la vuelta i es siempre el elemento que estaba en la posición i, y basta con avanzar i una vez por vuelta.

         a: 1 0 2 4 3 5    b:        keep = 1 0 1 1 0 1, left = 2
i = 0    keep 1  ra   a: 0 2 4 3 5 1    b:
i = 1    keep 0  pb   a: 2 4 3 5 1      b: 0      left = 1
i = 2    keep 1  ra   a: 4 3 5 1 2      b: 0
i = 3    keep 1  ra   a: 3 5 1 2 4      b: 0
i = 4    keep 0  pb   a: 5 1 2 4        b: 3 0    left = 0 → fin
                      (el 5, i = 5, ni se visita)

3. Lo que queda en a

Solo los de la LIS, en su orden original, aunque rotados: 5 1 2 4 leído como un anillo es 1 2 4 5. Por eso insert_pos puede tratar a como «ordenada, quizá rotada».

Coste

Se hacen tantos ra como elementos de la LIS haya antes del último que sobra, más un pb por cada uno de fuera: como mucho n operaciones. Siempre avanza con ra, nunca con rra, así que un único elemento fuera de sitio a mitad de la lista ya cuesta unas n/2 rotaciones, y su reinserción otras tantas. Con 1..100 y el 50 y el 51 intercambiados salen 102 operaciones (50 ra, 50 rra, un pb y un pa).

Y cada uno de b vuelve a su hueco en a:

static int	insert_pos(t_list *a, int v)
{
	...
	best = LONG_MAX;
	while (a)
	{
		key = *(int *)a->content;
		if (key < v)
			key += INT_MAX;
		if (key < best)
		{
			best = key;
			pos = i;
		}
		...
	}
	return (pos);
}

El hueco de v está encima del menor de a que sea mayor que v; si no hay ninguno mayor (v es el nuevo máximo), encima del menor de todos. El truco hace las dos búsquedas en una: a los menores que v se les suma INT_MAX (en un long, para no desbordar), así que solo pueden ganar el mínimo si no hay ningún mayor, y entre ellos gana el más pequeño. Funciona aunque a esté rotada.

Cómo funciona insert_pos
/*
** Donde hay que meter v en a (que esta ordenada, quiza rotada): encima del
** menor que sea mayor que v. Si no hay ninguno mayor, encima del menor de
** todos. Las dos cosas a la vez: a los <= v se les suma INT_MAX para que
** solo ganen si no hay ninguno mayor, y se busca el minimo.
*/
static int	insert_pos(t_list *a, int v)
{
	long	key;
	long	best;
	int		pos;
	int		i;

	best = LONG_MAX;
	pos = 0;
	i = 0;
	while (a)
	{
		key = *(int *)a->content;
		if (key < v)
			key += INT_MAX;
		if (key < best)
		{
			best = key;
			pos = i;
		}
		a = a->next;
		i++;
	}
	return (pos);
}

Dónde va v

a es un anillo ordenado. v tiene que quedar justo antes de su sucesor, el menor de los que son mayores que él: si se sube ese a la cima y se hace pa, v queda encima y el anillo sigue ordenado. Si no hay ninguno mayor, v es el nuevo máximo y su sitio en el anillo está entre el máximo actual y el mínimo, es decir, encima del menor de todos.

El truco de INT_MAX, con números

Dos búsquedas («el menor de los mayores» y, si no hay, «el menor de todos») se convierten en un solo mínimo cambiando la clave: los menores que v se penalizan sumándoles INT_MAX. Del ejemplo de 2 1 3 6 5 8, tras push_non_lis queda a = 5 1 2 4 y toca meter el v = 3:

posvalor¿< 3?key
05no5
11sí1 + 2147483647 = 2147483648
22sí2 + 2147483647 = 2147483649
34no4 ← mínimo
pos 3 de 4  →  rra   a: 4 5 1 2
pa                   a: 3 4 5 1 2

Después viene el v = 0, con a = 3 4 5 1 2: ninguno es menor que 0, ninguna clave se penaliza y gana el 1, en la posición 3 de 5 (rra rra, pa → 0 1 2 3 4 5). Y el caso del nuevo máximo, con 10 0 1 2 … 9: el 10 es el único fuera de la LIS, y al reinsertarlo en a = 0 1 … 9 todos son menores, todas las claves llevan + INT_MAX y gana la del 0, en la posición 0. Se hace pa sin rotar, queda 10 0 1 … 9 y el ra final que sube el 0 lo deja ordenado: 3 operaciones en total.

Por qué INT_MAX y por qué long

Basta con que cualquier clave penalizada sea mayor que cualquier clave sin penalizar. Los valores son rangos menores que n, así que sumar n ya serviría, pero INT_MAX vale para cualquier int no negativo sin pensar en el tamaño. El precio es que 1 + INT_MAX no cabe en un int (desbordaría, y eso es comportamiento indefinido); por eso key y best son long. best empieza en LONG_MAX para que la primera clave siempre gane y pos siempre salga de algún nodo.

Casos límite

  • a vacía: devolvería 0. No ocurre: tras push_non_lis en a queda como mínimo la LIS, que tiene al menos un elemento.
  • Ojo: el comentario dice «a los <= v», pero el código usa key < v. Es equivalente, porque v está en b y ningún valor de a puede ser igual a él.

Al final se sube el 0 a la cima. Traza real con 0 1 3 2 4 (desorden 10 %, 8 operaciones):

         a: 0 1 3 2 4    b:      LIS = 0 1 3 4, fuera: 2
ra       a: 1 3 2 4 0    b:
ra       a: 3 2 4 0 1    b:
ra       a: 2 4 0 1 3    b:
pb       a: 4 0 1 3      b: 2    left = 0: se para sin rotar el 4
rra      a: 3 4 0 1      b: 2    hueco de 2: encima del 3 (pos 3 de 4)
pa       a: 2 3 4 0 1    b:
rra      a: 1 2 3 4 0    b:      subir el 0 (pos 3 de 5)
rra      a: 0 1 2 3 4    b:

Entre las dos LIS de largo 4 (0 1 3 4 y 0 1 2 4) gana la primera, porque la comparación len[j] + 1 > len[i] es estricta y se queda con el primer j que alcanza el máximo. Si falla malloc, sort_low cae en sort_medium, que no necesita memoria extra.

Con k elementos fuera de la LIS, el paso de empujar cuesta como mucho n y la reinserción hasta k·n/2: O(n + k·n), que es O(n) cuando k es pequeño. Con 500 números y 25 intercambios entre vecinos (desorden 0.02 %), una prueba dio 918 operaciones; el radix habría hecho sus 6784 de siempre.

Qué te obliga a aprender — Programación dinámica (la LIS es el ejemplo de libro) aplicada a una pregunta concreta: ¿qué es lo máximo que puedo no tocar? Y la diferencia entre coste de cálculo y coste puntuado: aquí se gasta O(n²) de CPU en pensar para ahorrar operaciones, que es lo único que cuenta. El truco de INT_MAX es una lección de diseño de claves de comparación: codificar dos criterios en un solo número para resolverlo con un único mínimo.

12--adaptive, la estrategia por defecto

Fichero: sort_adaptive.cFunciones: sort_adaptive
void	sort_adaptive(t_ps *ps)
{
	int	regime;

	regime = disorder_regime(ps);
	if (regime == 0)
		sort_low(ps);
	else if (regime == 1)
		sort_medium(ps);
	else
		sort_complex(ps);
}
DesordenMétodoClase pedida
d < 0.2LIS + inserción (sort_low)O(n)
0.2 ≤ d < 0.5chunks (sort_medium)O(n√n)
d ≥ 0.5radix (sort_complex)O(n log n)

Los umbrales vienen del enunciado, que fija qué clase de complejidad toca en cada régimen, y el código los respeta a rajatabla. El README justifica por qué encajan: por debajo de 0.2 casi todo está en su sitio y conviene un método que no mueva lo que ya está bien; una lista aleatoria tiene un desorden de alrededor de 0.5, y por encima la entrada parece aleatoria o invertida y radix da una cota garantizada; en medio, los chunks se adaptan mejor.

La consecuencia, visible en las cifras: con entradas aleatorias el desorden ronda 0.5 y cae a veces en medium y a veces en complex, así que la media de la adaptativa queda entre las dos. Medido sobre 10 entradas aleatorias de 0 a 9999 (todas OK en el checker):

Estrategia100 números500 números
--simple~1443~32476
--medium~571~5061
--complex10846784
por defecto~926~5871

Por defecto, pues, queda en el nivel "bueno" del enunciado (menos de 1500 y de 8000), no en el excelente que sí alcanza --medium. Con el ejemplo del enunciado, ARG="4 67 3 87 23" (desorden 40 %, régimen medio), da 13 operaciones, la misma cifra que el ejemplo.

Con listas muy cortas la regla se nota: 2 1 tiene desorden 100 %, va a radix y sale ra pb pa (3 operaciones, donde un sa bastaría), y 3 2 1 se resuelve en 10. No hay casos especiales para n pequeño: el código aplica siempre el régimen.

Qué te obliga a aprender — Que no hay un algoritmo mejor para todo: el rendimiento depende de la forma de la entrada, y medir esa forma antes de elegir es lo que hacen los ordenadores de verdad (Timsort, el sort de Python y Java, se basa justo en aprovechar los tramos ya ordenados). También a documentar decisiones: el enunciado exige justificar los umbrales y el análisis de complejidad en el README.

13--bench

Fichero: bench.cFunciones: print_bench, put_disorder, put_strategy, put_count

Todo sale por el fd 2: stdout queda solo con las operaciones, que es lo que lee el checker, y así --bench no lo estropea. El porcentaje con dos decimales se imprime sin float:

static void	put_disorder(t_ps *ps)
{
	long	p;

	p = 0;
	if (ps->pairs)
		p = (ps->mistakes * 10000 + ps->pairs / 2) / ps->pairs;
	ft_putstr_fd("[bench] disorder:  ", 2);
	ft_putnbr_fd(p / 100, 2);
	ft_putchar_fd('.', 2);
	ft_putchar_fd('0' + p % 100 / 10, 2);
	ft_putchar_fd('0' + p % 10, 2);
	ft_putendl_fd("%", 2);
}

p es el desorden en centésimas de porcentaje (1 = 0.01 %). El + pairs / 2 hace que la división entera redondee en vez de truncar: con 1 de 3, (10000 + 1) / 3 = 3333, que se imprime como 33.33%. Luego p / 100 es la parte entera y los dos dígitos de p % 100 se escriben uno a uno, para no perder el cero de 10.05.

Cómo funciona put_disorder

El código es el de arriba. Lo que hace, por partes:

1. Escalar y redondear

Un porcentaje con dos decimales es un número de diezmilésimas: 33.33 % = 0.3333 = 3333 / 10000. Así que se multiplica mistakes por 10000 antes de dividir (si se dividiera primero, mistakes / pairs daría 0 en casi todos los casos). Sumar pairs / 2 al numerador es sumar medio divisor, y convierte el truncado de la división entera en un redondeo al más cercano:

CasoSin redondeoCon + pairs / 2Sale
1 de 310000 / 3 = 333310001 / 3 = 333333.33%
2 de 320000 / 3 = 666620001 / 3 = 666766.67%
2 de 1520000 / 15 = 133320007 / 15 = 133313.33%
1 de 495010000 / 4950 = 212475 / 4950 = 20.02%
3 de 330000 / 3 = 1000030001 / 3 = 10000100.00%

«2 de 3» es 3 1 2, «2 de 15» es el 2 1 3 6 5 8 de abajo y «1 de 4950» son los números del 1 al 100 con dos vecinos intercambiados; todos comprobados con --bench.

2. Partir en parte entera y decimales

Con p = 2 (el 0.02 %):

p / 100        = 0    →  "0"
'.'                   →  "."
p % 100 / 10   = 0    →  "0"
p % 10         = 2    →  "2"
                         "0.02%"

Si se imprimiera p % 100 con ft_putnbr_fd, saldría 0.2%: el cero de las décimas se perdería. Escribir cada cifra como '0' + dígito garantiza siempre dos. (% y / tienen la misma precedencia y van de izquierda a derecha, así que p % 100 / 10 es (p % 100) / 10.)

Casos límite

  • pairs == 0 (un solo número): no se puede dividir entre 0, así que el if lo salta y p se queda en 0: 0.00%.
  • Desbordamiento: con 500 números, mistakes llega como mucho a 124 750, y por 10000 son unos 1 250 millones, que cabe en un long sobradamente.
  • p / 100 va de 0 a 100 y se pasa a ft_putnbr_fd, que recibe un int: la conversión de long no pierde nada.

put_strategy imprime nombre y clase; con la adaptativa recalcula disorder_regime para decir qué método usó de verdad. El total es la suma de los once contadores. Salida real con el ejemplo del enunciado:

$ ./push_swap --bench 4 67 3 87 23 > /dev/null
[bench] disorder:  40.00%
[bench] strategy:  Adaptive / O(n√n)
[bench] total_ops:  13
[bench] sa:  0  sb:  0  ss:  0  pa:  5  pb:  5
[bench] ra:  0  rb:  2  rr:  0  rra:  0  rrb:  1  rrr:  0

Y con una entrada casi ordenada, donde entra sort_low:

$ ./push_swap --bench 2 1 3 6 5 8 > /dev/null
[bench] disorder:  13.33%
[bench] strategy:  Adaptive / O(n)
[bench] total_ops:  10
[bench] sa:  0  sb:  0  ss:  0  pa:  2  pb:  2
[bench] ra:  3  rb:  0  rr:  0  rra:  3  rrb:  0  rrr:  0

Si la lista ya está ordenada, el bench se imprime igual con disorder: 0.00% y total_ops: 0.

Cómo funciona put_strategy
/*
** Nombre de la estrategia y su clase de complejidad. Con adaptive, la clase
** depende del regimen que eligio sort_adaptive, asi que se vuelve a
** calcular igual que alli.
*/
static void	put_strategy(t_ps *ps)
{
	int	regime;

	ft_putstr_fd("[bench] strategy:  ", 2);
	regime = disorder_regime(ps);
	if (ps->strategy == SIMPLE)
		ft_putendl_fd("Simple / O(n²)", 2);
	else if (ps->strategy == MEDIUM)
		ft_putendl_fd("Medium / O(n√n)", 2);
	else if (ps->strategy == COMPLEX)
		ft_putendl_fd("Complex / O(n log n)", 2);
	else if (regime == 0)
		ft_putendl_fd("Adaptive / O(n)", 2);
	else if (regime == 1)
		ft_putendl_fd("Adaptive / O(n√n)", 2);
	else
		ft_putendl_fd("Adaptive / O(n log n)", 2);
}

Seis salidas en una cadena

Primero las tres forzadas, que tienen clase fija. Si no es ninguna, la estrategia es la adaptativa y la clase depende del régimen:

ps->strategyregimeImprime
SIMPLE(da igual)Simple / O(n²)
MEDIUM(da igual)Medium / O(n√n)
COMPLEX(da igual)Complex / O(n log n)
ADAPTIVE0Adaptive / O(n)
ADAPTIVE1Adaptive / O(n√n)
ADAPTIVE2Adaptive / O(n log n)

Por qué se puede recalcular el régimen

sort_adaptive no guarda en ps qué método eligió. Pero no hace falta: disorder_regime solo depende de mistakes y pairs, que se midieron antes de mover nada y no cambian, así que aquí da exactamente la misma respuesta que dio allí.

Detalles

  • El régimen se calcula siempre, aunque la estrategia sea forzada y no se use. Es una comparación de enteros y no tiene efecto.
  • ² y √ no son ASCII: en UTF-8 ocupan 2 y 3 bytes. ft_putendl_fd los escribe byte a byte tal cual, y es la terminal la que los muestra como un solo carácter.
  • Ojo: dice el método que correspondería, no si se ejecutó. Con una lista ya ordenada no se ejecuta ninguno, pero sale Adaptive / O(n), y con un solo número (pairs == 0) sale Adaptive / O(n log n); se explica en disorder_regime.
Cómo funciona put_count
/* "nombre:  n" seguido de end (separador o salto de linea). */
static void	put_count(char *name, int n, char *end)
{
	ft_putstr_fd(name, 2);
	ft_putstr_fd(":  ", 2);
	ft_putnbr_fd(n, 2);
	ft_putstr_fd(end, 2);
}

Un contador con su separador

Escribe un trozo nombre: n y, detrás, lo que diga end. Toda la gracia está en ese tercer parámetro: print_bench la llama once veces y con end decide si detrás va un hueco o un cambio de línea.

put_count("sa", 0, "  ")              "sa:  0  "
put_count("pb", 5, "\n[bench] ")      "pb:  5\n[bench] "
put_count("rrr", 0, "\n")             "rrr:  0\n"

Cómo salen las dos líneas

print_bench escribe "\n[bench] " después del total y luego cinco contadores: los cuatro primeros con " " y pb con "\n[bench] ", que es el salto de línea y, ya pegado, el prefijo de la siguiente. Después van los otros seis, y rrr cierra con "\n":

[bench] total_ops:  13
[bench] sa:  0  sb:  0  ss:  0  pa:  5  pb:  5
[bench] ra:  0  rb:  2  rr:  0  rra:  0  rrb:  1  rrr:  0

Si el separador fuera siempre " ", cada línea acabaría con dos espacios de sobra y el salto y el prefijo habría que escribirlos aparte. Con end, el último de cada línea cierra la suya y abre la siguiente.

Todo va por el fd 2, como el resto del informe, y los contadores se leen de ps->count indexando con el enum: ps->count[SA], ps->count[PB]…

Qué te obliga a aprender — Para qué existen stdout y stderr por separado: datos por un canal, diagnóstico por otro, y una tubería (| ./checker_linux) que solo ve los datos. Y aritmética de punto fijo: escalar por 10000, redondear sumando la mitad del divisor y partir el resultado con / y %, la misma técnica con la que se manejan céntimos en software financiero para no fiarse de la coma flotante.

14Rendimiento frente a los cortes

Probado con: extra/checker_linuxFecha: 01-11-2026

El enunciado fija cuántas operaciones se permiten con 100 y 500 números aleatorios, y en la evaluación se comprueba con el checker que se da como recurso del proyecto:

NúmerosPasa (mínimo)BuenoExcelente
100< 2000< 1500< 700
500< 12000< 8000< 5500

Lo que saca este push_swap con cada estrategia: 20 entradas aleatorias por tamaño (semillas fijas, valores en todo el rango de int), todas con OK del checker. El nivel se cuenta con el peor caso, no con la media:

Estrategia100: media100: peorNivel500: media500: peorNivel
--simple14481619pasa3198433629no pasa
--medium580602excelente50385132excelente
--complex10841084bueno67846784bueno
sin flag (--adaptive)8581084bueno58136784bueno

Cómo leerla:

Entradas pequeñas y casi ordenadas

El enunciado no pone cortes para listas cortas, pero en las evaluaciones se suelen probar a mano. Peor caso de todas las permutaciones posibles, con todas dando OK:

Peor cason = 2n = 3n = 4n = 5
--simple361014
--medium5121320
--complex3101225
sin flag3101325

Como referencia, 2 números se ordenan siempre con 1 operación como mucho (sa), 3 con 2 como mucho, y en las evaluaciones con 5 se suele esperar 12 o menos. Ninguna estrategia trata aparte las listas cortas ni usa sa, y ahí se nota.

Casi ordenadas (vecinos intercambiados en 0..n-1), sin flag:

100 números, 1 intercambio     104 operaciones
100 números, 5 intercambios    154
100 números, 25 intercambios   196
500 números, 1 intercambio     504
500 números, 5 intercambios    808
500 números, 25 intercambios   1000

Es el régimen de sort_low: muy por debajo del radix, pero un solo intercambio cuesta unas n operaciones, porque push_non_lis recorre a con ra hasta el elemento descolocado.

Qué te obliga a aprender — A medir en vez de suponer: la complejidad dice cómo crece el coste, pero los cortes se ganan o se pierden por las constantes, como el 1.5·√n de los tramos. Y a mirar el peor caso además de la media, porque en la evaluación sale una entrada concreta, no la media de veinte.

15Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado a fondo. Están agrupadas en: diseño, algoritmos, entrada y errores, y puntos débiles. Antes de mirar la respuesta, intenta contestar tú.

Diseño

¿Por qué cambias los números por su rango antes de ordenar?

Porque el orden relativo no cambia, así que ordenar los rangos 0..n-1 es ordenar los números, y a cambio todo es más sencillo: «el menor que queda» es el siguiente rango (--simple), «los k menores» son 0..k-1 (--medium), y el radix puede leer los bits de números pequeños y no negativos (--complex). De paso, normalize detecta los duplicados. → 05

¿Por qué listas enlazadas y no arrays?

Las pilas son t_list de la libft, que ya estaba hecha y probada. pa/pb y sa/sb son O(1) porque solo mueven punteros o intercambian contents. ra y rra recorren la lista hasta el final y cuestan O(n) de CPU, pero eso no importa: el proyecto puntúa el número de operaciones, no el tiempo. → 01, 02

¿Cómo calculas el desorden y por qué no usas float?

Para cada par (i, j) con i antes que j se suma 1 a pairs, y si a[i] > a[j], 1 a mistakes. El desorden es mistakes / pairs. Para comparar con 0.2 y 0.5 se multiplica en lugar de dividir (mistakes * 5 < pairs), y para imprimirlo con dos decimales se escala por 10000. Todo con enteros: exacto y sin depender de la coma flotante. → 06, 13

¿Por qué --bench escribe por stderr?

Porque el checker lee stdout y solo acepta nombres de operaciones. Si el informe saliera por stdout, ./push_swap --bench … | ./checker_linux … daría Error. Por stderr se ve en pantalla y la tubería solo recibe las operaciones. → 13

Algoritmos

Sin flag, ¿qué algoritmo se ejecuta?

El que toca según el desorden medido antes de mover nada: menos de 0.2, sort_low (LIS + inserción, O(n) cuando hay poco desorden); menos de 0.5, sort_medium (chunks, O(n√n)); a partir de 0.5, sort_complex (radix, O(n log n)). Si ya está ordenada, nada. → 12, disorder_regime

Explícame --medium. ¿Por qué es O(n√n)?

Ida: se pasan los números a b con una ventana de rangos [0, i + range] que se desliza con cada pb (range ≈ 1.5·√n); los que ya son pequeños para el momento bajan al fondo con rb, y b queda en forma de mariposa. Vuelta: el mayor de b es siempre tamaño - 1; se sube por el camino corto y pa. Cada número espera como mucho el ancho de la ventana (unas √n rotaciones), y son n números: n·√n. → 10

¿Por qué el radix siempre hace 1084 operaciones con 100 números?

Porque no mira la entrada: hace una pasada por cada bit del mayor rango (99 tiene 7 bits, así que son 7 pasadas), y en cada una recorre a entera (100 ra o pb) y devuelve con pa los que mandó a b. Lo único que cambia con la entrada es cuántos van a b en cada pasada, y con rangos 0..n-1 eso también está fijado. Funciona porque es estable. → 09, >> y & 1

¿Qué es la LIS y por qué sirve cuando hay poco desorden?

La subsecuencia creciente más larga: el mayor grupo de números que ya están en orden entre sí, aunque no estén seguidos. Esos se dejan quietos, se sacan a b los demás (pocos, si hay poco desorden) y se reinsertan uno a uno en su hueco. Con 0 1 3 2 4 la LIS es 0 1 2 4 o 0 1 3 4, y solo hay que mover un número. → 11, lis_keep

¿Cómo decides entre ra y rra?

Por el camino más corto: si el elemento está en la mitad de arriba (pos <= size / 2), ra pos veces; si no, rra size - pos veces. Nunca cuesta más de size / 2. → rotate_to_top

Entrada y errores

¿Qué entradas dan Error?

Un argumento que no es un número entero (abc, -, +, 1.5), un número fuera del rango de int (2147483648), un duplicado, un argumento vacío o solo con espacios (""), un flag desconocido (--simplex, --) y dos flags de estrategia. Siempre Error\n por stderr y nada por stdout. Sin argumentos, o con solo flags, no se imprime nada. → 04

¿1 01 y -0 0 son duplicados?

Sí. Los duplicados se comparan por valor, después de convertir: 01 vale 1 y -0 vale 0. Se detectan en rank_of, al normalizar. → rank_of

¿Cómo detectas que un número no cabe en un int?

to_int acumula en un long y comprueba el rango después de cada dígito, así que corta en cuanto se pasa y el long nunca llega a desbordar. -2147483648 es válido y 2147483648 no. → to_int

¿Puedo pasar los números en un solo argumento, o mezclar flags y números?

Sí a las dos cosas. "3 2 1" vale lo mismo que 3 2 1, porque cada argumento se parte por espacios. Los flags pueden ir en cualquier posición, pero cada uno tiene que ser un argumento propio: "1 --bench" es un número mal escrito. Ojo: el separador es solo el espacio, así que un tabulador da Error. → add_words

¿Hay leaks? ¿Qué pasa si falla un malloc?

Al acabar, free_ps libera las dos pilas (los nodos y el int* de cada uno), también al salir por error. Valgrind no da fugas. Si falla un malloc, la función devuelve 0 hasta main y se sale por error_exit, así que se imprime Error, igual que con una entrada inválida. → error_exit, free_ps

Puntos débiles (mejor tener la respuesta preparada)

¿Por qué 3 2 1 tarda 10 operaciones si con sa + rra bastan 2?

Porque ninguna estrategia trata aparte las listas cortas: 3 2 1 tiene un 100 % de desorden y va al radix, que hace sus pasadas completas. Lo mismo con 2 1 (3 operaciones en vez de 1) y con 5 números (hasta 25). Respuesta honesta: es una mejora pendiente, un caso especial para 2, 3 y 5 números antes de elegir estrategia. → 14

¿Por qué nunca usas sa, rr ni rrr?

Las funciones existen y funcionan, pero ningún algoritmo las llama: en --bench esos contadores salen siempre a 0. Se podrían aprovechar con sa en las listas cortas y en sort_low (dos vecinos cambiados se arreglan con una operación), y con rr/rrr cuando a y b tienen que rotar en el mismo sentido. → 02

¿Por qué sin flag sacas «bueno» y no «excelente» si --medium llega?

Con entradas aleatorias el desorden ronda 0.5, y cuando pasa de 0.5 la adaptativa elige el radix (1084 / 6784 operaciones). Es la elección que pide el enunciado, que asocia cada régimen a una clase de complejidad. Mandar también el régimen alto a sort_medium daría excelente. → 14

¿Qué estrategia dice --bench con un solo número?

«Adaptive / O(n log n)», aunque no se ejecuta ninguna: con un número, pairs es 0 y disorder_regime devuelve el régimen alto. Con una lista ya ordenada dice «Adaptive / O(n)». put_strategy recalcula el régimen sin saber si se llegó a ordenar algo. → put_strategy

Sobre el trabajo

Es un proyecto en pareja: ¿qué hizo cada uno?

Esta te la tienes que preparar tú. En la evaluación cualquiera de los dos puede tener que explicar cualquier parte del código, también la que escribió el otro. Si os piden un cambio en directo, los candidatos naturales son el caso especial de 3 números o cambiar el umbral de la adaptativa.