Adaptivity
Leçon 6 sur 11 du cours Tri à bulles de Coddy.
Nous avons discuté de la complexité temporelle de notre algorithme de tri à bulles, qui est de O(n2) . Mais, que se passe-t-il si notre tableau est déjà trié ? Dans ce cas également, il prendra un temps d'exécution de O(n2).
Qu'est-ce que l'Adaptativité ?
Un algorithme adaptatif est un algorithme qui modifie son comportement en fonction de la séquence d'entrée donnée.
Alors, le tri à bulles est-il adaptatif ?
Oui, nous pouvons rendre notre algorithme de tri à bulles adaptatif. Nous devons écrire l'algorithme de tri à bulles avec un temps d'exécution dans le pire des cas de O(n2) et dans le meilleur des cas de O(n) afin qu'il soit adaptatif. Ici, le meilleur des cas fait référence au cas où le tableau est déjà trié.
Nous utiliserons une variable drapeau (flag) booléenne pour contrôler la boucle while afin que l'algorithme s'arrête plus tôt s'il était déjà trié.
while(flag)
{
//code
}
Nous devons répéter le passage jusqu'à ce que le tableau soit trié. Nous avons déjà appris comment compter le nombre d'échanges (swaps), nous pouvons donc implémenter un drapeau et vérifier si aucun échange n'est requis lors du passage, puis nous pouvons interrompre la boucle.
Défi
MoyenCréez une fonction nommée ad_bubblesort qui reçoit un tableau et la taille du tableau. Implémentez l'algorithme de tri à bulles adaptatif. N'oubliez pas d'utiliser une variable nommée flag pour vérifier les échanges.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Écrivez le code ici
*returnSize = n;
return arr;
}
Toutes les leçons de Tri à bulles
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm