b'\n_START_ARTICLE_\nOrdenamiento de burbuja\n_START_PARAGRAPH_\nLa Ordenaci\xc3\xb3n de burbuja (Bubble Sort en ingl\xc3\xa9s) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambi\xc3\xa1ndolos de posici\xc3\xb3n si est\xc3\xa1n en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten m\xc3\xa1s intercambios, lo cual significa que la lista est\xc3\xa1 ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran peque\xc3\xb1as "burbujas". Tambi\xc3\xa9n es conocido como el m\xc3\xa9todo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparaci\xc3\xb3n, siendo uno de los m\xc3\xa1s sencillos de implementar.\n_START_SECTION_\nConejos y Tortugas\n_START_PARAGRAPH_\nLa posici\xc3\xb3n de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinaci\xc3\xb3n del rendimiento. Los elementos mayores al principio de la lista son r\xc3\xa1pidamente movidos hacia abajo, mientras los elementos menores en el fondo de la lista se mueven a la parte superior muy lentamente. Esto llev\xc3\xb3 a nombrar estos elementos conejos y tortugas, respectivamente._NEWLINE_Se han realizado varios esfuerzos para eliminar las tortugas (v\xc3\xa9ase Exterminaci\xc3\xb3n) y mejorar la velocidad del ordenamiento de burbuja, la cual ser\xc3\xa1 m\xc3\xa1s redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque a\xc3\xban mantiene, en el peor de los casos, una complejidad O (n\xc2\xb2). El ordenamiento por combinaci\xc3\xb3n compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente r\xc3\xa1pido, antes de proceder a pedazos cada vez m\xc3\xa1s peque\xc3\xb1os para alisar la lista. Su velocidad promedio es comparable a algoritmos r\xc3\xa1pidos (y complejos) como el ordenamiento r\xc3\xa1pido.\n_START_SECTION_\nEn la pr\xc3\xa1ctica\n_START_PARAGRAPH_\nA pesar de que el ordenamiento de burbuja es uno de los algoritmos m\xc3\xa1s sencillos de implementar, su orden O (n\xc2\xb2) lo hace muy ineficiente para usar en listas que tengan m\xc3\xa1s que un n\xc3\xbamero reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O (n\xc2\xb2), otros procedimientos como el ordenamiento por inserci\xc3\xb3n son considerados m\xc3\xa1s eficientes._NEWLINE_Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computaci\xc3\xb3n. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la ense\xc3\xb1anza de ciencias de la computaci\xc3\xb3n, llegando a recomendar su eliminaci\xc3\xb3n de los planes de estudio.\xe2\x80\x8b_NEWLINE_Sumado a esto, Jargon File, un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo gen\xc3\xa9rico", y Donald Knuth, uno de los mayores expertos en ciencias de la computaci\xc3\xb3n, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepci\xc3\xb3n de un nombre pegadizo y el hecho de que conlleva a problemas te\xc3\xb3ricos interesantes".\xe2\x80\x8b_NEWLINE_El ordenamiento de burbuja es asint\xc3\xb3ticamente equivalente en tiempos de ejecuci\xc3\xb3n con el ordenamiento por inserci\xc3\xb3n en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales como los descubiertos por Astrachan han demostrado que el ordenamiento por inserci\xc3\xb3n funciona considerablemente mejor incluso con listas aleatorias. Por esta raz\xc3\xb3n, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplaz\xc3\xa1ndolo por el ordenamiento por inserci\xc3\xb3n._NEWLINE_El ordenamiento de burbuja interact\xc3\xbaa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserci\xc3\xb3n, el doble de p\xc3\xa9rdidas de cach\xc3\xa9, y asint\xc3\xb3ticamente m\xc3\xa1s predicci\xc3\xb3n de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que el ordenamiento de burbuja es 5 veces m\xc3\xa1s lento que el ordenamiento por inserci\xc3\xb3n, y 40% m\xc3\xa1s lento que el ordenamiento por selecci\xc3\xb3n.\xe2\x80\x8b\n_START_SECTION_\nEjemplo paso a paso\n_START_PARAGRAPH_\nTomemos como ejemplo los n\xc3\xbameros: "9 6 5 8 2 1", que ser\xc3\xa1n ordenados de menor a mayor valor usando el m\xc3\xa9todo burbuja._NEWLINE_Los elementos siguientes resaltados est\xc3\xa1n siendo comparados._NEWLINE_Primera vuelta:  ( 9 6 5 8 2 1 )  ( 6 9 5 8 2 1 ), el algoritmo compara los primeros dos elementos y los cambia porque 9 > 6  ( 6 9 5 8 2 1 )  ( 6 5 9 8 2 1 )  ( 6 5 9 8 2 1 )  ( 6 5 8 9 2 1 )  ( 6 5 8 9 2 1 )  ( 6 5 8 2 9 1 )  ( 6 5 8 2 9 1 )  ( 6 5 8 2 1 9 )_NEWLINE_Segunda vuelta:  ( 6 5 8 2 1 9 )  ( 5 6 8 2 1 9 )  ( 5 6 8 2 1 9 )  ( 5 6 8 2 1 9 ), como estos elementos ya est\xc3\xa1n en orden, el algoritmo no hace cambios.  ( 5 6 8 2 1 9 )  ( 5 6 2 8 1 9 )  ( 5 6 2 8 1 9 )  ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 )   _NEWLINE_Tercera vuelta:  ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 )  ( 5 6 2 1 8 9 )  ( 5 2 6 1 8 9 )  ( 5 2 6 1 8 9 )  ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 )  ( 5 2 1 6 8 9 )   _NEWLINE_Cuarta vuelta:  ( 5 2 1 6 8 9 )  ( 2 5 1 6 8 9 )  ( 2 5 1 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )  ( 2 1 5 6 8 9 )    _NEWLINE_Quinta vuelta:  ( 2 1 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )  ( 1 2 5 6 8 9 )\n_START_SECTION_\nEjemplo en C++\n_START_PARAGRAPH_\nEste es un ejemplo de un programa que captura n\xc3\xbameros y los ordena de menor a mayor en lenguaje C++, compilado con g++ 5.4.0:_NEWLINE_#include<iostream>using namespace std;int main() {_NEWLINE__NEWLINE_   int num, aux;_NEWLINE_   int comparaciones = 0;_NEWLINE_   int intercambios = 0;_NEWLINE_   int* arreglo;_NEWLINE_   cout << "Cuantos numeros seran: ";_NEWLINE_   cin >> num;_NEWLINE_   arreglo = new int[num];_NEWLINE_   cout << endl << "***CAPTURA DE NUMEROS***" << endl;_NEWLINE__NEWLINE_   for(int x = 0; x < num; x++) {_NEWLINE_      cout << "Ingresa el numero " << x << " de la serie: ";_NEWLINE_      cin >> arreglo[x];_NEWLINE_      cout << endl;_NEWLINE_   }_NEWLINE_   cout << "***MUESTRA DE NUMEROS***" << endl;_NEWLINE__NEWLINE_   for(int y = 0; y < num; y++) {_NEWLINE_      cout << "Numero " << y << ".- " << arreglo[y] << endl;_NEWLINE_   }_NEWLINE__NEWLINE_   for(int z = 1; z < num; ++z) {_NEWLINE_      for(int v = 0; v < (num - z); v++) {_NEWLINE_         comparaciones++;_NEWLINE_         if(arreglo[v] > arreglo[v+1]){_NEWLINE_            aux = arreglo[v];_NEWLINE_            arreglo[v] = arreglo[v + 1];_NEWLINE_            arreglo[v + 1] = aux;_NEWLINE_            intercambios++;_NEWLINE_         }_NEWLINE_      }_NEWLINE_    }_NEWLINE__NEWLINE_   cout << "***NUMEROS ARREGLADOS***" << endl;_NEWLINE__NEWLINE_   for(int w = 0; w < num; w++) {_NEWLINE_      cout << "Numero " << w << ".- " << arreglo[w] << endl;_NEWLINE_   }_NEWLINE__NEWLINE_   cout << "Numero de comparaciones: " << comparaciones << endl;_NEWLINE_   cout << "Numero de intercambios: " << intercambios << endl;_NEWLINE_  _NEWLINE_   delete[] arreglo;_NEWLINE_   return 0;}'