Complexity Analysis
Lección 5 de 11 del curso Ordenamiento de burbuja de Coddy.
Análisis de complejidad del ordenamiento de burbuja (bubble sort).
La complejidad temporal depende del número de comparaciones e intercambios realizados.
Tenemos que realizar n pasadas y en cada pasada tenemos (n-1) comparaciones, donde n es el número de elementos en la lista.
Comparaciones totales=(n-1)+(n-1)+(n-1)....n veces
=n*(n-1)
=n2-n
La complejidad temporal para el algoritmo de ordenamiento de burbuja es O(n2).
Si hablamos de la complejidad espacial, no se utiliza espacio adicional en el algoritmo, se realiza un ordenamiento in-place y los elementos se organizan en la propia lista original.
La complejidad espacial para el algoritmo de ordenamiento de burbuja es O(1) (Constante).
Desafío
FácilCrea una función llamada count_swaps que recibe un arreglo y el tamaño del mismo. Realiza el algoritmo de ordenamiento de burbuja en el arreglo y cuenta el número de veces que se realizan intercambios.
Pruébalo tú mismo
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Escribe el código aquí
return 0;
}
Todas las lecciones de Ordenamiento de burbuja
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm