Tri par insertion

C’est le tri naturel du joueur de cartes qui ramasse celles qui lui sont distribuées et les insère dans son jeu.

Programmer pour lundi un code qui produit ceci, à l’aide de deux boucles imbriquées :

La liste initiale
[8, 6, 2, 9, 3, 4]
On insère le 6
[6, 8, 2, 9, 3, 4]
On insère le 2
[2, 6, 8, 9, 3, 4]
On insère le 9
[2, 6, 8, 9, 3, 4]
On insère le 3
[2, 3, 6, 8, 9, 4]
On insère le 4
[2, 3, 4, 6, 8, 9]
>>> 

Le pseudo-code depuis la page wikipedia :

  procédure tri_insertion(liste t)
       pour rang de 1 à len(t) - 1 # donc for rang in range(len(t)) ;-)

            # mémoriser t[rang] dans carte
            carte ← t[rang]                            

            # décaler vers la droite les éléments de t[0]..t[rang-1] qui sont plus grands que carte en partant de t[rang-1]
            i ← rang                               
            tant que i > 0 et t[i - 1] > carte
                     t[i] ← t[i - 1]
                     i ← i - 1

            # placer carte dans le "trou" laissé par le décalage
            t[i] ← carte

CORRIGÉ :

Déception : peu de codes rendus, mais aussi des satisfactions !
J’ai commenté individuellement sur MBN.

Version 1 – deux boucles imbriquées :

def tri_insertion(t):
    # il faut une liste non vide
    assert len(t) > 0
    print("La liste initiale")
    print(t)
    # parcours de la liste jusqu'à la dernière valeur
    for rang in range(1, len(t)):
        # On veut insérer cette 'carte', on la 'descend' vers la gauche
        # on stocke sa valeur. Le rang est gardé puisque c'est i qui 'descend'
        carte = t[rang]
        print("On insère le", carte)

        # i va décroître donc, en partant de rang
        i = rang
        
        # tant que celle de gauche est plus GRANDE
        # attention à ne pas aller en dessous de zéro !!
        
        while i > 0 and t[i - 1] > carte:
            t[i] = t[i - 1] # on décale vers la droite
            i -= 1          # on descend à gauche

        # on est sorti du while : soit on est à zéro soit c'est
        # en i qu'il faut mettre la carte
        t[i] = carte
        # affichage
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_insertion(t)

Version 2 – en utilisant une fonction insere intercalée :

def insere(t, rang):
    # On veut insérer cette 'carte', on la 'descend' vers la gauche
    # on stocke sa valeur. Le rang est gardé puisque c'est i qui 'descend'
    carte = t[rang]
    print("On insère le", carte)

    # i va décroître donc, en partant de rang
    i = rang
    
    # tant que celle de gauche est plus GRANDE
    # attention à ne pas aller en dessous de zéro !!
    
    while i > 0 and t[i - 1] > carte:
        t[i] = t[i - 1] # on décale vers la droite
        i -= 1          # on descend à gauche

    # on est sorti du while : soit on est à zéro soit c'est
    # en i qu'il faut mettre la carte
    t[i] = carte
    return t

def tri_insertion(t):
    # il faut une liste non vide
    assert len(t) > 0
    print("La liste initiale")
    print(t)
    # parcours de la liste jusqu'à la dernière valeur
    for rang in range(1, len(t)):
        

        # insertion
        t = insere(t, rang)
        
        # affichage
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_insertion(t)

Besoin d’un autre regard ?

Suite de notre progression en NSI ?

Prochain cours lundi 10h sur ce site.

Chat audio lundi à 11h sur discord.

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.