Diferencia entre el tipo de burbujas y el tipo de inserción

Clasificación de burbujas vs inserción

La clasificación de burbujas es un algoritmo de clasificación que funciona al pasar por la lista para ser ordenado repetidamente mientras se compara pares de elementos adyacentes. Si un par de elementos está en el orden incorrecto, se intercambia para colocarlos en el orden correcto. Este recorrido se repite hasta que no se requieran más intercambios. La clasificación de inserción también es un algoritmo de clasificación, que funciona 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 ordene la lista.

¿Qué es el tipo de burbuja??

La clasificación de burbujas es un algoritmo de clasificación que funciona al pasar por la lista para ser ordenado repetidamente mientras se compara pares de elementos adyacentes. Si un par de elementos está en el orden incorrecto, se intercambia 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 en la lista llegan a la cima cuando una burbuja llega a la superficie, se le da el nombre de burbujas. La clasificación de burbujas es un algoritmo de clasificación muy simple, pero tiene una complejidad promedio de tiempo de caso de O (N2) cuando se clasifica una lista con n elementos. Debido a esto, la clasificación de burbujas no es adecuada para clasificar listas con una gran cantidad de elementos. Pero debido a su simplicidad, la clasificación de burbujas se enseña durante las presentaciones a los algoritmos.

¿Qué es el tipo de inserción??

La clasificación de inserción es otro algoritmo de clasificación, que funciona 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 ordene la lista. En el tipo de inserción, la clasificación se lleva a cabo en el lugar. Por lo tanto, después de la i -ésica del algoritmo, las primeras entradas I+1 en la lista se ordenarán y el resto de la lista no. En cada iteración, el primer elemento en la parte no clasificada de la lista se tomará e insertará en el lugar correcto en la sección ordenada de la lista. El tipo de inserción tiene una complejidad promedio de tiempo de caso de O (N2). Debido a esto, el orden de inserción tampoco es adecuado para clasificar grandes listas.

¿Cuál es la diferencia entre la clasificación de burbujas y el tipo de inserción??

A pesar de que tanto el tipo de burbujas como los algoritmos de clasificación de inserción tienen complejidades promedio de tiempo de casos de O (N2), la clasificación de burbujas tiene casi todo el tiempo superado por el tipo de inserción. Esto se debe a la cantidad de intercambios que necesitan los dos algoritmos (las clases de burbujas necesitan más intercambios). Pero debido a la simplicidad de la clasificación de burbujas, el tamaño de su código es muy pequeño. También hay una variante de clasificación de inserción llamada Shell Sort, que tiene una complejidad de tiempo de O (N3/2), que permitiría que se use prácticamente. Además, el tipo de inserción es muy eficiente para clasificar listas "casi clasificadas", en comparación con el tipo de burbuja.