REPORTE DE ALGORITMO DE ORDENAMIENTO BURBUJA - AlexDominguez18/MIPS_32_BITS GitHub Wiki
Diagrama de flujo del algoritmo a implementar (Método burbuja)
Explicación
El algoritmo método Burbuja es un método para ordenar datos, funciona comparando los datos que se quieren ordenar y determinar cuál es el menor, intercambiándolos si es necesario.
Los datos que se ordenarán, serán 5 y se cargaran en la memoria de datos.
Este algoritmo irá comparando desde la posición 0 número tras número hasta encontrar uno mayor, si este es el mayor de todo el arreglo lo llevará hasta la última posición y si no será reemplazado por uno mayor que él.
Este proceso seguirá así hasta que haya ordenado todos los datos del arreglo.
Viéndolo de una manera más sencilla: (Visualizando el arreglo como una lista) Empezamos comparando el numero que está abajo [1] con el numero de arriba [0], si el numero que está abajo es menor al que esta arriba se pasa arriba, es decir, el numero en la posición [1] se pasa a la posición [0] y viceversa, por lo que los números menores pasarán arriba y los números mayores pasarán hacia abajo, esto con el fin de ordenarlos de menor a mayor. Lo mismo se hace con las posiciones 3 y 2, 4 y 3, 5 y 4, cuando llegue a la posición 5 volverá a comparar desde el principio, así si hay un numero que debería estar en la posición 2 y está en la 4 llegará a su destino con éxito. Todo este proceso se seguirá repitiendo hasta que al compararlos todos los números estén de menor a mayor.
Es un método que funciona bien, sin embargo, tiene un gran defecto, y es que hay ocasiones en las que los números están en su posición correcta, pero al comparar uno con otro se mueven para dejar pasar a un numero de una posición mas baja o mayor, haciendo que el numero que estaba en su posición se mueva y se tenga que comparar todo el arreglo de nueva cuenta.
Programa en Ensamblador
Después de analizar como funciona el ordenamiento burbuja procedimos a hacer el algoritmo en ensamblador utilizando las instrucciones que hace nuestro procesador MIPS. Lo que hace nuestro algoritmo es ordenar las primeras 5 posiciones de la Memoria de Datos usando el método burbuja. El algoritmo quedó de la siguiente manera:
ORDENAMIENTO BURBUJA ENSAMBLADOR
--000 00000000 nop $0, $0, $0
--004 0080F820 add $31, $4, $0
--008 00000000 nop $0, $0, $0
--00c 0000F020 add $30, $0, $0
--
--010 00000000 nop $0, $0, $0
--014 8FCD0000 lw $30, $13
--018 00000000 nop $0, $0, $0
--01c 03C1E020 add $28, $30, $1
--
--020 00000000 nop $0, $0, $0
--024 8F8E0000 lw $28, $14,
--028 00000000 nop $0, $0, $0
--02c 01CD302A slt $6, $14, $13
-- --030 00000000 nop $0, $0, $0
--034 10C00003 beq $6, $0, #3
--038 AFCE0000 sw $30, $14
--03c 00000000 nop $0, $0, $0
--
--040 AF8D0000 sw $28, $13
--044 00000000 nop $0, $0, $0
--048 00000000 nop $0, $0, $0
--04c 00000000 nop $0, $0, $0
--
--050 23DE0001 add $30, $30, $1
--054 00000000 nop $0, $0, $0
--058 03DF302A slt $6, $30, $31
--05c 00000000 nop $0, $0, $0
--
--060 10C1FFEC beq $6, $1, #-20
--064 03E1F822 sub $31, $31, $1
--068 001F302A slt $6, $0, $31
--06c 10C1FFE7 beq $6, $1, #-25
--
--070 00BE7822 sub $15, $5, $30
--074 00000000 nop $0, $0, $0
Explicación de su Funcionamiento
Con la instrucción lw saca el valor de j de la Memoria de Datos y lo guarda en el registro 13, con otra lw saca j+1 y lo guarda en el registro 14 (cuadros rojos en la imagen). Una vez guardados j en $13 y j+1 en $14 con la instrucción stl compara si j+1<j, en este caso 1<3 (cuadros morados) y como esta se cumple se guarda un 1 en el registro 6 (cuadro amarillo). Después con una instrucción beq compara lo que hay en el registro 6 y en el 0 y como en este caso son distintos no se hace el salto (cuadros verdes) y continua con la siguiente instrucción, usando dos sw guarda j en la posición 0 y j+1 en la posición 1 (cuadros naranjas).
En la siguiente imagen el algoritmo vuelve a repetir las instrucciones pasadas saca j y lo guarda en $13, saca j+1 y lo guarda en $14 (cuadros rojos). Después compara con stl si j+1<j, en este caso 15<3 (cuadros morados) y en este caso no se cumple, por ello guarda un 0 en $6 (cuadro amarillo), Después con la instrucción beq compara $6 y $0 y como en este caso son iguales hace un salto (cuadros verdes) para no hacer las instrucciones sw ya que j+1 no es menor que j, en este caso 15<3 no se cumple y por eso no es necesario cambiarlos de posición.
Pruebas de su Funcionamiento
Para saber si nuestro algoritmo funciona precargamos nuestra memoria de datos en las primeras 5 posiciones con números desordenados
Al momento de hacer la simulación se obtienen los resultados deseados y se ordenan los números en la Memoria de Datos.
