Semana 6 — Ordenamiento por selección, inserción y burbuja (O(n²)), merge sort (O(n log n)), archivos de texto, compiladores e intérpretes, y ciclo de vida de procesos
El ordenamiento es, junto con la búsqueda, uno de los problemas más estudiados en la historia de la computación. Se estima que más del 25% del tiempo de cómputo en aplicaciones comerciales se dedica a ordenar datos. La razón es directa: muchas operaciones posteriores —búsqueda binaria, eliminación de duplicados, generación de informes, fusión de archivos— requieren que los datos estén ordenados como precondición.
Formalmente, el problema se define así: dada una secuencia de n elementos con una relación de orden total (por ejemplo, ≤ para números), producir una permutación de la secuencia tal que los elementos queden dispuestos en orden no decreciente.
Entrada: una secuencia datos de n elementos comparables entre sí.
Salida: la misma secuencia reordenada tal que datos[0] ≤ datos[1] ≤ … ≤ datos[n-1].
Precondición: los elementos deben admitir comparación con < y ≤. Para ordenamiento in-place, la secuencia debe ser mutable (lista, no tupla).
Poscondición: la secuencia resultante es una permutación de la original (no se pierden ni se inventan elementos) y está ordenada.
En la Semana 5 estudiamos que la búsqueda binaria requiere datos ordenados como precondición, pero es dramáticamente más eficiente que la búsqueda lineal: O(log n) frente a O(n). Esta semana estudiamos el costo de cumplir esa precondición: ¿cuánto cuesta ordenar? Si ordenar cuesta O(n²) y buscar O(log n), conviene ordenar una vez y buscar muchas veces. Si ordenar cuesta O(n log n), la inversión se amortiza aún más rápido. La pregunta clave es: ¿cuántas búsquedas vamos a hacer sobre los mismos datos?
Los algoritmos de ordenamiento se clasifican según varios criterios que determinan su idoneidad para distintos contextos:
Supongamos que tenemos una lista de alumnos ya ordenada alfabéticamente y queremos reordenarla por nota. Si el algoritmo es estable, los alumnos con la misma nota quedarán en orden alfabético entre sí (el orden previo se preserva). Si es inestable, el orden entre alumnos con igual nota es impredecible.
El algoritmo de selección imita lo que haría una persona al ordenar un mazo de cartas: en cada pasada, recorre las cartas desordenadas, selecciona la menor y la coloca en su posición definitiva. Después de k pasadas, las primeras k posiciones contienen los k menores elementos en orden correcto.
for/range() vs. while: criterio de elecciónEn la Semana 3 establecimos la norma: for con range() para recorridos determinados (se conoce de antemano cuántas iteraciones se harán) y while para recorridos indeterminados (la condición de parada depende de los datos o de múltiples criterios simultáneos). En los algoritmos de ordenamiento aplicamos esta norma de forma consistente:
for/range(): el bucle externo recorre exactamente n−1 pasadas y el interno recorre desde i+1 hasta n−1.for/range(1, n) (exactamente n−1 elementos a insertar); bucle interno while (condición compuesta: j >= 0 and datos[j] > clave).while (dos condiciones: pasadas restantes y bandera de intercambio); bucle interno for/range(n-1-i) (cantidad de comparaciones determinada para cada pasada).Datos iniciales: [64, 25, 12, 22, 11]
| Pasada (i) | Sublista a explorar | pos_min | Intercambio | Estado de datos |
|---|---|---|---|---|
| 0 | [64, 25, 12, 22, 11] | 4 (valor 11) | datos[0] ↔ datos[4] | [11, 25, 12, 22, 64] |
| 1 | [25, 12, 22, 64] | 2 (valor 12) | datos[1] ↔ datos[2] | [11, 12, 25, 22, 64] |
| 2 | [25, 22, 64] | 3 (valor 22) | datos[2] ↔ datos[3] | [11, 12, 22, 25, 64] |
| 3 | [25, 64] | 3 (valor 25) | ninguno (ya en posición) | [11, 12, 22, 25, 64] |
Al comenzar la iteración i del bucle externo, las primeras i posiciones de datos contienen los i menores elementos de la secuencia original, en orden no decreciente, cada uno en su posición definitiva.
Inicialización: cuando i = 0, la zona ordenada está vacía — el invariante se cumple trivialmente.
Mantenimiento: el bucle interno encuentra el mínimo de datos[i..n-1] y lo ubica en datos[i]; así la zona ordenada crece en un elemento y el invariante se mantiene.
Terminación: cuando i = n − 1, las primeras n − 1 posiciones están correctas, y el último elemento es necesariamente el mayor — la secuencia completa está ordenada.
En la pasada i, el bucle interno realiza n − i − 1 comparaciones. El total es:
(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2 comparaciones ≈ O(n²)
Observación importante: la cantidad de comparaciones es siempre la misma, independientemente de si los datos ya estaban ordenados, desordenados o en orden inverso. La selección no se adapta al estado inicial de los datos.
No. Consideremos [3a, 3b, 1] (donde 3a y 3b son iguales pero distinguimos su orden original). En la pasada 0, el mínimo es 1 → swap con 3a → [1, 3b, 3a]. El orden relativo de los dos 3 se invirtió.
El algoritmo de inserción imita cómo se ordenan cartas en la mano: se toma cada carta nueva y se la inserta en la posición correcta dentro de las cartas ya ordenadas, desplazando las mayores hacia la derecha para hacer lugar.
La condición j >= 0 and datos[j] > clave combina dos motivos de parada: llegar al inicio de la lista (j < 0) o encontrar un elemento menor o igual a la clave (datos[j] ≤ clave). Al salir del bucle, la inspección de cuál condición se falsificó no es necesaria porque en ambos casos j + 1 es la posición correcta para insertar la clave. La evaluación en cortocircuito garantiza que datos[j] no se evalúe cuando j < 0.
A diferencia de selección, que siempre realiza O(n²) comparaciones, la inserción se adapta al grado de desorden de los datos. Si la secuencia está «casi ordenada» (pocos elementos fuera de lugar), inserción es casi lineal. Esto la hace excelente para listas pequeñas o listas casi ordenadas, razón por la cual el algoritmo sorted() de Python (Timsort) la usa internamente para sublistas cortas.
El algoritmo burbuja recorre la secuencia repetidamente, comparando pares de elementos adyacentes e intercambiándolos si están en orden incorrecto. En cada pasada, el mayor elemento «burbujea» hacia el final, como una burbuja que sube a la superficie. Después de k pasadas, los últimos k elementos están en su posición definitiva.
El bucle externo tiene dos condiciones: i < n - 1 (no se completaron todas las pasadas) y hubo_intercambio (la pasada anterior realizó al menos un swap). La bandera hubo_intercambio permite la parada temprana: si una pasada completa no realiza ningún intercambio, la secuencia ya está ordenada y no tiene sentido continuar. Esto convierte al mejor caso (datos ya ordenados) en O(n) —una sola pasada sin intercambios—. Nótese que no usamos break: la condición compuesta del while maneja ambos criterios de terminación.
| Aspecto | Selección | Inserción | Burbuja |
|---|---|---|---|
| Estrategia | Buscar el mínimo, colocarlo | Tomar el siguiente, insertarlo en su lugar | Comparar adyacentes, intercambiar si desordenados |
| Peor caso | O(n²) | O(n²) | O(n²) |
| Mejor caso | O(n²) — no se adapta | O(n) — ya ordenada | O(n) — con optimización |
| Intercambios (swaps) | O(n) — uno por pasada como máximo | O(n²) — desplazamientos (no swaps) | O(n²) — muchos swaps |
| Estabilidad | No estable | Estable | Estable |
| Memoria extra | O(1) — in-place | O(1) — in-place | O(1) — in-place |
| ¿Cuándo conviene? | Cuando los intercambios son costosos (el swap es caro) | Listas pequeñas o casi ordenadas; excelente rendimiento adaptativo | Uso pedagógico; en la práctica es superado por inserción |
Los tres algoritmos anteriores son O(n²) en el peor caso. ¿Es inevitable? No. Se puede demostrar que cualquier algoritmo de ordenamiento basado en comparaciones necesita al menos O(n log n) comparaciones en el peor caso. Esto significa que O(n log n) es un límite inferior teórico para los algoritmos comparativos —y hay algoritmos que lo alcanzan. El primero que estudiaremos es merge sort.
El paradigma divide y vencerás (divide and conquer) es una estrategia general de diseño de algoritmos que consta de tres pasos:
Merge sort es un algoritmo recursivo. La recursividad se estudia en profundidad en la Semana 8 (caso base, caso recursivo, árbol de llamadas, correctitud por inducción). Aquí la introducimos aplicada a un problema concreto: si entendemos cómo funciona merge sort, tendremos una base sólida para comprender la recursividad como paradigma general.
La idea de merge sort es elegantemente simple: dividir la secuencia por la mitad, ordenar recursivamente cada mitad, y luego fusionar (merge) las dos mitades ordenadas en una sola secuencia ordenada. El caso base es una secuencia de 0 o 1 elementos, que ya está trivialmente ordenada.
La operación de fusión toma dos secuencias ya ordenadas y produce una única secuencia ordenada. La idea es simple: comparar los primeros elementos de ambas secuencias, copiar el menor al resultado, y avanzar en la secuencia de donde se copió. Cuando una se agota, copiar el resto de la otra.
<= y no < en la comparación?Usar <= (y no <) garantiza la estabilidad del algoritmo: cuando ambos elementos son iguales, se copia primero el de la sublista izquierda, preservando el orden relativo original.
n >> 1La expresión n >> 1 (desplazamiento a la derecha de 1 bit) es equivalente a n // 2 para enteros no negativos. A nivel de la ALU, un desplazamiento de bits es una sola instrucción del procesador, mientras que la división entera puede requerir múltiples ciclos. En la Semana 1 vimos que la ALU realiza desplazamientos como operación primitiva; aquí aplicamos ese conocimiento. Si bien en Python la diferencia de rendimiento es mínima (la PVM interpreta ambas operaciones), el hábito de pensar en eficiencia a nivel de máquina es una competencia valiosa para un ingeniero.
¿Por qué merge sort es O(n log n)? Analicemos la estructura recursiva:
Total = O(n) × O(log n) = O(n log n)
Esta complejidad es la misma en el mejor, peor y caso promedio: merge sort siempre divide y siempre fusiona, sin importar el orden inicial de los datos.
Merge sort necesita crear listas auxiliares durante la fusión. En total, la memoria adicional es del orden O(n). Este es el trade-off: se gana eficiencia temporal (O(n log n) en lugar de O(n²)) pero se paga con espacio adicional. Los algoritmos cuadráticos, en cambio, son in-place (O(1) memoria extra).
Quick sort es otro algoritmo O(n log n) basado en divide y vencerás, pero con una estrategia radicalmente diferente a la de merge sort. En lugar de dividir por la mitad y luego fusionar, quick sort elige un pivote, particiona la secuencia colocando todos los menores a la izquierda y todos los mayores a la derecha, y luego ordena recursivamente cada partición. El pivote queda en su posición definitiva tras la partición —sin necesidad de una operación de fusión posterior.
En merge sort, dividir es trivial (partir por la mitad) y combinar es costoso (fusionar dos listas ordenadas). En quick sort es al revés: dividir es costoso (particionar comparando cada elemento con el pivote) y combinar es trivial (no hay que hacer nada —la concatenación de «menores + pivote + mayores» ya está ordenada).
Usemos la misma lista que en merge sort: [38, 27, 43, 3, 9, 82, 10]. Si en cada nivel elegimos como pivote el último elemento de la sublista:
Cada pivote queda en su posición definitiva inmediatamente después de la partición (marcados en verde). No se necesita una fusión posterior: la concatenación «menores + pivote + mayores» es la solución. En este ejemplo, con pivote = último elemento, las particiones quedaron razonablemente equilibradas y la recursión tuvo poca profundidad.
¿Qué sucede si la elección de pivote es consistentemente mala? Supongamos que la misma lista ya estuviese ordenada: [3, 9, 10, 27, 38, 43, 82] y usamos pivote = último. En cada paso, el pivote sería el mayor, la partición izquierda tendría n−1 elementos y la derecha estaría vacía:
Cuando el pivote es siempre el mayor (o el menor) elemento, la partición deja n−1 elementos de un lado y 0 del otro. La recursión tiene profundidad n−1 (en lugar de log n), y en cada nivel se hacen O(n) comparaciones, dando un total de O(n²). Esto ocurre, irónicamente, cuando los datos ya están ordenados y se elige el último elemento como pivote. Las estrategias para mitigar este riesgo incluyen: elegir el pivote aleatoriamente, usar la mediana de tres (primer, último y medio elemento), o cambiar a inserción para sublistas pequeñas.
La implementación anterior es conceptualmente clara pero no es in-place: crea listas menores y mayores en cada llamada recursiva, con un costo de memoria O(n) similar al de merge sort. La ventaja práctica de quick sort (memoria O(log n) usando solo la pila de recursión) se logra con la versión in-place clásica, que particiona intercambiando elementos dentro de la misma lista usando dos punteros. Esta versión se estudia en profundidad en la Semana 11.
| Aspecto | Merge Sort | Quick Sort |
|---|---|---|
| Dónde está el trabajo | En la fusión (después de recurrir) | En la partición (antes de recurrir) |
| Peor caso | O(n log n) — siempre | O(n²) — pivote malo |
| Caso promedio | O(n log n) | O(n log n) |
| Memoria auxiliar | O(n) — no in-place | O(log n) — solo la pila (versión in-place) |
| Estabilidad | Estable | No estable (en su versión in-place clásica) |
| Localidad de caché | Menor (listas auxiliares dispersas) | Mayor (opera sobre datos contiguos) |
| En la práctica | Predecible; ideal para datos en disco | Usualmente más rápido en RAM; base de qsort() en C |
| Algoritmo | Mejor caso | Caso promedio | Peor caso | Memoria | Estable |
|---|---|---|---|---|---|
| Selección | O(n²) | O(n²) | O(n²) | O(1) | No |
| Inserción | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Burbuja | O(n) | O(n²) | O(n²) | O(1) | Sí |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Python sorted() | O(n) | O(n log n) | O(n log n) | O(n) | Sí |
La función sorted() y el método .sort() de Python usan Timsort, un algoritmo híbrido diseñado por Tim Peters en 2002. Timsort combina inserción (para sublistas cortas) y merge sort (para la fusión global), aprovechando las «corridas» (runs) de elementos ya parcialmente ordenados que suelen existir en datos reales. Su mejor caso es O(n) cuando los datos ya están ordenados, y su peor caso es O(n log n). Es estable.
Hasta ahora, nuestros programas reciben datos del teclado y muestran resultados en pantalla. Esa información es volátil: desaparece cuando el programa termina. Los archivos permiten que los datos persistan más allá de la ejecución del programa, almacenándose en medios no volátiles (disco duro, SSD).
En la Semana 5 estudiamos la jerarquía de memoria: registros, caché, RAM (volátil) y disco (no volátil). Los archivos residen en el nivel más bajo de la jerarquía —son lentos de acceder pero persisten sin alimentación eléctrica. El sistema operativo gestiona todo el acceso a archivos mediante el sistema de ficheros (file system), que traduce las operaciones lógicas (abrir, leer, escribir) en operaciones físicas sobre el disco.
El trabajo con archivos sigue un patrón estricto de tres fases:
| Modo | Descripción | Si el archivo no existe | Si el archivo existe |
|---|---|---|---|
'r' | Lectura (por defecto) | Error FileNotFoundError | Lee desde el inicio |
'w' | Escritura | Lo crea | Borra el contenido previo |
'a' | Añadir (append) | Lo crea | Escribe al final |
'r+' | Lectura y escritura | Error | Lee/escribe desde el inicio |
'w'El modo 'w' destruye el contenido previo del archivo al abrirlo. Si se necesita añadir datos sin perder los existentes, usar 'a'. Este es un error frecuente y difícil de revertir: una vez borrado, el contenido no se puede recuperar (el SO marca los bloques del disco como libres).
withLa forma recomendada de trabajar con archivos en Python es mediante un context manager (gestor de contexto), que garantiza que el archivo se cierre correctamente incluso si ocurre un error durante la operación:
with internamente?La sentencia with invoca el método __enter__() del objeto archivo al entrar en el bloque y __exit__() al salir, garantizando que close() se llame siempre. A nivel del SO, cerrar un archivo libera el descriptor de archivo y vacía (flush) los datos que pudieran estar en el búfer del SO hacia el disco.
Python ofrece varias formas de leer un archivo de texto:
Los métodos read() y readlines() cargan todo el archivo en memoria RAM. Si el archivo tiene 10 GB, se necesitan 10 GB de RAM. En cambio, iterar con for linea in archivo lee una línea a la vez, usando memoria constante independientemente del tamaño del archivo. Esta diferencia es crucial en aplicaciones reales.
Veamos un programa completo que lee números de un archivo, los ordena con merge sort y escribe el resultado en otro archivo. Esto conecta los dos temas principales de la semana: ordenamiento y archivos.
Nuestro modelo de programa se extiende naturalmente al trabajo con archivos: el prólogo abre y lee los datos de entrada, la resolución aplica el algoritmo, y el epílogo escribe los resultados y presenta la salida. Las funciones leer_numeros y escribir_numeros encapsulan las operaciones de E/S, separando la lógica de acceso a archivos de la lógica algorítmica (principio de separación de responsabilidades).
En la Semana 4 introdujimos la distinción entre compiladores e intérpretes y vimos cómo Python es un caso híbrido. Esta semana profundizamos en las fases de compilación, conectando este conocimiento con nuestra comprensión de cómo el código fuente se transforma hasta llegar a la CPU.
Análisis léxico: convierte el texto fuente en una secuencia de tokens (unidades léxicas): identificadores, números, operadores, palabras clave. Es como separar una oración en palabras.
Análisis sintáctico: verifica que los tokens forman una estructura gramaticalmente válida y construye un árbol de sintaxis abstracta (AST). Es como verificar que las palabras forman una oración con sujeto, verbo y predicado.
Análisis semántico: verifica el significado: que las variables estén declaradas, que las operaciones sean válidas entre los tipos involucrados, que el alcance sea correcto.
Generación de código: traduce el AST a instrucciones del procesador destino (código máquina) o a un formato intermedio (bytecode).
disComo vimos en la Semana 4, CPython compila nuestro código a bytecode y luego lo interpreta. Podemos observar el bytecode de una función de ordenamiento:
El swap de Python datos[i], datos[j] = datos[j], datos[i] se traduce en múltiples instrucciones de bytecode: primero carga ambos valores del lado derecho (LOAD_FAST + BINARY_SUBSCR), los rota en la pila con ROT_TWO, y luego los almacena en las posiciones inversas (STORE_SUBSCR). La PVM ejecuta cada instrucción secuencialmente —a diferencia de un procesador moderno que puede ejecutar múltiples instrucciones en paralelo (pipeline).
Cuando ejecutamos nuestro programa de ordenamiento, el sistema operativo crea un proceso para gestionarlo. Comprender el ciclo de vida de un proceso nos permite entender por qué un programa «se cuelga», qué sucede cuando leemos un archivo (el proceso se bloquea esperando el disco), y cómo el SO multiplexa la CPU entre múltiples programas.
Un proceso transita por cinco estados fundamentales durante su vida:
Cada operación de lectura —ya sea archivo.read(), archivo.readline() o la iteración con for linea in archivo— provoca que el proceso pase de EJECUCIÓN a BLOQUEADO: la CPU no puede continuar hasta que el disco (o el SSD) entregue los datos solicitados. El SO aprovecha este tiempo para despachar otro proceso que esté en estado LISTO. Cuando los datos están disponibles, nuestro proceso vuelve a LISTO y eventualmente retoma la ejecución. Este ciclo es invisible para el programador, pero explica por qué los programas que acceden mucho al disco son más lentos: no es que la CPU sea lenta, es que el proceso pasa mucho tiempo bloqueado esperando E/S.
Si el archivo cabe en la memoria RAM disponible, la estrategia óptima es leerlo completo a memoria (una transición EJECUCIÓN → BLOQUEADO → LISTO), ordenar en RAM sin más bloqueos de E/S, y escribir el resultado (otra transición). Esto es lo que hacemos con archivo.read() o archivo.readlines(), y es viable para archivos de tamaño moderado (hasta cientos de MB en máquinas actuales). Minimizar las transiciones a BLOQUEADO es un principio general de diseño eficiente.
Pero ¿qué ocurre si el archivo no cabe en RAM? Un registro de transacciones de 50 GB no puede cargarse en una máquina con 16 GB de memoria. Aquí la iteración línea a línea (for linea in archivo), que recomendamos en la sección 9.4, resuelve la lectura —pero no el ordenamiento: los algoritmos que estudiamos (selección, inserción, burbuja, merge sort) asumen que todos los datos están en RAM simultáneamente.
El ordenamiento externo es la familia de algoritmos diseñados para ordenar datos que no caben en memoria principal. El paradigma clásico es una adaptación directa de merge sort, lo que muestra la versatilidad del enfoque divide y vencerás.
El patrón de acceso de merge sort es secuencial: tanto en la lectura de las corridas como en la fusión, se recorren los datos de principio a fin. Esto se alinea perfectamente con las características del disco, que es rápido para lecturas secuenciales pero extremadamente lento para accesos aleatorios (seek). Los algoritmos cuadráticos (selección, burbuja) requerirían accesos aleatorios constantes al disco, y quick sort necesita particionar sobre posiciones arbitrarias. Merge sort es el algoritmo de elección para ordenamiento externo porque su naturaleza secuencial minimiza los costosos seeks de disco.
Durante el ordenamiento externo, el proceso alterna continuamente entre EJECUCIÓN (comparar y decidir qué elemento copiar) y BLOQUEADO (esperar datos del disco o esperar que la escritura se complete). En cada pasada de fusión se leen y se escriben todos los datos, generando una enorme cantidad de E/S. Por eso, minimizar el número de pasadas (fusionando más de dos corridas a la vez — fusión k-way) es una optimización crucial en la práctica.
Apliquemos las cuatro fases de Pólya al problema completo: «Dado un archivo notas.txt con un número de legajo y una nota separados por coma en cada línea, producir un archivo notas_ordenadas.txt con los datos ordenados por nota de mayor a menor».
Entrada: archivo notas.txt con formato legajo,nota por línea (ej: 12345,8).
Salida: archivo notas_ordenadas.txt con las mismas líneas ordenadas por nota descendente.
Casos de análisis:
La implementación sigue exactamente la descomposición del diseño. Cada función tiene su docstring con precondiciones y poscondiciones. Se usa merge sort porque necesitamos estabilidad (alumnos con igual nota mantienen el orden original del archivo).
Ejecutar el programa con cada caso de análisis definido en la Fase 1 y comparar la salida esperada con la obtenida. Verificar que el archivo de salida tiene el mismo número de líneas que el de entrada (no se pierden registros) y que las notas están en orden no creciente.
Esta semana hemos completado el binomio fundamental de la algoritmia: búsqueda (Semana 5) y ordenamiento (Semana 6). Estudiamos tres algoritmos cuadráticos —selección, inserción y burbuja— que, a pesar de su ineficiencia para grandes volúmenes, son conceptualmente reveladores: cada uno ilustra una estrategia diferente (seleccionar, insertar, intercambiar) y exhibe propiedades distintas (adaptabilidad, estabilidad, cantidad de swaps). Merge sort nos mostró que la barrera O(n²) no es inevitable: la estrategia divide y vencerás logra O(n log n) al precio de memoria auxiliar O(n). Quick sort, con la misma complejidad promedio, ofreció una perspectiva complementaria donde el trabajo se concentra en la partición y no en la fusión, pero también nos mostró que una mala elección de pivote puede degradar el rendimiento a O(n²).
Los archivos de texto nos abrieron la puerta a la persistencia de datos: leer, procesar y escribir información que sobrevive al programa. El context manager with garantiza un manejo seguro de recursos, y la iteración línea a línea permite procesar archivos de cualquier tamaño con memoria constante. Cuando los datos no caben en RAM, el ordenamiento externo —basado en merge sort— muestra que la elección del algoritmo depende no solo de la complejidad teórica sino también de la interacción con la jerarquía de memoria.
En el plano holístico, las fases de compilación nos mostraron el camino completo del código fuente hasta la CPU, y el ciclo de vida de procesos nos explicó por qué las operaciones de E/S (como leer un archivo) hacen que nuestro programa «espere» —y cómo el SO aprovecha esa espera para ejecutar otros procesos.
El rendimiento de un algoritmo de ordenamiento no depende solo de su complejidad teórica. La localidad de referencia afecta el uso de la caché: inserción accede a posiciones contiguas (buena localidad espacial), mientras que merge sort crea y recorre listas auxiliares que pueden no estar contiguas en memoria (peor localidad). A nivel del SO, ordenar un archivo que no cabe en RAM requiere ordenamiento externo, donde los datos se leen y escriben en disco por bloques —y aquí merge sort es la base de los algoritmos de ordenamiento externo porque su patrón de acceso secuencial se adapta bien a las características del disco.
Las fases de compilación (análisis léxico, sintáctico, semántico, generación de código) son el puente entre el código fuente que escribimos y el bytecode que la PVM interpreta. Cada vez que ejecutamos python ordenamiento.py, CPython realiza estas fases internamente antes de comenzar la ejecución. El ciclo de vida del proceso nos muestra que nuestro programa no vive en aislamiento: comparte la CPU con otros procesos, y las operaciones de E/S (como leer un archivo) causan transiciones de estado que el SO gestiona transparentemente.
Algoritmos de Ordenamiento y Archivos de Texto — Semana 6
Desarrollo de Contenidos — Algoritmia y Programación — Carrera de Informática