Diferencia entre revisiones de «Ordenamiento de burbuja»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 06:20 9 mar 2011

El Ordenamiento de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está 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ñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Descripción

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

{\color {Sepia}{\mathit {procedimiento}}}\;{\color {Blue}{\mathit {DeLaBurbuja}}}\;({\color {Black}{\mathit {a}}}{\color {Plum}{\mathit {{}_{0}}}},{\color {Black}{\mathit {a}}}{\color {Plum}{\mathit {{}_{1}}}},{\color {Black}{\mathit {a}}}{\color {Plum}{\mathit {{}_{1}}}},\ldots ,{\color {Black}{\mathit {a}}}{}_{(}{\color {black}{\mathit {{}_{n}}}}{\color {Blue}{\mathit {{}_{-}}}}{\color {Plum}{\mathit {{}_{1}}}}{}_{)})

{\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {i}}}\;{\color {Blue}{\mathit {\gets }}}\;{\color {Plum}{\mathit {2}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n}}}\;{\color {Sepia}{\mathit {hacer}}}

{\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {j}}}\;{\color {Blue}{\mathit {\gets }}}\;{\color {Plum}{\mathit {0}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n}}}\;{\color {Blue}{\mathit {-}}}\;{\color {Black}{\mathit {i}}}\;{\color {Sepia}{\mathit {hacer}}}

{\color {Sepia}{\mathit {si}}}\;{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{}_{)}\;{\color {Blue}{\mathit {>}}}\;{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{\color {Blue}{\mathit {{}_{+}}}}{\color {Plum}{\mathit {{}_{1}}}}{}_{)}\;{\color {Sepia}{\mathit {entonces}}}

{\color {Black}{\mathit {aux}}}\;{\color {Blue}{\mathit {\gets }}}\;{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{}_{)}\;

{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{}_{)}\;{\color {Blue}{\mathit {\gets }}}\;{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{\color {Blue}{\mathit {{}_{+}}}}{\color {Plum}{\mathit {{}_{1}}}}{}_{)}

{\color {Black}{\mathit {a}}}{}_{(}{\color {Black}{\mathit {{}_{j}}}}{\color {Blue}{\mathit {{}_{+}}}}{\color {Plum}{\mathit {{}_{1}}}}{}_{)}\;{\color {Blue}{\mathit {\gets }}}\;{\color {Black}{\mathit {aux}}}

{\color {Sepia}{\mathit {fin\;si}}}

{\color {Sepia}{\mathit {fin\;para}}}

{\color {Sepia}{\mathit {fin\;para}}}

{\color {Sepia}{\mathit {fin\;procedimiento}}}

Este algoritmo realiza el ordenamiento de una lista a de n valores, en este caso de n términos numerados del 0 al n-1, consta de dos bucles anidados uno con el índice i, que da un tamaño menor al recorrido de la burbuja en sentido inverso de 2 a n, y un segundo loop con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.

La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.

Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende de n, y no del orden de los términos, esto es si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego verano una variante que evita este inconveniente.

Para comprender el funcionamiento, veamos un ejemplo sencillo:

Tenemos una lista de números que hay que ordenar:

a=\{55,86,48,16,82,\}\,

{\begin{array}{r}a_{4}=82\\a_{3}=16\\a_{2}=48\\a_{1}=86\\a_{0}=55\end{array}}

Podemos ver que la lista que tiene cinco términos, luego:

n=5\,

El índice i hará un recorrido de 2 hasta n:

{\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {i}}}\;{\color {BlueViolet}{\mathit {\gets }}}\;{\color {Black}{\mathit {2}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n}}}\;{\color {Sepia}{\mathit {hacer}}}

Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

{\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {j}}}\;{\color {BlueViolet}{\mathit {\gets }}}\;{\color {Black}{\mathit {0}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n-i}}}\;{\color {Sepia}{\mathit {hacer}}}

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

{\color {Sepia}{\mathit {si}}}\;{\color {Black}a_{(j)}}\;{\color {BlueViolet}>}\;{\color {Black}a_{(j+1)}}\;{\color {Sepia}{\mathit {entonces}}}

Si el termino j es menor, en su caso podría se mayor, que el termino j+1, los valores se permutan, en caso contrario se continúa con la iteración.

{\begin{array}{r||r|r|r|r|r}&j=0&j=1&j=2&j=3&\\\hline a_{4}&82&82&82&\to 82&86\\a_{3}&16&16&\to 16&\to 86&82\\a_{2}&48&\to 48&\to 86&16&16\\a_{1}&\to 86&\to 86&48&48&48\\a_{0}&\to 55&55&55&55&55\end{array}}

Para el caso del ejemplo, tenemos que:

n=5\,

Para la primera iteración del primer bucle:

i=2\,

y j tomara los valores de 0 hasta 3:

{\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {j}}}\;{\color {BlueViolet}{\mathit {\gets }}}\;{\color {Black}{\mathit {0}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {3}}}\;{\color {Sepia}{\mathit {hacer}}}

Cuando j vale 0, se comparan $a_{0}\;a_{1}$ , el 55 y el 86, dado que 55 < 86 no se permutan el orden.

Ahora j vale 1 y se comparan $a_{1}\;a_{2}$ el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nueva lista.

Se repite el proceso hasta que j valga 3, dando lugar a una re lista super ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.

{\begin{array}{r||r|r|r|r}&j=0&j=1&j=2&\\\hline a_{4}&86&86&86&86\\a_{3}&82&82&\to 82&82\\a_{2}&16&\to 16&\to 55&55\\a_{1}&\to 48&\to 55&16&16\\a_{0}&\to 55&48&48&48\end{array}}

Ahora i vale 3, y j hará un recorrido de 0 a 2.

Primero j vale 0, se comparan $a_{0}\;a_{1}$ , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.

Para j = 1 se compara el 55 con el 16 y se cambian de orden.

Para j = 2 se compara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.

El algoritmo consiste en comparaciones sucesivas de dos términos consecutivos, ascendiendo de abajo a arriba en cada iteración, como la ascensión de las burbujas de aire en el agua, de ahí el nombre del procedimiento, en la primera iteración el recorrido ha sido completo, en el segundo se ha dejado él último termino, al tener ya el mayor de los valores, en los sucesivos sé ira dejando re realizar las ultimas comparaciones, como se puede ver.

{\begin{array}{r||r|r|r}&j=0&j=1&\\\hline a_{4}&86&86&86\\a_{3}&82&82&82\\a_{2}&55&\to 55&55\\a_{1}&\to 16&\to 48&48\\a_{0}&\to 48&16&16\end{array}}

Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.

Cuando j vale 0, se comparan $a_{0}\;a_{1}$ esto es el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar a una lista algo más ordenada que la anterior, desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos $a_{1}\;a_{2}$ el 48 y el 55 que quedan en el mismo orden.

En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista esta ya ordenada, pero el algoritmo tendrá que completarse, realizando una ultima iteración.

Hay que tener en cuenta que el bucle para realiza un número fijo de repeticiones y para finalizar tendrán que completarse, aun en el caso extremo, de que la lista estaría previamente ordenada.

Por último i vale 5 y j solo puede vale 0, con lo que solo se realizara una comparación de $a_{0}\;a_{1}$ el 16 y el 48, que ya están ordenados y se dejan igual.

{\begin{array}{r||r|r}&j=0&\\\hline a_{4}&86&86\\a_{3}&82&82\\a_{2}&55&55\\a_{1}&\to 48&48\\a_{0}&\to 16&16\end{array}}

Los bucles finalizan y también el procedimiento, dejando la lista ordenada.

Una variante que finaliza en caso de que la lista este ordenada, puede ser la siguiente, empleando un centinela ordenado, que detecta que no se ha modificado la lista en un recorrido de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.

${\color {Sepia}procedimiento}\;{\color {BlueViolet}DeLaBurbuja2}\;({\color {Black}a_{(0)},a_{(1)},a_{(2)},\ldots ,a_{(n-1)}})$ ${\color {Black}i}\;{\color {BlueViolet}\gets }\;{\color {Black}1}\;$ ${\color {Black}ordenado}\;{\color {BlueViolet}\gets }\;{\color {Black}no}\;$ ${\color {Sepia}{\mathit {mientras}}}\;{\color {Black}{\mathit {(i<n)\;\land \;(ordenado=no)}}}\;{\color {Sepia}{\mathit {hacer}}}$ ${\color {Black}i}\;{\color {BlueViolet}\gets }\;{\color {Black}i+1}\;$ ${\color {Black}ordenado}\;{\color {BlueViolet}\gets }\;{\color {Black}si}\;$ ${\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {j}}}\;{\color {BlueViolet}{\mathit {\gets }}}\;{\color {Black}{\mathit {0}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n-i}}}\;{\color {Sepia}{\mathit {hacer}}}$ ${\color {Sepia}{\mathit {si}}}\;{\color {Black}a_{(j)}}\;{\color {BlueViolet}>}\;{\color {Black}a_{(j+1)}}\;{\color {Sepia}{\mathit {entonces}}}$ ${\color {Black}ordenado}\;{\color {BlueViolet}\gets }\;{\color {Black}no}\;$ ${\color {Black}aux}\;{\color {BlueViolet}\gets }\;{\color {Black}a_{(j)}}\;$ ${\color {Black}a_{(j)}}\;{\color {BlueViolet}\gets }\;{\color {Black}a_{(j+1)}}\;$ ${\color {Black}a_{(j+1)}}\;{\color {BlueViolet}\gets }\;{\color {Black}aux}\;$ ${\color {Sepia}{\mathit {fin\;si}}}$ ${\color {Sepia}{\mathit {fin\;para}}}$ ${\color {Sepia}{\mathit {fin\;mientras}}}$ ${\color {Sepia}{\mathit {fin\;procedimiento}}}$

${\color {Sepia}procedimiento}\;{\color {BlueViolet}DeLaBurbuja3}\;({\color {Black}a_{(0)},a_{(1)},a_{(2)},\ldots ,a_{(n-1)}})$ ${\color {Black}i}\;{\color {BlueViolet}\gets }\;{\color {Black}1}\;$ ${\color {Sepia}{\mathit {repetir}}}$ ${\color {Black}i}\;{\color {BlueViolet}\gets }\;{\color {Black}i+1}\;$ ${\color {Black}ordenado}\;{\color {BlueViolet}\gets }\;{\color {Black}si}\;$ ${\color {Sepia}{\mathit {para}}}\;{\color {Black}{\mathit {j}}}\;{\color {BlueViolet}{\mathit {\gets }}}\;{\color {Black}{\mathit {0}}}\;{\color {Sepia}{\mathit {hasta}}}\;{\color {Black}{\mathit {n-i}}}\;{\color {Sepia}{\mathit {hacer}}}$ ${\color {Sepia}{\mathit {si}}}\;{\color {Black}a_{(j)}}\;{\color {BlueViolet}>}\;{\color {Black}a_{(j+1)}}\;{\color {Sepia}{\mathit {entonces}}}$ ${\color {Black}ordenado}\;{\color {BlueViolet}\gets }\;{\color {Black}no}\;$ ${\color {Black}aux}\;{\color {BlueViolet}\gets }\;{\color {Black}a_{(j)}}\;$ ${\color {Black}a_{(j)}}\;{\color {BlueViolet}\gets }\;{\color {Black}a_{(j+1)}}\;$ ${\color {Black}a_{(j+1)}}\;{\color {BlueViolet}\gets }\;{\color {Black}aux}\;$ ${\color {Sepia}{\mathit {fin\;si}}}$ ${\color {Sepia}{\mathit {fin\;para}}}$ ${\color {Sepia}{\mathit {hasta\;que}}}\;{\color {Black}{\mathit {\neg (i<n)\;\lor \;(ordenado=si)}}}$ ${\color {Sepia}{\mathit {fin\;procedimiento}}}$

Análisis

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

Rendimiento en casos óptimos

El ordenamiento de burbuja tiene una complejidadΩ(n²). Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos. Esto lo cataloga como el algoritmo mas ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.

Conejos y Tortugas (Yo-yos) (?)

La posición de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinación del rendimiento. Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo, mientras los elementos menores en el fondo de la lista se mueven a la parte superior muy lentamente. Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.

Varios esfuerzos se han realizado para eliminar las tortugas véase Exterminación y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque aún mantiene, en el peor de los casos, una complejidad O (n²). El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista. Su velocidad promedio es comparable a algoritmos rápidos (y complejos) como el ordenamiento rápido.

En la práctica

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O (n²) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O (n²), otros procedimientos como el ordenamiento por inserción son considerados más eficientes.

Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computación. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio.^[1]

Sumado a esto, Jargon File, un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y Donald Knuth, uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". ^[2]

El ordenamiento de burbuja es asintóticamente equivalente en tiempos de ejecución con el ordenamiento por inserción 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ón funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazándolo por el ordenamiento por inserción.

El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción, y 40% más lento que el ordenamiento por selección.^[1]

Implementación

A continuación se muestra el Ordenamiento de burbuja en distintos lenguajes de programación:

LUA

function burbuja_ordenar(t)
    for i=1, #t do
        for j=i+1, #t do
            if (t[i] > t[j]) then
                temp = t[i]
                t[i] = t[j]
                t[j] = temp
            end
        end
    end
end

QBASIC

CLS
RANDOMIZE TIMER
n = 10
DIM a(n)

REM Generar e imprimir n+1 números aleatorios
FOR i = 0 TO n
    a(i) = INT(RND * 1000)
    PRINT USING "a(##)=#####"; i; a(i)
NEXT
PRINT

REM algoritmo de la burbuja
FOR j = n TO 1 STEP -1
    FOR i = 1 TO j
        IF a(i - 1) > a(i) THEN
            aux = a(i)
            a(i) = a(i - 1)
            a(i - 1) = aux
        END IF
    NEXT
NEXT

REM imprimir datos ordenados
FOR i = 0 TO n
    PRINT USING "a(##)=#####"; i; a(i)
NEXT

C

//Ordenamiento por método de la Burbuja
void ordenamientoBurbuja(int v[], int util_v) {
	 int temp, i, j;
	 
	 for (i = 0; i < util_v -1 ; i++) {
	 	 for (j = i + 1; j < util_v ; j++) {
 	  	 	 if (v[i] > v[j]) {
		 	 	temp = v[i];
		 	 	v[i] = v[j];
		 	 	v[j] = temp;
		 }
		 }	 
	 }
}

C++

template<typename _Ty>
void bubble_sort(vector<_Ty> & v){

	for (size_t i = 0; i < v.size() - 1; ++i){
		for (size_t j = i + 1; j < v.size(); ++j){
			if (v[i] > v[j])
				swap(v[i], v[j]);
		}
	}
}

C#

    Public int[] OrdenarBurbuja(int[]x)
       {
            int t= x.Length, temp;
            for(int i=1 ; i< t ; i++)
                  for(int j = t-1 ; j >= i; j--)
                       {
                         if(x[j] < x[j-1])
                             {
                              temp= x[j];
                              x[j]= x[j-1];
                              x[j-1]= temp;
                             }
                       }
       return x;
       }

Java

    //Ordenamiento por Burbuja 
    // by ramses2999
    public static int[] OrdenarBurbuja(int[] n){
        int temp;
        int t = n.length;
        for (int i = 1; i < t; i++) {
            for (int k = t- 1; k >= i; k--) {
                if(n[k] < n[k-1]){
                    temp = n[k];
                    n[k] = n[k-1];
                    n[k-1]=  temp;
                }//fin if
            }// fin 2 for
        }//fin 1 for
        return n;
    }//fin

Perl

sub bubblesort {
    # Ordena la lista pasada como argumento por valor
    for my $i (    0 .. @_-2 ) {
    for my $j ( $i+1 .. @_-1 ) {
        @_[ $i, $j ] = @_[ $j, $i ] if $_[$i] > $_[$j];
    }}
}

Visual Basic

    Private Sub OrdenarBurbuja(ByRef VectorOriginal() As Integer)
        Dim Temp, Longitud As Integer
        Longitud = VectorOriginal.Length - 2
        For b = 0 To Longitud
            For a = 0 To Longitud
                If VectorOriginal(a) > VectorOriginal(a + 1) Then
                    Temp = VectorOriginal(a + 1)
                    VectorOriginal(a + 1) = VectorOriginal(a)
                    VectorOriginal(a) = Temp
                End If
            Next
        Next
    End Sub

PHP

<?php

//Ordenamiento por burbuja
$numeros = array(9, 4, -1, 7, 8, 11, 6, 12, 10, 5);

$n = count($numeros);

for ($i = 1; $i<$n; $i++) {
    for ($j = $n-1; $j >= $i; $j--) {
        echo "i: $i, j: $j\n";
        echo "Comparando " . $numeros[$j-1] . " y " . $numeros[$j] . "\n";
        if ($numeros[$j-1] > $numeros[$j]) {
            $aux = $numeros[$j];
            $numeros[$j] = $numeros[$j-1];
            $numeros[$j-1] = $aux;
        }
    }
}

print_r($numeros);

Referencias

↑ ^a ^b Astrachan, Owen (2003). «Ordenamiento de burbuja: Un anális arqueológico de un algoritmo». SIGCSE (en inglés). Consultado el 9 de marzo de 2011.
↑ Knuth, Donald (1998). «5.2.2: Ordenamiento por intercambio». El arte de programar ordenadores, Volumen 3 (en inglés) (segunda edición). Addison-Wesley. pp. 106-110. ISBN 0-201-89685-0. |fechaacceso= requiere |url= (ayuda)

Véase también

Algoritmo de ordenamiento

Enlaces externos

[Astrachan2003-1] Astrachan, Owen (2003). «Ordenamiento de burbuja: Un anális arqueológico de un algoritmo». SIGCSE (en inglés). Consultado el 9 de marzo de 2011.

[Knuth-2] Knuth, Donald (1998). «5.2.2: Ordenamiento por intercambio». El arte de programar ordenadores, Volumen 3 (en inglés) (segunda edición). Addison-Wesley. pp. 106-110. ISBN 0-201-89685-0. |fechaacceso= requiere |url= (ayuda)

[1]

[2]

@@ Línea 441: / Línea 441: @@
 A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden ''O (n<sup>2</sup>)'' lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden ''O (n<sup>2</sup>)'', otros procedimientos como el [[ordenamiento por inserción]] son considerados más eficientes.
-Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de [[ciencias de la computación]]. A pesar de esto, algunos investigadores como [[Owen Astrachan]] han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio.<ref name="Astrachan2003">Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . [http://www.cs.duke.edu/~ola/papers/bubble.pdf (pdf)] (en inglés)</ref> Sumado a esto, [[Jargon File]], un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y [[Donald Knuth]], uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". <ref name="Knuth">[[Donald Knuth]]. ''[[El arte de programar ordenadores]]'', Volumen 3: ''Clasificación y búsqueda'', Segunda Edición. Addison-Wesley, 1998. ISBN 0-201-89685-0. Páginas 106&ndash;110 de la sección 5.2.2: Ordenamiento por intercambio. (en inglés)</ref>
+Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de [[ciencias de la computación]]. A pesar de esto, algunos investigadores como [[Owen Astrachan]] han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio.<ref name="Astrachan2003">
+{{cita publicación |apellidos=Astrachan |nombre=Owen |año=2003 |título=Ordenamiento de burbuja: Un anális arqueológico de un algoritmo  |publicación=SIGCSE |url=http://www.cs.duke.edu/~ola/papers/bubble.pdf  |fechaacceso=9 de marzo de 2011 |idioma=inglés}}</ref>
+Sumado a esto, [[Jargon File]], un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y [[Donald Knuth]], uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". <ref name="Knuth"> {{cita libro |apellido=Knuth |nombre=Donald |título=[[El arte de programar ordenadores]], Volumen 3 |fechaacceso=9 de marzo de 2011 |idioma=inglés  |edición=segunda |año=1998 |editorial=Addison-Wesley |isbn=0-201-89685-0 |capítulo=5.2.2: Ordenamiento por intercambio |páginas=106-110}}</ref>
 El ordenamiento de burbuja es [[Cota superior asintótica|asintóticamente]] equivalente en tiempos de ejecución con el [[ordenamiento por inserción]] 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ón funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazándolo por el ordenamiento por inserción.
@@ Línea 609: / Línea 612: @@
 print_r($numeros);
 </source>
+== Referencias ==
+{{listaref}}
 == Véase también ==