Nombre: Santiago René Sarmiento Sotomayor
Docente: Ing. Daniel Irene
Tema: Método de Intercambio o de Burbuja.
Consiste en evaluar pares de elementos contiguos del arreglo, y si el primero es mayor que el siguiente los intercambia, según la condición. Todo sucede dentro de dos ciclos (for) que recorren el arreglo. El ciclo más interno realiza las comparaciones, y es ahí donde el elemento mayor ocupara una posición mayor.
Formas de Método Burbuja:
Comparando primer elemento con el segundo, luego segundo con tercero y sucesivamente.
for (i=1;i<Nelementos;i++){ for (j=0;j<=Nelementos-1 ;j++) { if (array[j] > array[j+1]) { Aux=array[j]; array[j]=array[j+1]; array[j+1]=Aux; } }}
Comparando primer elemento con todos los demás restantes, y luego el segundo con todos los elementos restantes, así sucesivamente.
El algoritmo se puede diseñar para que ordene un vector de forma ascendente como también descendentemente.
for (i = 0; i < Nelementos; i++){ for (int j = i +1; j < Nelementos; j++) { if (array[i] > array[j]) { Aux = array[i]; array[i] = array[j]; array[j] = Aux; } } }
Ejemplo: Ordenar ascendentemente el siguiente vector. A=[5, 3, 7, 1] (Corrida manual)
Pasos
Condición for(j=0;j<limite;j++)
{ for(i=0;i<limite;i++)
If(A[i]>A[i+1]) intercambia }
Array (limite=3)
A=[5, 3, 7, 1]
1 5 > 3 A=[3, 5, 7, 1]
2 5 < 7 A=[3, 5, 7, 1]
3 7 > 1 A=[3, 5, 1, 7]
Vuelvo a comparar desde A[0]
4 3 < 5 A=[3, 5, 1, 7]
5 5 > 1 A=[3, 1, 5, 7]
6 5 > 7 A=[3, 1, 5, 7]
Vuelvo a A[0]
7 3 > 1 A=[1, 3, 5, 7]
Fin Procedimiento
Primer array A=[5, 3, 7, 1]
Array ordenado de forma ascendente A=[1, 3, 5, 7]
Métodos Directos de Ordenamiento de un Array o Vector.
Burbuja. Inserción Directa.
Consiste en insertar un elemento en el vector y comenzar de nuevo con los elementos restantes. Ejemplo: ordenar el elemento 7.
Insertaremos el elemento numero 8 saltando por los elementos 6 y 7.
Selección.1. Seleccionar el menor elemento del vector de n elementos.2. Intercambia dicho elemento con el primero.3. Se repiten esas operaciones con n-1 elementos restantes, se selecciona el segundo
y continuamos con n-2, así sucesivamente hasta que solo quede el mayor.
Referencia:
http://www.nachocabanes.com/tutors/salvadorPozo-Cpp.pdf
http://webdelprofesor.ula.ve/ingenieria/eliana/prog/Vectores.pdf
EJEMPLO: Usar método burbuja para ordenar el array creado aleatoriamente.
Metodo_Burbuja.cpp#include <iostream>#include <time.h>#include <cstdlib>#include <windows.h>#define length(x) (sizeof(x)/sizeof(x[0]))using namespace std;
void cambio(int &a, int &b);void ordenar_burbuja(int arreglo[], int limite);void mostrar_array(int arreglo[], int limite);
int main(){ int lim=0; cout<<"Ingrese el limite del array unidimensional"<<endl; cin>>lim; int array[lim]; srand(time(NULL)); cout<<"\n"<<"Primer array"<<endl<<"A=["; for (int i=0; i<lim;i++)//crea un array con numeros aleatorios array[i]=1+rand()%29; mostrar_array(array,lim); cout<<" ]"<<"\n\n"<<"Array ordenado"<<"\n"<<"A=["; ordenar_burbuja(array,lim); mostrar_array(array,lim); cout<<" ]"; system("pause>null");
return 0;}void ordenar_burbuja(int arreglo[], int limite)//Compara susecivamente.{ for (int i=0;i<limite-1;i++) for (int j=0;j<limite-1;j++) if(arreglo[j] > arreglo[j+1]) cambio(arreglo[j],arreglo[j+1]);}void cambio(int &a, int &b)//Paso por referencia de valor de un elemento{ int aux=b; b=a; a=aux;}void mostrar_array(int arreglo[], int limite){ for (int i=0; i<limite;i++) cout<<" "<<arreglo[i];}
El código fuente está diseñado para que comprare cada uno de los elementos con el que le sigue, de esa forma sucesivamente hasta terminar el proceso.
Recommended