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.

Information, représentation des données (3)

On a vue ensemble l’écriture binaire de nombres décimaux.

Il reste à voir comment ils peuvent être codés en mémoire. Pour cela, les normes en vigueur définissent les flottants, en simple précision sur 32 bits (float), et en double précision sur 64 bits (double).

Je vous propose de commencer par ce petit test pour rassembler vos connaissances et découvrir et vous frotter aux difficultés du jour :

On ne triche pas et on cherche avant de continuer !

On suppose que vous avez bien cherché… On va tout détailler !

cm 2020-03-19 ISN virgule flottante 01

cm 2020-03-19 ISN virgule flottante 02

cm 2020-03-19 ISN virgule flottante 03

On explique pourquoi :

>>> 0.1 + 0.1 + 0.1
0.30000000000000004
>>>

cm 2020-03-19 ISN virgule flottante 04

Remarque : attention aux codes avec les flottants !

« 0.2 + 0.1 n’est pas égal à 0.3. Il faut éviter de tester l’égalité de deux flottants. »

Illustrons-le avec un petit code python très maladroit :

nombre = 0.1

while nombre != 1 :
    nombre += 0.1
    print(nombre)

Il faut en effet éviter de tester l’égalité de deux flottants :

>>> 
======== RESTART: cm 2020-02-03 NSI exemple1.py ========
0.2
0.30000000000000004
0.4
0.5
0.6
0.7
0.7999999999999999
0.8999999999999999
0.9999999999999999
1.0999999999999999
1.2
1.3
...

Il nous a fallu une interruption (Ctrl-C) pour ce programme qui tournait en boucle infinie !

Conclusion pour l’oral du bac ISN ?

Encore un exercice ?

cm 2020-03-19 ISN virgule flottante 05cm 2020-03-19 ISN virgule flottante 06

A mettre en simple précision sur 32 bits.

On peut vérifier avec ce convertisseur :

  • 6,625 donne 01000000 11010100 00000000 00000000
  • 5,4375 donne 01000000 10101110 00000000 00000000

 

Tri par sélection

On veut donc trier un tableau ou pour nous une liste qu’on nomme ici t.

t = [8, 6, 2, 9, 3, 4]

Questions 1 :

  • Que vaut len(t) ?
  • Que vaut t[0] ? t[1] ?
  • Que vaut t[5] ? t[6] ?
  • Que vaut t[-1] ?

Réponses 1 :

Question 2 :

  • Comment trouver l’indice du minimum de cette liste ?
t = [8, 6, 2, 9, 3, 4]

Réponse 2 :

En code, qu’est-ce que ça donne ?

def indice_minimum(liste):
    assert len(liste) > 0
    i_min = ...
    for i in range(..., ......):
        if liste[...] < liste[...]:
            i_min = ...
    return ...

Question 3 :

  • Compléter le code ci-dessus.
    Pour le tester :

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

Réponse 3 :

Question 4 :

  • Comment intervertir les valeurs de deux variables a et b en python ?

Réponse 4 :

  • En python, c’est plus facile que dans d’autres languages :
    >>> a = 42
    >>> b = 21
    >>> a, b
    (42, 21)
    >>> a, b = b, a # interversion
    >>> a, b
    (21, 42)
    >>> a
    21
    >>> b
    42
    >>>  # c'est gagné 🙂

Le tri en lui même

Reprenons maintenant notre tri, comme sur la vidéo. Les étapes sont :

[8, 6, 2, 9, 3, 4]
indice du minimum : 2
On intervertit les valeurs des rangs 0 et 2
[2, 6, 8, 9, 3, 4]
indice du minimum : 4
On intervertit les valeurs des rangs 1 et 4
[2, 3, 8, 9, 6, 4]
indice du minimum : 5
On intervertit les valeurs des rangs 2 et 5
[2, 3, 4, 9, 6, 8]
indice du minimum : 4
On intervertit les valeurs des rangs 3 et 4
[2, 3, 4, 6, 9, 8]
indice du minimum : 5
On intervertit les valeurs des rangs 4 et 5
[2, 3, 4, 6, 8, 9]
>>> 

On a donc deux boucles imbriquées (je proposerai un corrigé avec deux fonctions pour éviter cette lourdeur) :

  • une boucle « extérieure » avec une indice rang qui parcourt la liste t an allant des rangs 0 à 4 ici, donc de 0 à len(t) - 2 en règle générale,
    • une boucle « intérieure » avec un indice i qui cherche l’indice du minimum i_min,
    • on intervertit alors t[rang] et t[i_min] après cette boucle « intérieure ».

En pseudo-code, l’algorithme du tri par sélection est (source Wikipedia) :

  procédure tri_selection(liste t)
      pour rang de 0 à len(t) - 2
          i_min ← rang       
          pour i de rang + 1 à len(t) - 1
              si t[i] < t[i_min], alors i_min ← i
          fin pour
          si i_min ≠ rang, alors échanger t[rang] et t[i_min]
      fin pour
  fin procédure

Mieux comprendre le rôle des indices ? Une nouvelle vidéo :

Question 5 pour vendredi :

  • programmer une fonction tri_selection(t) qui effectue ce tri.
  • déposer ce code dans la collecte prévue à cet effet sur mon bureau numérique.

Réponse 5, finalement samedi – CORRIGÉ :

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

Version 1 – deux boucles imbriquées :

def tri_selection(t):
    # il faut une liste non vide
    assert len(t) > 0
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        # on initialise
        i_min = rang
        # on parcourt le reste de la liste
        for i in range(rang + 1, len(t)):
            # si on trouve plus petit ...
            if t[i] < t[i_min]:
                # ... alors l'indice change !
                i_min = i
        print("indice du minimum :", i_min)

        if i_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", i_min)
            t[rang], t[i_min] = t[i_min], t[rang]
        print(t)

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

Version 2 – en utilisant la fonction indice_minimum :

def indice_minimum(liste, rang):
    # il faut une liste non vide
    assert len(liste) > 0
    # on initialise
    i_min = rang
    # on parcourt le reste de la liste
    for i in range(rang + 1, len(liste)):
        # si on trouve plus petit ...
        if liste[i] < liste[i_min]:
            # ... alors l'indice change !
            i_min = i
    # On renvoie l'indice du minimum
    return i_min

def tri_selection(t):
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        ind_min = indice_minimum(t, rang)
        print("indice du minimum :", ind_min)
        if ind_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", ind_min)
            t[rang], t[ind_min] = t[ind_min], t[rang]
        print(t)

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

Besoin d’un autre regard ?

Suite de notre progression en NSI ?

  • Corrigé et autre algorithme de tri vendredi.
  • Salon de discussion discord lundi prochain le 23 mars à 11h00.

Bon courage !