Requisito previo: problema de clasificación de burbujas : escriba un programa en lenguaje ensamblador en un microprocesador 8085 para clasificar una lista dada de n números utilizando la clasificación de burbujas.
Ejemplo –
Suposición: el tamaño de la lista se almacena en 2040H y la lista de números desde 2041H en adelante.
Algoritmo –
- Cargue el tamaño de la lista en el registro C y establezca el registro D en 0
- Decremento C como para n elementos Ocurren n-1 comparaciones
- Cargue el elemento inicial de la lista en Acumulador
- Comparar Acumulador y siguiente elemento
- Si el acumulador es menor o igual que el siguiente elemento, vaya al paso 8
- Intercambiar los dos elementos
- Establezca el registro D en 1
- Decremento C
- Si C>0 toma el siguiente elemento en Acumulador y ve al punto 4
- Si D = 0, esto significa que en la iteración no se produce ningún intercambio, por lo que sabemos que no se producirá en más iteraciones, por lo que se cierra el bucle y se detiene el programa.
- Vaya al paso 1 para más iteraciones
Programa –
| Dirección | Etiqueta | Instrucción | Comentario |
|---|---|---|---|
| 2000H | COMIENZO | LXI H, 2040H | Tamaño de carga de la array |
| 2003H | MVI D, 00H | Borrar el registro D para configurar una bandera | |
| 2005H | MOV C, M | Establecer registro C con número de elementos en la lista | |
| 2006H | DCR C | Decremento C | |
| 2007H | INXH | Incrementar la memoria para acceder a la lista | |
| 2008H | CONTROLAR | MOV A, M | Recuperar elemento de lista en Acumulador |
| 2009H | INXH | Incrementar la memoria para acceder al siguiente elemento | |
| 200AH | CMP M | Comparar Acumulador con el siguiente elemento | |
| 200BH | JC NEXTBYTE | Si el acumulador es menor, salte a NEXTBYTE | |
| 200EH | JZ NEXTBYTE | Si el acumulador es igual, salta a NEXTBYTE | |
| 2011H | MOV B, M | Intercambiar los dos elementos | |
| 2012H | MOV M, A | ||
| 2013H | DCXH | ||
| 2014H | MOV M, B | ||
| 2015H | INXH | ||
| 2016H | MVI D, 01H | Si se produce el intercambio, guarde 01 en el registro D | |
| 2018H | SIGUIENTEBYTE | DCR C | Decrementar C para la próxima iteración |
| 2019H | CHEQUE JNZ | Saltar a COMPROBAR si C>0 | |
| 201CH | MOV A, D | Transferir el contenido de D al acumulador | |
| 201DH | IPC 01H | Comparar el contenido del acumulador con 01H | |
| 201FH | INICIO JZ | Saltar a INICIO si D=01H | |
| 2022H | HLT | DETENER |
Explicación-
- Recuperar un elemento en el acumulador.
- Compárelo con el siguiente elemento, si es mayor, intercámbielo; de lo contrario, muévase al siguiente índice.
- Si en un ciclo completo no ha habido intercambio, deténgalo; de lo contrario, comience toda la iteración nuevamente.
- El siguiente enfoque tiene dos bucles, uno anidado dentro de otro so-
Complejidad de tiempo de peor caso y promedio: O(n*n). El peor de los casos ocurre cuando la array se ordena de forma inversa.
Complejidad temporal del mejor caso: O(n). El mejor de los casos ocurre cuando la array ya está ordenada.