Découvrez le fonctionnement des algorithmes

Tri à bulles

4 mars 2019 à 10:23:36

Bonjour.

Deux questions aujourd'hui à propos du chapitre "Triez les informations" et donc sur le tri à bulles :

1) est-ce que quelqu'un pourrait m'expliquer cette phrase :

"Si nous réfléchissons bien, il faut faire un nombre de boucles correspondant au nombre d'items restants à trier dans la liste au carré."

Je ne comprends pas ce que vient faire le "carré" dans cette histoire... Et puis, "tour de boucle" signifie bien, dans ce cas, le parcours complet par la variable d'une plage de chiffres et pas une seule comparaison, non ?

2) Si on suit ce qui écrit, il me semble que le code suivant :

def inter(a_list):

for i in range(0, len(a_list) - 1):

for j in range(0, len(a_list) - 1):

if a_list[j + 1] < a_list[j]:

a_list[j+1], a_list[j] = a_list[j], a_list[j+1]

 return a_list

pourrait être plutôt :

def inter(a_list):

for i in range(1, len(a_list) - 1):

for j in range(0, i - 1):

if a_list[j + 1] < a_list[j]:

a_list[j+1], a_list[j] = a_list[j], a_list[j+1]

 return a_list

Si je ne me trompe pas, le tour de boucles pour i = 0 est inutile et si on suit les explications données, il faut que la plage parcourue par "j" diminue en fonction de "i".

Qu'en pensez-vous ?

Bonne journée.

Un débutant

11 mars 2019 à 9:31:51

Pas d'avis sur la question ?

Splintz

4 juin 2019 à 21:01:29

En faite le tour de boucle au carré vient du fais que pour chaque valeur de la liste tu vas de voir tester avec toutes les valeurs qui n'ont pas encore été triées, du coup tu vas tester avec "N" variables dans le pire des cas et tu va le faire "N" fois, donc "N²" opérations (même si en réalité, il y en a moins le théorème d'accélération linaire nous dis que deux complexité sont égales si elle ne diffère que d'une constante).

Et en effet il est inutile de tester toutes les variables à tous les tours de boucle