Tris quadratiques
Trier - réorganiser les éléments d'un tableau (liste) dans un ordre donné.
Méthode bulle (tri à bulles), ou tri par échanges simples).
Un classique immortel du genre. Le principe d'action est simple : on fait le tour du tableau du début à la fin, en échangeant simultanément des éléments voisins non triés. À la suite du premier passage à la dernière place, "apparaît" élément maximal. Maintenant, nous contournons à nouveau la partie non triée du tableau (du premier élément à l'avant-dernier) et changeons les voisins non triés en cours de route. Le deuxième plus grand élément sera à l'avant-dernière place. En continuant dans le même esprit, nous allons contourner la partie non triée toujours décroissante du tableau, poussant les maximums trouvés jusqu'à la fin.
Source
Implémentation algorithmique de cet algorithme
BOUCLE POUR J=1 À N-1 ÉTAPE 1
F=0
BOUCLE POUR I=1 VERS N-J-1 ETAPE 1
SI UN[I] > ; A[I+1] ALORS
ECHANGE A[I],A[I+1]
F=1
ENSUITE JE
SI F=0 ALORS SORTIR DE LA BOUCLE // s'il n'y a pas eu d'échanges lors de la passe,
// cela signifie tous les éléments
// rangé dans l'ordre
SUIVANT J
Complexité de cet algorithme : \(\displaystyle O(n^{2})\).
Informations utiles supplémentaires : Article Wikipédia.