El número total de comparaciones en la clasificación de burbujas es ( n – 1) + ( n – 2) + (n-3) + (n-4) + (n-5) …… .. (2) + (1) = n ( n – 1) / 2 es decir, n2.
Explicación:
El algoritmo de clasificación de burbujas requiere un par de bucles anidados. El bucle externo debe iterar una vez para cada elemento para los elementos dados, es decir, n veces. mientras que el bucle interno itera n veces para la primera iteración, n-1 veces para la segunda iteración, n-2 veces para la tercera iteración y este proceso continúa.
- Como principiante, ¿debo invertir mi tiempo en escribir mi propio algoritmo de aprendizaje automático desde cero?
- Cómo verificar si un algoritmo que hice en C ++ es eficiente en la vida real
- ¿Cuáles son algunos algoritmos para el comercio de acciones automatizado?
- Cómo completar consultas en tiempo O (1) en un problema RANGESUM en SPOJ
- Cómo demostrar que el camino más corto posible entre dos puntos es una línea recta
Para la primera iteración del bucle externo, cuando intentamos colocar el elemento más grande en su posición correcta, se realizan n – 1 comparaciones, es decir, la primera comparación se realiza entre el primer y el segundo elemento, la segunda comparación se realiza entre segundo y tercer elementos, y así sucesivamente hasta que se haga la (n-1) th comparación entre el (n-1) th y el enésimo elemento.
Para la segunda iteración del bucle externo, no es necesario compararlo con el último elemento de la lista, ya que se colocó en la posición correcta en el pase anterior. Por lo tanto, la segunda iteración requiere solo n-2 comparaciones.
Del mismo modo, la tercera iteración requiere comparaciones (n-3). y así…
Entonces, el número total de comparaciones es ( n – 1) + ( n – 2) + (n-3) + (n-4) + (n-5) …… .. (2) + (1) = n ( n – 1) / 2 es decir, n2
