Ordenación por burbujas frente a Ordenación por inserción
La clasificación de burbujas es un algoritmo de clasificación que funciona recorriendo la lista para ordenarla repetidamente mientras compara pares de elementos que son adyacentes. Si un par de elementos está en el orden incorrecto, se intercambian para colocarlos en el orden correcto. Este recorrido se repite hasta que no se requieren más intercambios. La ordenación por inserción también es un algoritmo de ordenación, que opera insertando un elemento en la lista de entrada en la posición correcta en una lista que ya está ordenada. Este proceso se aplica repetidamente hasta que se ordena la lista.
¿Qué es la clasificación por burbujas?
La clasificación de burbujas es un algoritmo de clasificación que funciona recorriendo la lista para ordenarla repetidamente mientras compara pares de elementos que son adyacentes. Si un par de elementos está en el orden incorrecto, se intercambian para colocarlos en el orden correcto. Este recorrido se repite hasta que no se requieren más intercambios (lo que significa que la lista está ordenada). Dado que los elementos más pequeños de la lista aparecen en la parte superior cuando una burbuja sale a la superficie, se le da el nombre de tipo de burbuja. Bubble sort es un algoritmo de clasificación muy simple, pero tiene una complejidad de tiempo de caso promedio de O (n2) al clasificar una lista con n elementos. Debido a esto, la ordenación por burbujas no es adecuada para ordenar listas con una gran cantidad de elementos. Pero debido a su simplicidad, la clasificación de burbujas se enseña durante las introducciones a los algoritmos.
¿Qué es la ordenación por inserción?
La ordenación por inserción es otro algoritmo de ordenación que opera insertando un elemento en la lista de entrada en la posición correcta en una lista (que ya está ordenada). Este proceso se aplica repetidamente hasta que se ordena la lista. En la clasificación por inserción, la clasificación se lleva a cabo en el lugar. Por lo tanto, después de la i-ésima iteración del algoritmo, las primeras i+1 entradas de la lista se ordenarán y el resto de la lista no se ordenará. En cada iteración, el primer elemento de la parte no ordenada de la lista se tomará y se insertará en el lugar correcto en la sección ordenada de la lista. La ordenación por inserción tiene una complejidad de tiempo de caso promedio de O(n2). Debido a esto, la ordenación por inserción tampoco es adecuada para ordenar listas grandes.
¿Cuál es la diferencia entre la clasificación por burbuja y la clasificación por inserción?
Aunque tanto el algoritmo de ordenación por burbuja como por inserción tienen complejidades de tiempo de caso promedio de O(n2), la ordenación por burbuja casi siempre es superada por la ordenación por inserción. Esto se debe a la cantidad de intercambios que necesitan los dos algoritmos (la clasificación de burbujas necesita más intercambios). Pero debido a la simplicidad del tipo de burbujas, el tamaño de su código es muy pequeño. También existe una variante de ordenación por inserción llamada ordenación por shell, que tiene una complejidad temporal de O(n3/2), lo que permitiría su uso práctico. Además, la ordenación por inserción es muy eficaz para ordenar listas "casi ordenadas", en comparación con la ordenación por burbuja.
