Complexity Analysis
Leçon 5 sur 11 du cours Tri à bulles de Coddy.
Analyse de la complexité du tri à bulles.
La complexité temporelle dépend du nombre de comparaisons et d'échanges effectués.
Nous devons effectuer n passes et dans chaque passe nous avons (n-1) comparaisons. où, n est le nombre d'éléments dans la liste.
Total des comparaisons=(n-1)+(n-1)+(n-1)....n fois
=n*(n-1)
=n2-n
La complexité temporelle de l'algorithme de tri à bulles est O(n2).
Si nous parlons de complexité spatiale, aucun espace supplémentaire n'est utilisé dans l'algorithme, un tri en place est effectué et les éléments sont disposés dans la liste d'origine elle-même.
La complexité spatiale de l'algorithme de tri à bulles est O(1) (Constante).
Défi
FacileCréez une fonction nommée count_swaps qui reçoit un tableau et la taille du tableau. Exécutez l'algorithme de tri à bulles (bubble sort) sur le tableau et comptez le nombre de fois qu'un échange (swap) est effectué.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Écrire le code ici
return 0;
}
Toutes les leçons de Tri à bulles
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm