11/18/2005

Ordenamiento burbuja en C++

Los algorítmos de ordenacion son un tema de constante estudio en las ciencias informáticas. Un buen lugar dónde empezar a investigar es la wikipedia, aquí tenemos un repaso sobre los algorítmos de ordenación.

El ordenamiento por burbuja es bastante sencillo, consiste en evaluar pares de elementos contiguos del arreglo y si el primero es mayor que el siguiente los intercambia (los más chicos quedan abajo). Todo ésto sucede dentro de dos ciclos for que recorren el arreglo. El ciclo más interno realiza las comparaciones, y se asegura ya en la primera pasada completa que el elemento ás grande del arreglo suba a la posición más alta (ésto más adelante nos permitirá desarrollar un algorítmo mejorado del método burbuja).

El programa siguiente consta de 3 funciones:

//La usamos para desplegar los elementos del arreglo.
void mostrarArreglo(const int[], int); 

//Es el algoritmo de ordenamiento por burbuja
void ordenarArreglo(int[], int);

/*Esta función es llamada por la función anterior, 
y se encarga de intercambiar los pares de elementos
cuando sea necesario. Notar que recibe referencias 
ya que necesita modificar los valores de sus argumentos.*/
void intercambiar(int&, int&);

Ejemplo:

//Ordena burbuja, ordenamiento
//de un arreglo metodo burbuja
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que recibe un arreglo constante
void ordenarArreglo(int[], int); //prototipo que modifica y ordena elarreglo
void intercambiar(int&, int&); //prototipo, intercambialos valores de dos elementos
int main()
{
  const int tamano = 15;
  int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78,21,10};
  cout << "Arreglo antes de ordenarse: " <<endl;
  mostrarArreglo(arreglo,tamano);
  cout << "Arreglo despues de ordenarse: " <<endl;
  ordenarArreglo(arreglo,tamano);
  mostrarArreglo(arreglo,tamano);
  cout << "Fin del programa :)" << endl;
  return 0;
}//fin de main

void mostrarArreglo(const int arreglo[], int tamano)
{
  for (int i = 0 ; i < tamano ; i++)
    cout << "arreglo["<< i << "]=" << arreglo[i]<< endl;
}
void ordenarArreglo(int arreglo[], int tamano)
{
  for (int i = 0; i<tamano-1 ; i++)
    for (int j = 0; j<tamano-1 ; j++)
      if(arreglo[j] < arreglo[j+1])
 intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
  int tmp = b;
  b = a;
  a = tmp;
} 

Ver como hacer para compilar este programa.

5 comentarios:

Anónimo dijo...

guachin te equivocaste! en el ordenamiento de burbuja, si el primero es menor al siguiente se intercambian por ende los mas chicos quedan al final.

Anónimo dijo...

Hermano ahi ordenas los datos al contrario. En el ordenamiento Burbuja los valores mas bajos van al principio. De esta forma un arreglo: arr[5]={5,4,3,2,1} se ordenaria a arr[5]={1,2,3,4,5}

Anónimo dijo...

PuntoPeek tiene razon, depende de como lo quieras ordenar, puedes elegir entre menor a mayor (vec[I]> vec[I+1]) o viceversa (vec[I]< vec[I+1]). Y si, lo malo es que revisa varias veces el vector, aunque en la primer pasada ya este ordenado. Aunque existen otros metodos de ordenamiento, este es una posibilidad a utilizar, tal vez no sea la mejor opcion, pero es una de las tantas que hay

Anónimo dijo...

gracias genio, todo el dia estuve buscando esta funcion, me salvaste la vida

Marco Guevara dijo...

Obvio, pues que no le piensan un poquito o que?
Solo cambien el sentido del simbolo ¬_¬


Como hay genios...