Diferencia entre el ordenamiento de la burbuja y el ordenamiento por inserción

Burbuja Ordenar vs Inserción Ordenar

La ordenación de burbujas es un algoritmo de clasificación que funciona al pasar por la lista para ordenarse repetidamente mientras se comparan los pares de elementos 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 requieran más swaps. La ordenación por inserción también es un algoritmo de clasificación, que opera al insertar 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 la lista se ordena..

Que es Bubble Sort?

La ordenación de burbujas es un algoritmo de clasificación que funciona al pasar por la lista para ordenarse repetidamente mientras se comparan los pares de elementos 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 requieran más swaps (lo que significa que la lista está ordenada). Dado que los elementos más pequeños en la lista llegan a la parte superior a medida que una burbuja sale a la superficie, se le da el nombre de burbuja de clasificación. El ordenamiento de burbuja es un algoritmo de clasificación muy simple, pero tiene una complejidad de tiempo de caso promedio de O (n2) al ordenar una lista con n elementos. Debido a esto, la clasificación de burbujas no es adecuada para clasificar listas con un gran número de elementos. Pero debido a su simplicidad, el ordenamiento por burbuja se enseña durante las introducciones a los algoritmos..

¿Qué es la clasificación por inserción??

La ordenación por inserción es otro algoritmo de clasificación, que opera al insertar 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 la lista se ordena. En la ordenación por inserción, la clasificación se lleva a cabo in situ. Por lo tanto, después de la iteración del algoritmo, las primeras entradas de i + 1 en la lista se ordenarán y el resto de la lista no se ordenará. En cada iteración, el primer elemento en la parte no clasificada de la lista se tomará y se insertará en el lugar correcto en la sección ordenada de la lista. El orden de 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 Bubble Sort y Insertion Sort??

A pesar de que tanto la clasificación de burbujas como los algoritmos de clasificación de inserción tienen una complejidad de tiempo de caso promedio de O (n2), la clasificación de burbuja es casi siempre superada por la clasificación de inserción. Esto se debe a la cantidad de swaps que necesitan los dos algoritmos (los tipos de burbuja necesitan más swaps). Pero debido a la simplicidad del tipo de burbuja, su tamaño de código es muy pequeño. También hay una variante de clasificación de inserción llamada ordenación de shell, que tiene una complejidad de tiempo de O (n3 / 2), que permitiría su uso práctico. Además, la ordenación por inserción es muy eficiente para clasificar listas "casi ordenadas", en comparación con la ordenación por burbujas.