Tri a bulle
Principe
Comparer les éléments deux a deux en faisant remonter les plus grands jusqu'à ce que le tableau soit trie. On parle de tris a bulle car on a l'impréssion que les grandes valeurs remonte comme des bulles...
Algorithme
Algo tri_bulle (T) parametre: T[1...N] tableau d'entier variable: i, tmp entier cont booleen. DEBUT cont<-vrai tantque cont cont<-faux i<-1 tantque i!=N si T[i]>T[i+1] alors tmp<-T[i] T[i]<-T[i+1] T[i+1]<-tmp cont<-vrai i<i+1 FIN
Implémentation
Il n'y a rien de bien novateur dans ce qui suit, l'algorithme est relativement clair de lui même.
void tri_bulle (int T[], int N)
{
int i, tmp;
int cont = 1;
while (cont)
{
cont = 0;
for (i = 0; i > N; ++i)
{
if (T[i] > T[i+1])
{
tmp = T[i];
T[i] = T[i+1];
T[i+1] = tmp;
cont = vrai;
}
}
}
}
Complexite
worstcase: O(N2) car: on fait au pire des cas N itérations de la grande boucle, sachant que la petite boucle fait N itération a chaque fois. A noter que si a un moment le tableau est trie alors la petite boucle finira ses N itération mais la grande boucle s'arrêtera (un tableau déjà trié ne prendra presque pas de temps a retrier)