Complexité de temps de tri de bulles
Dans cet article, le tri ascendant est considéré. Cet article vise à indiquer la vitesse relative de l'algorithme de tri de bulles. Cette vitesse relative est appelée complexité temporelle. Le codage se fait dans le langage informatique C.
Contenu de l'article
- Introduction - Voir ci-dessus
- Illustration de tri à bulles
- Performes pires
- De meilleures performances pour les bulles
- Une séquence d'éléments entrecouchée déjà triée
- Cas parfait
- Conclusion
Illustration de tri à bulles
Considérez la liste non triée suivante:
R x f s u z v jIl y a 8 éléments, qui ont besoin de 8 analyses complètes, ce qui entraîne:
R f s u x v j zF r s u v j x z
F r s u j v x z
F r s j u v x z
F r j s u v x z
F j r s u v x z
F j r s u v x z
F j r s u v x z
La disposition de la liste finale est le tri complet.
Performes pires
Le code C pour trier les huit caractères précédents, expliqué précédemment est:
#inclurevoid bubblesort (char arr [], int n)
int counter = 0;
pour (int i = 0; i < n; i++)
pour (int j = 1; j < n; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
compteur + = 1;
printf ("% i \ n", compteur);
Le code pour l'échange est dans la boucle intérieure imbriquée. Le compteur compte le nombre d'opérations de base. Les boucles pour boucle externe de 0 à 7, je.e., 8 fois. Les boucles intérieures à boucle de 1 à 7, je.e., 7 fois. Le nombre total d'opérations de base (boucle intérieure) est de 8 x 7 = 56. La sortie du compteur est 56.
Si la boucle intérieure en boucle de 0 à 7, alors le nombre total d'opérations de base aurait été de 8 x 8 = 64. Il s'agit du nombre maximum d'opérations de base pour cette nidification pour les boucles. Soit 8 n. Ensuite, le nombre maximum de ces boucles de nidification est n2.
La complexité de temps du pire des cas pour la fonction précédente est donnée comme,
Sur2)
Le Big O suivi de ses parenthèses avec n2 s'appelle la notation Big-o. Il indique la vitesse relative du code. Bien que dans le code précédent, le nombre d'opérations de base est de 56, le nombre maximal possible d'opérations, 82 = 64, c'est ce qui serait donné pour la complexité temporelle.
Une fonction principale C appropriée pour le code précédent est:
int main (int argc, char ** argv)int n = 8;
char arr [] = 'r', 'x', 'f', 's', 'u', 'z', 'v', 'j';
Bubblesort (arr, n);
pour (int i = 0; i
printf ("\ n");
retour 0;
De meilleures performances pour les bulles
Remarquez dans l'illustration précédente pour le tri des bulles; Après le premier scan, l'élément le plus élevé est à l'extrémité droite. Après le deuxième scan, les deux éléments les plus élevés sont à l'extrémité droite, dans l'ordre. Après le troisième scan, les trois éléments les plus élevés sont à la droite, dans l'ordre, et ainsi de suite. Les opérations sur ces éléments à droite à l'extrême au fur et à mesure de leur croissance peuvent être omises dans le codage. Cela augmenterait la vitesse globale (temps pour le tri complet). Le code modifié suivant l'illustre:
void bubblesort (char arr [], int n)int counter = 0;
pour (int i = 0; i < n; i++)
pour (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
compteur + = 1;
printf ("% i \ n", compteur);
Cette fois, la sortie du compteur est de 28. Le nombre d'opérations de base est de 28, un peu moins de la moitié de 64, soit 32. Les boucles intérieures à boucle de 1 à n - i. Dans son premier scan, I est nul et n - i = 8.
Maintenant,
enregistrer2 8 = journal2 23
= 3
8 x 3 = 8xlog2 23
= 24
qui est proche de 28. Soit n = 8. L'expression de l'opérande droit du dernier mais un ci-dessus, devient n.enregistrer2 23, = n.enregistrer2 8, généralement écrit comme, n log n.
Lorsque la complexité temporelle se situe dans une certaine plage moyenne, 20 à 40, dans ce cas, elle est exprimée:
O (n log n)
Où n est le nombre d'éléments dans la liste. Ainsi, la complexité temporelle des performances améliorées du tri des bulles est n log n, ce qui signifie n x logarithme2(n).
Une séquence d'éléments entrecouchée déjà triée
Il y a huit scans pour l'illustration de tri à bulles précédents. Notez que par le sixième scan, la liste était complètement triée. Les deux dernières rangées sont les répétitions de la sixième rangée. Pour cette liste particulière non triée, les deux analyses précédentes n'étaient pas nécessaires. Cela se produit lorsque la liste non triée donnée a des séquences entrecoupées déjà triées. Si la liste donnée est complètement non triée, alors la dernière ligne serait la liste triée finale (ce ne serait pas une répétition de la précédente).
Les dernières lignes comme les deux derniers ci-dessus peuvent être omises dans le tri, et ainsi améliorer les performances (vitesse). Le code suivant illustre ceci:
void bubblesort (char arr [], int n)_Bool échangé = 0;
pour (int i = 0; i < n; i++)
échangé = 0;
pour (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
échangé = 1;
if (échangé == 0)
casser;
Cas parfait
Des performances parfaites se produisent lorsque la liste donnée est déjà complètement triée. Le code à tester est:
void bubblesort (char arr [], int n)int counter = 0;
_Bool échangé = 0;
pour (int i = 0; i < n; i++)
échangé = 0;
pour (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
arr [j - 1] = temp;
échangé = 1;
compteur + = 1;
if (échangé == 0)
casser;
printf ("% i \ n", compteur);
La sortie est:
7F j r s u v x z
pour une liste d'entrée de,
F j r s u v x zLe 7 est de la boucle intérieure. Cependant, pour la complexité temporelle, un maximum de 8 est considéré. La complexité du temps pour des performances parfaites est exprimée comme suit:
Sur)
Conclusion
Dans cet article, nous avons discuté de la complexité du temps de tri des bulles et souligné ce qui suit:
La complexité du temps du pire des cas pour le tri des bulles est:
Sur2)
Avec l'amélioration du code, la complexité temporelle devient:
O (n log n)
Lorsque la liste donnée est déjà complètement triée, la complexité du temps est:
Sur)