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.
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:
| Clase | n = 100 | n = 500 | crece | medido 100 | medido 500 | crece |
O(n²), --simple | 10 000 | 250 000 | ×25 | ~1443 | ~32476 | ×22.5 |
O(n√n), --medium | 1 000 | 11 180 | ×11.2 | ~571 | ~5061 | ×8.9 |
O(n log n), --complex | 664 | 4 483 | ×6.8 | 1084 | 6784 | ×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.
02Las 11 operaciones
Ficheros: swap.c, push.c, rotate.c, rotate_reverse.cAutor de push.c: gabgalla
| Operación | Efecto |
sa / sb / ss | intercambia los dos primeros de a / b / ambas |
pa / pb | pasa la cima de b a a / la de a a b |
ra / rb / rr | rota hacia arriba: la cima pasa al fondo |
rra / rrb / rrr | rota 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
| Argumentos | ps->strategy | Se ejecuta |
| ningún flag | ADAPTIVE (0, por el ft_bzero) | sort_adaptive |
--adaptive | ADAPTIVE | sort_adaptive |
--simple | SIMPLE | sort_simple |
--medium | MEDIUM | sort_medium |
--complex | COMPLEX | sort_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
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.
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'.
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
| Flag | Letras | n |
--bench | 7 | 8 |
--simple, --medium | 8 | 9 |
--complex | 9 | 10 |
--adaptive | 10 | 11 |
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é pasa | node | Resultado |
falla el malloc del int | (no llega) | return 0 |
to_int rechaza la palabra | NULL | free(value), return 0 |
falla ft_lstnew | NULL | free(value), return 0 |
| todo bien | nodo nuevo | al 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.
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:
- 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ón | Qué significa | Acción |
v > i + range | demasiado grande para meterlo todavía | ra y mirar el siguiente |
i < v <= i + range | está en la ventana | pb: se queda arriba de b |
v <= i | en la ventana y ya pequeño para el momento | pb + rb: al fondo de b |
Cada pb sube i, así que la ventana se desliza: no hay bloques fijos.
- 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 v | i | i + range | ¿entra? | ¿v <= i? | ops |
| 5 | 0 | 4 | no | — | ra |
| 1 | 0 | 4 | sí | no | pb |
| 8 | 1 | 5 | no | — | ra |
| 3 | 1 | 5 | sí | no | pb |
| 0 | 2 | 6 | sí | sí | pb rb |
| 7 | 3 | 7 | sí | no | pb |
| 2 | 4 | 8 | sí | sí | pb rb |
| 6 | 5 | 9 | sí | no | pb |
| 4 | 6 | 10 | sí | sí | pb rb |
| 5 | 7 | 11 | sí | sí | pb rb |
| 8 | 8 | 12 | sí | 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
size | isqrt | isqrt * 3 / 2 |
| 2, 3 | 1 | 1 |
| 5 | 2 | 3 |
| 9 | 3 | 4 |
| 100 | 10 | 15 |
| 500 | 22 | 33 |
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:
i | vals[i] | len | prev | por qué |
| 0 | 1 | 1 | −1 | no hay nada antes |
| 1 | 0 | 1 | −1 | ningún anterior es menor que 0 |
| 2 | 2 | 2 | 0 | desde el 1 (j = 0); el 0 (j = 1) también daría 2, pero no supera |
| 3 | 4 | 3 | 2 | desde el 2, que tenía len 2 |
| 4 | 3 | 3 | 2 | desde el 2; el 4 no es menor que 3 |
| 5 | 5 | 4 | 3 | desde 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:
| pos | valor | ¿< 3? | key |
| 0 | 5 | no | 5 |
| 1 | 1 | sí | 1 + 2147483647 = 2147483648 |
| 2 | 2 | sí | 2 + 2147483647 = 2147483649 |
| 3 | 4 | no | 4 ← 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.
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:
| Caso | Sin redondeo | Con + pairs / 2 | Sale |
| 1 de 3 | 10000 / 3 = 3333 | 10001 / 3 = 3333 | 33.33% |
| 2 de 3 | 20000 / 3 = 6666 | 20001 / 3 = 6667 | 66.67% |
| 2 de 15 | 20000 / 15 = 1333 | 20007 / 15 = 1333 | 13.33% |
| 1 de 4950 | 10000 / 4950 = 2 | 12475 / 4950 = 2 | 0.02% |
| 3 de 3 | 30000 / 3 = 10000 | 30001 / 3 = 10000 | 100.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->strategy | regime | Imprime |
SIMPLE | (da igual) | Simple / O(n²) |
MEDIUM | (da igual) | Medium / O(n√n) |
COMPLEX | (da igual) | Complex / O(n log n) |
ADAPTIVE | 0 | Adaptive / O(n) |
ADAPTIVE | 1 | Adaptive / O(n√n) |
ADAPTIVE | 2 | Adaptive / 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.
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.