Metodo Burbuja

PHP [editar] function bubble_sort($array){ $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j=$j-1){ if ($array[$j] < $array[$j-1]){ $tmp = $array[$j]; $array[$j] = $array[$j-1]; $array[$j-1] = $tmp; } } } return $array; }

ORDENACIÓN POR EL MÉTODO DE LA BURBUJA Este método consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar y acomodar el siguiente más grande comparando de nuevo los numeros desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación. Entonces: Dado un vector a1, a2, a3, ... an 1) Comparar a1 con a2 e intercambiarlos si a1>a2 (o a12) 2) Seguir hasta que todo se haya comparado an-1 con an 3) Repetir el proceso anterior n-1 veces Algoritmo:

Complejidad

for(i=0; i < n-1; i++){ for(j=0; j < n-1; j++){ if(vec[j] > vec[j+1]){

}

T(n2) T(n) T(1)

aux=vec[j];

T(1)

vec[j]=vec[j+1];

T(1)

vec[j+1]=aux;}

T(1)

} El procedimiento de la burbuja es el siguiente: 

 

Ir comparando desde la casilla 0 numero tras número hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevará hasta la última casilla, si no es así, será reemplazado por uno mayor que él. Este procedimiento seguirá así hasta que halla ordenado todas las casillas del vector. Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario. Ejemplo:

Variables i 0 0 0 0 0 1 1 1 1 2 2 3 3 4 5

j 1 2 4 5 6 0 1 3 4 2 3 1 2 1 0

Vector pos a[j] a[j+1] inicio 55 12 cambio 55 42 cambio 94 18 cambio 94 6 cambio 94 67 cambio 44 12 cambio 44 42 cambio 55 18 cambio 55 6 cambio 44 18 cambio 44 6 cambio 42 18 cambio 42 6 cambio 18 6 cambio 12 6 ordenado

0 44 44 44 44 44 44 12 12 2 12 12 12 12 12 12 6

1 55 12 12 12 12 12 44 42 42 42 42 42 18 18 6 12

2 12 55 42 42 42 42 42 44 44 44 18 18 42 6 18 18

3 42 42 55 55 55 55 55 55 18 18 44 6 6 42 42 42

4 94 94 94 18 18 18 18 18 55 6 6 44 44 44 44 44

5 18 18 18 94 6 6 6 6 6 55 55 55 55 55 55 55

6 6 6 6 6 94 67 67 67 67 67 67 67 67 67 67 67

ORDENAMIENTO BURBUJA SIMPLE void CordenamientoburbujaDlg::OnBnClickedButton1() { // TODO: Agregue aquí su código de controlador de notificación de control

7 67 67 67 67 67 94 94 94 94 94 94 94 94 94 94 94

#define TAMANIO 10 int vector[TAMANIO]={4,5,3,9,2,3,1,4,8,6}; int pasadas,elemento,almacena; UpdateData(TRUE); m_a1=vector[0]; m_a2=vector[1]; m_a3=vector[2]; m_a4=vector[3]; m_a5=vector[4]; m_a6=vector[5]; m_a7=vector[6]; m_a8=vector[7]; m_a9=vector[8]; m_a10=vector[9]; UpdateData(FALSE); for (pasadas=1;pasadasvector[elemento+1]){ almacena=vector[elemento]; vector[elemento]=vector[elemento+1];//Declaración destructiva. vector[elemento+1]=almacena; } } } UpdateData(TRUE);

m_b1=vector[0]; m_b2=vector[1]; m_b3=vector[2]; m_b4=vector[3]; m_b5=vector[4]; m_b6=vector[5]; m_b7=vector[6]; m_b8=vector[7]; m_b9=vector[8]; m_b10=vector[9]; UpdateData(FALSE); }

ORDENAMIENTO BURBUJA DOBLE void CordenamientoburbujaDlg::OnBnClickedButton2() { // TODO: Agregue aquí su código de controlador de notificación de control #define TAMANIO 10 int vector[TAMANIO]={4,5,3,9,2,3,1,4,8,6}; int pasadas,elemento,almacena; UpdateData(TRUE); m_a1=vector[0]; m_a2=vector[1]; m_a3=vector[2]; m_a4=vector[3]; m_a5=vector[4];

m_a6=vector[5]; m_a7=vector[6]; m_a8=vector[7]; m_a9=vector[8]; m_a10=vector[9]; UpdateData(FALSE); for (pasadas=1;pasadasvector[elemento+1]){ almacena=vector[elemento]; vector[elemento]=vector[elemento+1]; vector[elemento+1]=almacena; } if(vector[TAMANIO-(elemento+1)]
m_b5=vector[4]; m_b6=vector[5]; m_b7=vector[6]; m_b8=vector[7]; m_b9=vector[8]; m_b10=vector[9]; UpdateData(FALSE); }

ORDENAMIENTO BURBUJA TRIPLE void CordenamientoburbujaDlg::OnBnClickedButton3() { // TODO: Agregue aquí su código de controlador de notificación de control #define TAMANIO 11 int vector[TAMANIO]={4,5,3,9,2,3,1,4,8,6}; int pasadas,elemento,menor,medio,mayor; UpdateData(TRUE); m_a1=vector[0]; m_a2=vector[1]; m_a3=vector[2]; m_a4=vector[3]; m_a5=vector[4]; m_a6=vector[5]; m_a7=vector[6]; m_a8=vector[7]; m_a9=vector[8];

m_a10=vector[9]; UpdateData(FALSE); for(pasadas=1;pasadas
} } if((vector[elemento+2]vector[elemento])){//Caso de 1,1,2 (dos primeros iguales y tercero mayor). menor=vector[elemento]; medio=vector[elemento+1]; mayor=vector[elemento+2]; }

if((vector[elemento]==vector[elemento+2]) && (vector[elemento+1]>vector[elemento])){//Caso de 1,2,1 (primero y tercero iguales y segundo mayor). menor=vector[elemento]; medio=vector[elemento+2]; mayor=vector[elemento+1]; } if((vector[elemento+1]==vector[elemento+2]) && (vector[elemento]>vector[elemento+1])){//Caso de 2,1,1 (segundo y tercero iguales y primero mayor). menor=vector[elemento+1]; medio=vector[elemento+2]; mayor=vector[elemento]; } vector[elemento]=menor; vector[elemento+1]=medio; vector[elemento+2]=mayor; } } UpdateData(TRUE); m_b1=vector[0]; m_b2=vector[1]; m_b3=vector[2]; m_b4=vector[3]; m_b5=vector[4]; m_b6=vector[5]; m_b7=vector[6];

m_b8=vector[7]; m_b9=vector[8]; m_b10=vector[9]; UpdateData(FALSE); } ESTE SI function bubble_sort($array){ $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j–-){ if ($array[$j] < $array[$j-1]){ $tmp = $array[$j]; $array[$j] = $array[$j-1]; $array[$j-1] = $tmp; } } } return $array; } function bubble_sort($array){ $count = count($array); //Cuento los elementos del arreglo if ($count <= 0) return false; //Si no hay elementos entonces que voy ordenar? retorno falso for($i=0; $i<$count; $i++){//Recorro cada uno de los elementos for($j=$i+1; $j<$count; $j++){ if ($array[$j] < $array[$i]){//Comparo si hay un elemento del arreglo menor que el de la posicion i, si es asi intercambio posiciones $tmp = $array[$j]; $array[$j] = $array[$i]; $array[$i] = $tmp; } } } return $array; }