abr
2
2012

Ensamblador | Algoritmo de la burbuja

Descarga el contenido del Artículo en PDF Download PDF

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);
 
}
Click on any of these buttons to help us to maintain this website.      
CJO

Artículos relacionados

Related Posts

Acerca del Autor:

2 Comments + Add Comment

  • 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?

  • Hola Fiorito,

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

    Un saludo,

Leave a comment


1 × = cinco

ndslite

Ayudas!

Recientes

  • Muebles origenes: Muchas gracias por este pos, es muy interesante saludos
  • Keducc: Gracias me sirvió. Para marcar la partición como activa hice esto: http://windows.microsoft.co...
  • Nicolás Damián Sadofschi: Lo pude asociar perfecto en mi pagina de alquiler de pistas de hielo, graciasª
  • Ber: Hola, Entiendo lo que te sucede, pero eso es cosa del theme de tu Wordpress, si programas un poquito edítalo y...
  • Multinivel: Sabes como le puedo hacer para que el título de mi post no sea h1 Trabajo con seo pressor y este me pide...