Python >> Tutoriel Python >  >> Python

L'algorithme de tri à bulles en Python

Le tri à bulles fait exactement ce que vous attendez de lui. Il trie une liste d'entrée en traitant chaque élément comme une bulle qui monte dans la liste. Chaque bulle monte tant qu'elle est supérieure aux éléments de la liste. Si un élément de liste est inférieur ou égal à un élément de liste, la bulle cesse de monter et l'élément de liste commence à remonter.

Algorithme Python de tri par bulles

def bubblesort(lst):
    for passesLeft in range(len(lst)-1, 0, -1):
        for i in range(passesLeft):
            if lst[i] > lst[i + 1]:
                lst[i], lst[i + 1] = lst[i + 1], lst[i]
    return lst

l = [5, 3, 4, 1, 2, 0]
print(bubblesort(l))
# [0, 1, 2, 3, 4, 5]

Explication de l'algorithme de tri à bulles

L'algorithme précis fonctionne comme suit. La variable d'index externe border marque l'index après lequel les éléments de droite de la liste sont déjà triés.

La variable d'index interne i va de gauche à droite jusqu'à ce qu'il atteigne la bordure de la variable d'index. Sur son chemin vers la droite, il commute deux éléments de liste suivants si le premier élément est plus grand que le deuxième élément.

Ainsi, après le premier passage, le plus grand élément de la liste se trouve à droite. Comme cet élément le plus à droite est déjà trié, on peut réduire de un la taille de la liste à trier, c'est-à-dire décrémenter la variable border.

Ensuite, le deuxième plus grand élément montera vers le haut et la procédure se répétera.

Étudiez attentivement ce modèle algorithmique de base. Tous les informaticiens et tous les grands codeurs doivent le savoir.

Puzzle de tri à bulles

Pouvez-vous résoudre le puzzle suivant sur notre application de puzzle interactive Finxter ? (Cliquez pour résoudre)


Êtes-vous un codeur maître?
Testez vos compétences maintenant !

Vidéo sur le tri à bulles


Post précédent