Saltar al contenido
Codifíca.me | Desarrollo web | Programación

Ensamblador | Algoritmo de la burbuja

2 abril, 2012

En este ejemplo utilizamos el algoritmo de la burbuja para ordenar un Vector de 100 elementos y lo hemos codificado utilizando código ensamblador (x86-64).

Este código ordena un vector de 100 elementos utilizando el algoritmo de la burbuja, la funcionalidad desde la que hemos codificado las instrucciones en código ensamblador sería así:

Cada uno de los 100 elementos lo vamos a comparar con cada uno de los otros 99 elementos restantes, y después de cada comparación vamos a ir cambiando la posición de los elementos a la posición más adelantada dependiendo de si A es más grande que B

Para probarlo necesitamos tener un vector con 100 elementos, y pasarle la posición de memoria en la que empieza el vector a través de la variable Vector, cada elemento del vector será un número entero (32 bits) así que tendremos que ir recorriendo el vector de 4 bytes en 4 bytes para ir accediendo a los distintos elementos.

En código Java sería parecido a este:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void ordenarBurbuja (){
	int vector[]=	new int[100];
	vector[0]=101; //ponemos los valores
	vector[1]=64;
	vector[2]=45;
//	...
//	...
	vector[99]=8;
	int i,posicion,cambio;
 
//bucles	
	  for (i=0; i<100; i++) {
	    for (posicion=i+1; posicion<100; posicion++) {
	      if (vector[posicion]>vector[i]) {  
	    	  cambio=vector[posicion];         
	    	  vector[posicion]=vector[i];
	    	  vector[i]= cambio;
	      }
	    }
	  }
	}
}

Este es el código hecho en ensamblador, lo podemos llamar desde un fichero hecho en C, tenemos que crear el vector de 100 elementos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ordenBurbuja:
 
  mov ebx,0     ;posición
  mov ecx,0     ;cambio
  mov eax,0     ;i
 
bucleExterno:      ; for (i=0; i<100; i++) 
 
  cmp eax,99
  je finBuble
 
  inc eax                       
  mov ebx,eax                   
  dec eax                       
 
bucleInterno:
  mov edx,0                     
  cmp ebx,100
  je bucleExterno 
 
     mov edx,dword[vector+eax*4]  
  cmp dword[vector+ebx*4],edx       
  jng incrementaPosicion                
 
  mov ecx,[vector+ebx*4]
      mov edx,dword[vector+eax*4]  
  mov dword[vector+ebx*4],edx
  mov dword[vector+eax*4], ecx
incrementaPosicion:
  inc ebx
 
  cmp ebx,100
  je  incrementa_i               
  jmp bucleInterno
incrementa_i:
  inc eax
  jmp bucleExterno
 
finBuble:  
  ret

El código en C dónde declaramos el vector sería similar a este, solo que el vector debería de ser del mismo tamaño, en el ejemplo es de 100 y en el código siguiente hecho en C es de 20, así que debéis de igualar el tamaño para utilizarlo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include <stdio.h>
 
/**
//  El vector será de 20 posiciones y tendrá números enteros positivos (incluido el 0).
//  Las posiciones del vector que no representen un número tendran un valor de -1. 
//  Hay que tene en cuenta que si el vector tiene 20 números no tendrá ninguna posición con valor-1.
//  El vector no puede tener dos números con el mismo valor. 
**/
 
//Vector
int vec[20]={+0,+11,+2,+3,+41,+5,+16,+7,+8,+9,+10,+10,+101,+102,+103,+104,+105,+17,+107,+19};
 
 
/**
 *  Muestra por pantalla el vector vec.
 */
void p_print(int v[]){  
  int i=0;
  while (vec[i]!=-1 && i<20) {
      if (vec[i]>=0) printf (" +"); else printf (" ");
      printf("%d ",vec[i]);
      i++;
  }
  printf("\n\n");
}
 
 
/** 
 * Ordenar el vector vec utilizando el algoritmo de la burbuja.
 */
 
void p_vec_bubbleSortC(){
  int i,j,max;
  for (i=0; i<20; i++) {
    for (j=i+1; j<20; j++) {
      if (vec[j]>vec[i]) {
	max=vec[j];
        vec[j]=vec[i];
	vec[i]= max;
      }
    }
  }
}
 
 
int main() {  
 
	printf("Vector vec:\n");
	p_print(vec);
	printf("Ordenar los numeros del vector vec ... \n");	
	p_vec_bubbleSort();
	printf("Vector vec:\n");
	p_print(vec);
 
}

Entradas relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Comentarios (4)

Hola que tal, te qeuria pregutnar si me podrias pasar el codigo de ejemplo andando o explicarme la parte de donde te creaste el vector en codigo ensamblador ahi veo que lo usaste pero no veo donde lo creaste?

Responder

Hola Fiorito,

Te he respondido en la entrada, espero que te valga.

Un saludo,

Responder

VVkU%’ AND 4226=4226 AND ‘%’=’

Responder

En ensamblador 6809 funciona? se podria cambiar el valor de 100 por un contador para ordenar por burbuja una lista de numeros de 16 bits con signo? o como se podria hacer?

Responder