Troisième manche ( 1 2 4 6) -> ( 1 2 4 6): Pas de permutation en 1 er élément. (1 2 4 6) -> (1 2 4 6): Aucun échange dans les deux éléments suivants. (1 2 4 6) -> (1 2 4 6): Aucun échange dans les deux derniers éléments. Comme aucun échange n'a eu lieu à aucun stade, l'algorithme comprend maintenant que le tri est parfait. Le tri par bulles a son nom parce que les éléments remontent dans le bon ordre, comme des bulles remontant à la surface. Tri à bulles en langage Python Voyons maintenant l'implémentation logique du tri à bulles via python. Python est un langage très largement utilisé de nos jours. Le comprendre à l'aide de python vous donnera sûrement la confiance nécessaire pour pouvoir également l'écrire dans d'autres langues. Code Python def bubble_Sort(arr): m = len(arr) # Traverse through all the array elements for u in range(m): for v in range(0, mu-1): # traverse the array from 0 to mu-1 # Swap if the element is greater than adjacent next one if arr(v) > arr(v+1): arr(v), arr(v+1) = arr(v+1), arr(v) Pour imprimer le tableau après le tri à bulles, vous devez suivre le code: for i in range(len(arr)): print("%d"%arr(i)), Here arr will be your array.
Lors de ce nouveau passage on peut ignorer la dernière case du tableau, car celle-ci contient déjà l'élément le plus grand et ne nécessite donc pas d'être traitée à nouveau. [ 1, 2, 4, 3, 5] # On compare 1 et 2 et on ne fait rien. [ 1, 2, 4, 3, 5] # On compare 2 et 4 et on ne fait rien. [ 1, 2, 4, 3, 5] # On compare 4 et 3 et on les inverse. [ 1, 2, 3, 4, 5] # Fin du deuxième passage On recommence par faire un nouveau passage pour les 3 premières cases du tableau qui ne sont potentiellement pas encore dans l'ordre. Voici le pseudo-code du tri à bulles (version non-optimisée), où \(n\) est la longueur du tableau T à trier. Tri-Bulles(T) pour i de n-1 à 1 // (pas -1) pour j de 0 à i - 1 si T[j] > T[j+1] T[j] <-> T[j+1] // inverser T[j] et T[j+1]: Implémentez cette version de l'algorithme en Python et testez-là en lui donnant en entrée une liste aléatoire de nombres entiers. Pour générer une liste L de t nombres entiers aléatoires compris dans l'interval [a, b) on peut écrire: L = random.
: Implémentez le tri par paquets en suivant les étapes suivantes: Initialisez une liste de listes (urnes) vides. Parcourez le tableau à trier et mettez chaque élément dans l'urne qui lui correspond. Triez chaque urne en utilisant le tri par insertion. Parcourez les urnes dans l'ordre et remettez les éléments dans le tableau initial. Testez votre implémentation sur un tableau de grande taille généré aléatoirement. Comparez ses performances aux autres algorithmes de tri. Autres algorithmes de tri Implémentez les deux autres algorithmes de tri vus en cours ( tri par insertion et tri rapide).
Ainsi, la complexité du temps est O (n ^ 2) Pour n nombre de nombres, le nombre total de comparaisons effectuées sera (n - 1) +... Cette somme est égale à (n-1) * n / 2 (voir Nombres triangulaires) qui équivaut à 0, 5 n ^ 2 - 0, 5 n soit O (n ^ 2)