Complexity Analysis
Lição 5 de 11 do curso Bubble Sort da Coddy.
Análise de complexidade do bubble sort.
A complexidade de tempo depende do número de comparações e trocas realizadas.
Temos que realizar n passagens e em cada passagem temos (n-1) comparações. Onde, n é o número de elementos na lista.
Total de comparações=(n-1)+(n-1)+(n-1)....n vezes
=n*(n-1)
=n2-n
A complexidade de tempo para o algoritmo bubble sort é O(n2).
Se falarmos sobre a complexidade de espaço, nenhum espaço extra é usado no algoritmo, a ordenação in-place está sendo realizada e os elementos são organizados na própria lista original.
A complexidade de espaço para o algoritmo bubble sort é O(1) (Constante).
Desafio
FácilCrie uma função chamada count_swaps que recebe um array e o tamanho do array. Execute o algoritmo bubble sort no array e conte o número de vezes que a troca (swapping) é realizada.
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Escreva o código aqui
return 0;
}
Todas as lições de Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm