Análisis de Arquitectura MIPS y Algoritmos de

Ordenamiento
Jesús Herrada -
Rafael Pérez - 30079341
Julio 2025

1. Diferencias entre Registros Temporales ($t0-$t9)

y Registros Guardados ($s0-$s7)
Los registros temporales ($t0-$t9) se usan para guardar valores temporales dentro de
funciones, por lo que no es necesario preservar su valor después de una llamada de función,
pueden sobreescribirse, y son útiles para almacenar valores de cálculos inmediatos.

Los registros guardados ($s0-$s7) se usan para guardar valores importantes que deben
mantenerse a través de llamadas a funciones, las cuales deberán guardar su valor original
y restaurarlo antes de retornar haciendo uso de las pilas ($sp).

1.1. Aplicación de la Distinción entre Registros en BubbleSort

Registros temporales($t0-$t9):
a. Calculos inmediatos:
suma inmediata: addi $t1, $a1, -1 # n-1
resta: $t3, $t1, $t0 # t3 = n-1-i
multiplicacion: $t4, $t2, 2 # t4 = j*4
b. Almacenar valores temporales:
lw $t7, 0($t5) # t7 = v[j]
lw $t8, 4($t5) # t8 = v[j+1]
#Luego se intercambian los valores de las variables en Intercambio
sw $t8, 0($t5) # v[j] = v[j+1]
sw $t7, 4($t5) # v[j+1] = v[j]

Registros Guardados($s0-$s7):
En la realización del Código Bubble Sort no se utilizaron Registros Guardados ($s0-
$s7) ya que no se implementó el uso de pilas para realizar el código, esto para evitar
aumentar el nivel de complejidad del código y los desbordamientos causados por la pila,
de modo que de haberse utilizado los registros, se implementarı́an para almacenar valores
de registros que perdurarı́an entre las funciones.

1
2. Diferencias entre Registros de Argumentos, Valo-
res de Retorno y Retorno de Dirección
a. Argumentos ($a0-$a3): usados para guardar argumentos, o los primeros paráme-
tros que se pasan a una función.
En el Bubble Sort se utilizaron para almacenar los valores del arreglo y el tamaño
del mismo.
Ejemplo:

la $a0,array
lw $a1,n

b. Valores de Retorno($v0-$v1): usados para almacenar el resultado que retorna

una función.
En el Bubble Sort se usaron para imprimir los valores del arreglo ordenado, su
tamaño, y el mensaje a imprimir.
Ejemplo:

#imprimir n
li $v0, 1
syscall
# Imprimir mensaje
li $v0, 4
la $a0, msg
syscall

c. Retorno de Dirección ($ra): guarda la dirección de retorno cuando se hace una

llamada a una función usando (jal).
En el Bubble Sort se usó al final del código para retornar a la función main en
donde se saltó y enlazó hacia la función Bubble.

3. ¿Cómo afecta el uso de registros frente a memo-

ria en el rendimiento de los algoritmos de ordena-
miento implementados?
Los Registros presentan ventajas ante el uso de Accesos a Memoria en cuanto al ren-
dimiento de los algoritmos de ordenamiento, principalmente en la velocidad de ejecución,
la eficiencia y la organización del código:

2
 Aspecto Uso de Registros ($t0- Acceso a Memoria (di-
$t9), ($s0,$s9) recciones con lw/sw)
Velocidad Muy rápido, ya que accede Más lento, ya que requiere
directamente al hardware ciclos de lectura/escritura
Repetición Ideal para variables que se Costoso si se accede muchas
usan en muchos ciclos veces por ciclo
Eficiencia en Bucles Excelente para contadores, Necesario si los datos deben
ı́ndices, comparadores conservarse a largo plazo
Persistencia entre funciones Requiere manejo de pila si La memoria ya es persisten-
se usan registros guardados te por naturaleza
($s0-$s7)

Los registros permiten almacenar y manipular datos de forma mucho más rápida que
acceder a memoria, ya que están ubicados dentro del procesador y no requieren ciclos
extra para lectura o escritura. Por eso, cuando un algoritmo como Bubble Sort utiliza
registros para manejar los ı́ndices, las variables temporales o las banderas de control, su
ejecución es más eficiente.
En cambio, las operaciones con memoria, como acceder a un arreglo para comparar o
intercambiar elemento, suelen ser más lentas, porque implican buscar la dirección, cargar
el dato, modificarlo y volver a escribirlo. Aunque es necesario acceder a memoria para
modificar el contenido del arreglo, si se abusa de ello para tareas que pueden resolverse
con registros (por ejemplo, contar o almacenar datos intermedios), el rendimiento puede
disminuir.

4. ¿Qué impacto tiene el uso de estructuras de con-

trol (bucles anidados, saltos) en la eficiencia de los
algoritmos en MIPS32?
Ciclos de ejecución
Bucles anidados: aumentan exponencialmente el número de iteraciones, lo que
incrementa los ciclos de CPU. Ejemplo: un bucle con n iteraciones dentro de otro
bucle de m iteraciones ejecutan n x m veces el cuerpo del bucle.

Saltos condicionales: (beq, bne, j, etc.) pueden generar stalls (paradas) en el

pipeline si no se predicen correctamente.

Pipeline o tuberı́a de instrucciones: es una técnica clave en procesadores mo-

dernos como MIPS que permite ejecutar múltiples instrucciones en diferentes eta-
pas, mejorando el rendimiento, (tareas en paralelo).

Rendimiento del Pipeline

MIPS32 utiliza un pipeline de 5 etapas (IF, ID, EX, MEM, WB).

Saltos (branches) causan hazards de control.

3
 Hazards (o riesgos): son situaciones en las que el pipeline de un procesador (como
en MIPS32) no pueden ejecutar la siguiente instrucción en el ciclo de reloj esperado,
causando paradas (stalls), resultados incorrectos o necesidad de retroceso. Son un
problema crı́tico en CPUs modernas porque reducen la eficiencia del paralelismo a
nivel de instrucción.

Cuando el procesador no sabe si tomar o no el salto, puede perder ciclos (branch

penalty).

Bucles muy ajustados (con muchas instrucciones de saltos) pueden degradar el

rendimiento.

Uso de registro y memoria

Bucles anidados requieren más registros para almacenar contadores temporales y
variables temporales.

Si no hay suficientes registros se usa la memoria (stack), lo que es más lento (de-
pendencia de memoria).

Optimizaciones posibles
Desenrollado de bucles (loop unrolling): reduce la sobrecarga de saltos.

Reordenamiento de instrucciones: para llenar branch delay slots.

Uso de condiciones en lugar de saltos: en algunos casos moven/movez pueden evitar

saltos.

5. ¿Cuáles son las diferencias de complejidad compu-

tacional entre el algoritmo Bubble y el algoritmo
alternativo?
Las principales diferencias que existen entre el algoritmo bubble sort y el quick sort,
que es el algoritmo alternativo elegido en cuanto a complejidad computacional es el si-
guiente:
Criterio Bubble sort Quick sort
Peor caso O(n2 ) O(n2 ) (pivote mal elegido)
Caso promedio O(n2 ) O(n log n)
Mejor caso O(n) (con optimización) O(n log n)
Estabilidad Si (no cambia elementos iguales) No (depende de la implementación)
Memoria adicional O(1) (in-place) O(n log n) (recursión)
Eficiencia práctica Lento incluso para pequeños datasets Rápido en la práctica para grandes datasets

A nivel de complejidad computacional el algoritmo de quick sort es mucho más efi-

ciente que el algoritmo de ordenamiento de burbuja debido a su estructura interna, el
algoritmo de ordenamiento rápido (quick sort) que usa el principio de “divide y vencerás”.
Su funcionamiento se basa en:

4
 Seleccionar un pivote un elemento aleatorio del array (arreglo).
Particionar el arreglo: reorganiza los elementos para que los menores que el pivote
queden a su izquierda y los mayores a su derecha.
Repite el proceso recursivamente ordenando las subparticiones izquierda y derecha.
Por otro lado bubble sort:
Compara elementos adyacentes recorriendo el arreglo del inicio hasta el final.
Compara cada par de elementos consecutivos arr[i] y arr[j+1].
Intercambia si es necesario si arr[i] ¿arr[j+1] intercambia, esto “empuja” el elemento
más grande hacia el final del arreglo (como una burbuja que sube).
Repite el proceso, cada pasada completa garantiza que el elemento más grande no
ordenado llega a su posición correcta, lo que hace recorriendo el arreglo por cada
posición y luego volviendo a verificar (ciclo doble).

¿Qué implicaciones tiene esto para la implementación en un en-

torno MIPS32?
En un entorno MIPS32, la elección entre bubble sort y quick sort tiene implicaciones
crı́ticas en rendimiento, uso de memoria, complejidad de implementación y eficiencia
energética.
Ejemplo: ordenar 100 elementos en MIPS32:
Bubble sort ≈ 1,000,000 instrucciones.
Quick sort ≈ 10,000 instrucciones (promedio).
Uso de memoria:
El algoritmo de bubble sort tiene una complejidad en espacio de O(1) ya que no
usa memoria adicional para ordenar, lo cual es ideal para sistemas con memoria
limitada (como microcontroladores MIPS embebidos) ya que no usa pila.
Mientras que quick sort tiene una complejidad en espacio de O(n log n) (recursión)
debido al uso de la pila, lo que puede provocar un desbordamiento de pila (stack
overflow) si n es muy grande.
Overhead en quick sort:
Cada llamada recursiva ocupa 16 bytes en pila (ejemplo al guardar los registros
$ra, $a0, $a1, $a2) para n = 1000 se necesitan ≈ 10,000 bytes (si la recursión es
balanceada).
Complejidad de implementación:
Dificultad en MIPS: Bubble sort tiene una dificultad baja debido a que solo usa
ciclos para su implementación lo cual es ideal para principiantes, por otro lado quick
sort tiene una dificultad avanzada que requiere manejo explı́cito de la pila para la
recursión, partición con acceso a memoria no secuenciales (ineficiente en cache) y
requiere una implementación más compleja que requiere de bastante práctica.

5
6. ¿Cuáles son las fases del ciclo de ejecución de ins-
trucciones en la arquitectura MIPS32 (camino de
datos)?
La arquitectura MIPS32 utiliza un modelo de pipeline de 5 etapas para ejecutar ins-
trucciones de manera eficiente. Cada etapa se completa en un ciclo de reloj, permitiendo
que múltiples instrucciones se solapen en diferentes fases.
Etapa Nombre Descripción Componentes claves
IF Instruction Fetch (búsqueda) Lee la instrucción desde me- PC, memoria de instrucciones (IMEM)
moria
ID Instruction Decode (decodificación) Decodifica la instrucción y Banco de registros, unidad de control
lee registros
EX Execute (ejecución) Realiza operaciones ALU, unidad de cálculo de direcciones
aritméticas/lógicas o
calcula direcciones
MEM Memory Access (acceso a memoria) Accede a datos en memoria Memoria de datos (DMEM)
(load/store)
WB Write Back (escritura) Escribe resultados en el Banco de registros
banco de registros

Detalles de cada etapa

IF (Instruction fetch): Obtiene la instrucción desde memoria. Proceso: el PC
(program counter) apunta a la dirección de la instrucción, la memoria de instruc-
ciones (IMEM) devuelve la instrucción en esa dirección. El PC se actualiza a PC +
4.

ID (Instruction decode): Decodifica las instrucciones y prepara los operandos.

Proceso: la unidad de control determina el tipo de instrucción. El banco de registros
lee los valores de los registros especificados. Para instrucciones tipo I (inmediatas)
o J (saltos), se extiende el signo del valor inmediato.

EX (execute): Ejecuta la operación. Proceso: operaciones aritméticas/lógicas: La

ALU realiza cálculos. Accesos a memoria: calcula la dirección efectiva. Saltos con-
dicionales: evalúa condicionales.

MEM (memory Access): Accede a memoria (solo para load/store). Proceso:

load (lw): lee un dato de DMEM. Store (sw): escribe un dato en DMEM. Otras
instrucciones no usan esta etapa.

WB (write back): Escribe resultados en el banco de registros. Proceso: instruc-

ciones R-type: El resultado de la ALU se escribe en un registro. Load (lw): el dato
leı́do de memoria se guarda en un registro.

Ejemplo con la instrucción add $t0, $t1, $t2

IF: Lee add $t0, $t1, $t2 desde IMEM.

ID: Decodifica add, lee $t1 y $t2.

EX: La ALU calcula $t1 + $t2.

6
 MEM: No aplica (instrucción no accede a memoria).

WB: Escribe el resultado en $t0.

7. ¿Qué tipo de instrucciones se usaron predominan-

temente en la práctica (R, I, J) y por qué?
R-type (Register)
Se usa ampliamente en operaciones aritméticas y lógicas, comparaciones internas y
manipulación de valores sin tocar memoria.

Banco de Registros: se leen dos operandos (rs, rt)

ALU (Unidad Aritmético-Lógica): Realiza la operación (add, sub, and, or, slt,
etc)

Registro Destino (rd): es donde se guarda el resultado

No accede a memoria ni modifica el PC

Componentes implicados: Multiplexores, ALU control, RegWrite.

Flujo: Buscar Valores en el Banco de Registros, enviarlos a la ALU, guardar el

resultado en un registro destino (rd).

I-type (Inmediate)
Usa Memoria de datos y desplazamientos, es muy usada en algoritmos como Bubble
Sort, que requieren desplazamientos (lw, sw, addi, bgt).

Banco de Registros: Lee un registro base (rs)

Sign Extender: amplı́a el valor inmediato

ALU: Suma Base + desplazamiento

Memoria de datos: se accede si es lw o sw

PC: se altera si es una instrucción de salto condicional (beq, bne)

Componentes implicados: ALU, MemRead / MemWrite, Branch control, RegDst

y RegWrite.

Flujo: Si es lw/sw va a la memoria. Si es beq/bne compara registros, usa ALU,

modifica PC. Si es addi: opera con ALU y registros directamente.

7
J-type (Jump)
Realiza saltos incondicionales largos (j, jal), es fundamental en modularidad, llamadas
a funciones y estructuras de control global.

Instrucción: codifica directamente una dirección de salto

PC: se actualiza con esa dirección

$ra(jal): guarda el valor de retorno

Componentes implicados: Jump control, PCSrc, RegWrite (si se guarda $ra).

8. ¿Cómo se ve afectado el rendimiento si se abusa

del uso de instrucciones de salto (j, beq, bne) en
lugar de usar estructuras lineales?
Al realizar instrucciones de salto, éstas alteran el contador de programa (PC), cam-
biando el flujo normal y lineal de la ejecución. Son necesarias para controlar ciclos y
funciones, sin embargo, su exceso puede disminuir la eficiencia causando:

a. Menor predictibilidad de flujo: muchos saltos seguidos crean bifurcaciones fre-

cuentes, lo que reduce la eficiencia del pipeline, y puede generar pausas en la eje-
cución.

b. Sobrecarga en el control del flujo: una mayor cantidad de decisiones condi-

cionales requiere más comparaciones, evaluaciones de registros y actualizaciones de
PC.

c. Rompen la linealidad del camino de datos: las estructuras lineales permiten

ejecución secuencial directa y continua, los saltos interrumpen esa secuencia, pro-
vocando cargas y cálculos extras en el camino de datos como PCSrc, multiplexores
y controladores branch/jump.

d. Mayor latencia en bucles mal optimizados: los ciclos con muchos saltos con-
dicionales mal estructurados pueden generar múltiples iteraciones innecesarias.

9. ¿Qué ventajas ofrece el modelo RISC de MIPS en

la implementación de algoritmos básicos como los
de ordenamiento?
El modelo RISC (Reduced Instruction Set Computer) que utiliza MIPS ofrece una
arquitectura limpia y eficiente que es ideal para implementar algoritmos básicos como los
de ordenamiento. Una de sus principales ventajas es que todas las instrucciones tienen un
tamaño fijo y realizan operaciones simples en un solo ciclo de reloj. Esto permite ejecutar
ciclos de comparación e intercambio —muy comunes en algoritmos como Bubble Sort—
de manera rápida y predecible.

8
 Además, el modelo RISC sigue un enfoque de carga y almacenamiento (load/store),
lo que significa que solamente las instrucciones especı́ficas acceden a la memoria. To-
das las demás trabajan directamente entre registros, reduciendo el tráfico de memoria y
mejorando el rendimiento.
Como los algoritmos de ordenamiento requieren manipular muchos valores en bu-
cles, tener 32 registros disponibles en MIPS facilita el manejo de ı́ndices, contadores y
elementos del arreglo sin necesidad de acceder constantemente a memoria RAM.
Por otro lado, el diseño uniforme de instrucciones en MIPS simplifica el control del
flujo del programa y permite optimizar fácilmente el pipeline del procesador. Esto es útil
cuando se ejecutan muchas iteraciones, ya que ayuda a mantener la velocidad y evita
cuellos de botella.
En resumen, RISC en MIPS favorece implementaciones ordenadas, rápidas y fácil-
mente depurables para algoritmos clásicos, sobre todo cuando se trabaja con estructuras
como ciclos anidados o comparaciones simples.

10. ¿Cómo se usó el modo de ejecución paso a pa-

so (Step, Step Into) en MARS para verificar la
correcta ejecución del algoritmo?
En MARS el modo de ejecución paso a paso es una herramienta muy útil que permite
verificar el correcto funcionamiento de un algoritmo o instrucción, permitiendo analizar
errores lógicos ya que permite visualizar en tiempo real el contenido de los registros y ası́
poder analizar qué error está ocurriendo internamente.
En nuestro caso, usamos esta herramienta para verificar y analizar un error lógico en
un algoritmo de bubble sort el cual le introducimos un error en una instrucción lo que
modificaba la lógica de ordenamiento, dicho algoritmo es el siguiente:

# -----------------------------------------------------------
# Funcion: bubbleSort
# Parametros:
# $a0 = direccion base del array
# $a1 = tamano del array (n)
# -----------------------------------------------------------
bubbleSort:
li $t0, 0 # i = 0 (contador del bucle externo)
addi $t1, $a1, -1 # $t1 = n - 1 (limite para el bucle externo: i < n-1)
forExterno:
bge $t0, $t1, endForExterno # Salir del ciclo si i >= n-1
li $t3, 0 # j = 0 (contador del bucle interno)
sub $t4, $a1, $t0 # $t4 = n - i
subi $t4, $t4, 3 # *** ERROR LOGICO INTRODUCIDO: $t4 = n - i - 3 ***
# Esto hara que el bucle interno termine prematuramente,
# resultando en un array NO completamente ordenado.
forInterno:
bge $t3, $t4, endForInterno # Salir del ciclo si j >= n-i-3
sll $t5, $t3, 2 # $t5 = j * 4 (desplazamiento)
add $t5, $a0, $t5 # $t5 = direccion de array[j]

9
lw $t6, 0($t5) # $t6 = array[j]
lw $t7, 4($t5) # $t7 = array[j+1]
ble $t6, $t7, endIf # Si array[j] <= array[j+1], no se intercambia
sw $t7, 0($t5) # Intercambio: array[j] = array[j+1]
sw $t6, 4($t5) # Intercambio: array[j+1] = array[j]
endIf:
addi $t3, $t3, 1 # j++
j forInterno # Regresar al inicio del bucle interno
endForInterno:
addi $t0, $t0, 1 # i++
j forExterno # Regresar al inicio del bucle externo
endForExterno:
jr $ra # Retornar de la funcion

Cuyo error lógico está en la instrucción subi $t4, $t4, 3 ya que no recorre el arreglo
hasta el final sino que lo hace hasta 3 posiciones menos, lo que provoca que el arreglo
solo se ordene hasta n-3 posiciones dejando el arreglo parcialmente ordenado, en el paso
a paso es posible visualizar hasta que numero se va actualizando el registro $t4.

11. ¿Qué herramienta de MARS fue más útil para

observar el contenido de los registros y detectar
errores lógicos?
En nuestro caso las herramientas más útiles que nos permitieron detectar y corregir
errores lógicos fueron las siguientes:

Ventana de registros
Por qué: Nos permitió ver en tiempo real como cambian los registros (especialmente
$a0, $a1, $t0 etc. . . ) durante la ejecución del programa.

Ejecución paso a paso (step):

Por qué: de igual modo nos permitió identificar exactamente en qué instrucción se
modifica un registro el cual no deberı́a ser modificado, ya que afectarı́a el flujo del
programa.

Puntos de interrupción:
Por qué: pausa la ejecución del programa en puntos crı́ticos.

La combinación de registros + paso a paso (step) + breakpoints es la más efectiva para:

Identificar que algún registro se corrompe.

corregir usando un registro temporal.

Verificar que la implementación del código se ejecute correctamente por ejemplo

ordenar un arreglo.

10
12. ¿Cómo puede visualizarse en MARS el camino de
datos para una instrucción tipo R? (por ejemplo:
add)
MARS ofrece una opción llamada MIPS X-Ray la cual es una herramienta avanzada
de visualización que proporciona una representación detallada y en tiempo real del camino
de datos durante la ejecución de instrucciones MIPS.
Funciones principales de MIPS X-Ray

Visualización dinámica del camino de datos: Muestra gráficamente el flujo de

datos y resalta en colores las partes activas del camino de datos.

Desglose detallado por etapas: Divide la ejecución en las 5 etapas clásicas del
pipeline MIPS (IF, ID, EX, MEM, WB).

Información contextual: Muestra el contenido actual de todos los registros, el

estado de la memoria y los valores que circulan por los buses.

Ejemplo con add $t0, $t1, $t2

IF: El PC envı́a la dirección a la memoria de instrucciones. La instrucción se carga

en el registro de instrucción (IR).

ID (decodificación): El opcode (0x000000 para tipo R) indica que es una opera-

ción aritmética/lógica. Los campos se separan $t1 (rs) y $t2 (rt) se leen del banco
de registros. $t0 (rd) se identifica como destino. El campo funct (ej 0x20 para add)
determina la operación en la ALU.

Ejecución (EX): Los operandos van a la ALU: $t1 por el bus A y $t2 por el bus B.
La ALU realiza la suma. El multiplexor de destino de registro selecciona rd ($t0).

MEM: Nada significativo. Las instrucciones de tipo R no acceden a memoria.

Write back (WB): El resultado de la ALU se escribe en $t0.

13. ¿Cómo puede visualizarse en MARS el camino

de datos para una instrucción de tipo I? (por
ejemplo: lw)
Ejemplo con lw $t0, 8($s1)

IF: obtención de la instrucción

El PC apunta a la dirección de la instrucción. La memoria de instrucciones envı́a
lw $t0, 8($s1) al registro de instrucciones (IR).

ID (decodificación) lectura de registro y extensión de signo

Se decodifica el opcode (10011 para lw). Se lee el valor de $s1 del banco de registros.
El offset (8) se extiende de 16 a 32 bits. Señales de control clave: ALUsrc=1 (usa
el offset extendido), MemRead=1 (habilita lectura de memoria).

11
 Ejecución (EX) cálculo de dirección
La ALU suma $s1 + offset extendido. El multiplexor de destino selecciona $t0 (rt,
no rd).

MEM lectura del dato

La memoria de datos lee el valor en la dirección calculada. Señal memRead=1 activa
la lectura. El bus de datos se ilumina.

Write back (WB) escritura en registro

El dato leı́do se escribe en $t0. Señales claves: memtoReg=1 (selecciona dato de
memoria, no de la ALU), RegWrite=1 (habilita escritura en banco de registros).

14. Justificar la elección del algoritmo alternativo

La principal razón por la que el algoritmo de QuickSort fue elegido como algoritmo
alternativo es la siguiente:

1. Alta eficiencia en promedio

Al ser una arquitectura RISC, MIPS32 se beneficia de algoritmos que minimi-

cen accesos a memoria y operaciones complejas.

Quicksort requiere menos escrituras en memoria que MergeSort, lo que lo hace

más eficiente en sistemas embebidos.

2. Menos overhead que MergeSort

MergeSort requiere manejo de arreglos auxiliares, lo que en MIPS implica más

instrucciones (lw/sw) y mayor consumo de registros.

Quicksort puede implementarse con menos llamadas a funciones auxiliares,

optimizando el uso de registros.

3. Optimización con ensamblador

La recursión en Quicksort puede optimizarse con técnicas como tail recursion

o implementarse de forma iterativa con una pila, reduciendo el overhead en
MIPS.

La partición (función principal de Quicksort) puede escribirse con instrucciones

eficientes en MIPS, como comparaciones (slt, beq) e intercambios (sw, lw).

4. Consideraciones en MIPS32

12
 Peor caso O(n²): Si el pivote se elige mal (ej: siempre el primer elemento),
Quicksort puede degradarse. Esto se mitiga con elección inteligente del pivote.

Recursión profunda: En MIPS, cada llamada recursiva consume espacio en el

stack. Si el arreglo es muy grande, puede causar stack overflow (desbordamien-
to de pila).Una solución es implementar una versión iterativa usando una pila
manual.

Aunque se pudiesen haber elegido algoritmos de ordenamiento como selection

sort o insertion sort, que no usan llamadas recursivas, evitando a si la pila, di-
chos algoritmos generan mayor cantidad de instrucciones debido a la cantidad
de swap (intercambios) que hacen, lo cuál podrı́a generar una desventaja, y a
su vez en la práctica son demasiado ineficientes.

15. Análisis y Discusión de los Resultados

La diferencia de rendimiento entre ambos el Bubble Sort y el QuickSort es evidente y
se mide por su complejidad temporal (notación Big O), que estima cómo crece el tiempo
de ejecución a medida que aumenta el número de elementos (n) a ordenar.

Bubble Sort

• Complejidad Promedio y Peor Caso [O(n2 )]: Esto significa que si dupli-
cas el número de elementos, el tiempo de ejecución se cuadruplica. Es extre-
madamente ineficiente para listas grandes.

• Complejidad Mejor Caso [O(n)]: Esto solo ocurre si la lista ya está orde-
nada, ya que solo necesita una pasada para verificarlo.

• Uso: Es un algoritmo simple de entender y enseñar, pero en la práctica solo

es útil para listas muy pequeñas o como herramienta educativa.

QuickSort

• Complejidad Promedio y Mejor Caso [O(n log n)]: Este es un creci-

miento mucho más lento y controlado que el de Bubble Sort. Lo convierte en
uno de los algoritmos de ordenamiento más rápidos y es el que se usa por
defecto en muchas implementaciones de librerı́as estándar.

• Complejidad Peor Caso [O(n2 )]: Este caso es raro y ocurre con una mala
elección del ”pivote”(por ejemplo, si la lista ya está ordenada y siempre se
elige el primer elemento como pivote). Sin embargo, se mitiga fácilmente con
técnicas como la elección de un pivote aleatorio.

13
 • Uso: Es el algoritmo de elección para ordenar grandes volúmenes de datos de
manera rápida y eficiente en memoria.

Tipo de Camino de Datos Utilizado

El çamino de datos”se refiere a cómo fluye la información y el control dentro del pro-
cesador para ejecutar las instrucciones del algoritmo.

Bubble Sort: Camino de Datos Iterativo/Secuencial

• ¿Cómo funciona?: El procesador ejecuta un conjunto de instrucciones de

forma repetitiva y predecible. Las operaciones principales son:

1. Comparar dos elementos adyacentes (usando la ALU).

2. Intercambiar los elementos si es necesario (implica operaciones de carga y

almacenamiento en memoria o registros).

3. Incrementar los contadores del bucle y saltar al inicio del mismo.

• Camino de datos predominante: Es un flujo de control lineal y repetitivo.

No requiere estructuras complejas. El hardware se enfoca en ejecutar un pe-
queño bloque de instrucciones una y otra vez, modificando las direcciones de
memoria a las que accede en cada paso.

Quicksort: Camino de Datos Recursivo / Basado en Pila (Stack)

• ¿Cómo funciona?: Quicksort es un algoritmo de tipo ”divide y vencerás”que

se implementa usando recursividad. Cada vez que la función Quicksort se lla-
ma a sı́ misma para ordenar una sub-lista, el estado actual del procesador debe
guardarse para poder volver a él más tarde.

1. Se guarda el contexto actual (dirección de retorno, variables locales como

los lı́mites de la sub-lista) en una zona especial de la memoria llamada
pila de llamadas (call stack). Esta operación se conoce como push.

2. Se ejecuta la nueva llamada recursiva con la sub-lista.

3. Cuando la llamada recursiva termina, se recupera el contexto guardado de

la pila para continuar donde se habı́a quedado. Esta operación es un pop.

Camino de datos predominante: Es un flujo no lineal y dependiente de la pi-

la. El procesador utiliza intensivamente el puntero de la pila (stack pointer) y las
operaciones de memoria asociadas (push/pop) para gestionar el anidamiento de

14
llamadas. Este manejo de la pila añade una sobrecarga, pero es lo que permite la
poderosa estrategia de ”divide y vencerás”que lo hace tan rápido

15