Devoir Maison – Première NSI

Thématiques abordées

Recherche dichotomique (Binary Search)
Tri par insertion et rappel sur le tri
Tri par insertion _dichotomique_

Exercice 1 : Recherche dichotomique

On souhaite écrire une fonction recherche_dichotomique(tab, valeur) qui prend en paramètre :

tab : une liste de nombres triés par ordre croissant,
valeur : la valeur à chercher dans tab.

La fonction doit renvoyer l’indice où se trouve la valeur dans la liste si elle est présente, et -1 sinon.

Rappels sur le principe de la recherche dichotomique

On compare la valeur recherchée avec l’élément central de la liste.
Si la valeur est égale à l’élément central, on a trouvé l’indice !
Si la valeur est plus petite que l’élément central, on restreint la recherche à la sous-liste de gauche.
Si la valeur est plus grande que l’élément central, on restreint la recherche à la sous-liste de droite.
On répète le processus sur la sous-liste correspondante (elle-même coupée en deux, etc.).

À faire

Implémenter la fonction recherche_dichotomique(tab, valeur).
Tester la fonction.

def recherche_dichotomique(tab, valeur):
    """Recherche dichotomique d'une valeur dans un tableau trié.
    Retourne l'indice de la valeur si trouvée, -1 sinon."""
    
    # Compléter le code
    debut = 0
    fin = len(tab) - 1
    
    while debut <= fin:
        # Calcul de l'indice central
        milieu = (debut + fin) // 2
        # Comparaison
        if tab[milieu] == valeur:
            return milieu  # Valeur trouvée
        elif tab[milieu] < valeur:
            debut = milieu + 1
        else:
            fin = milieu - 1
    
    return -1  # Valeur non trouvée

# Tests
liste_test = [1, 3, 5, 7, 9, 11]
print(recherche_dichotomique(liste_test, 7))   # Attendu : 3
print(recherche_dichotomique(liste_test, 2))   # Attendu : -1

3
-1

Exercice 2 : Rappel sur le tri

2.1) Tri par sélection

On vous demande d'implémenter un algorithme de tri par sélection (_selection sort_).

Principe du tri par sélection :

On cherche l’élément minimum dans la liste complète, on l’échange avec l’élément à la position 0.
Ensuite, on cherche le minimum dans la sous-liste qui commence à l’indice 1, et on l’échange avec l’élément en position 1.
On recommence jusqu’à ce que la liste soit triée.

À faire :

Implémenter la fonction tri_selection(tab), qui trie en place la liste tab.
Tester la fonction.

def tri_selection(tab):
    """Trie la liste tab en place par sélection."""
    # Compléter le code
    n = len(tab)
    for i in range(n):
        # Trouver l'index du minimum dans la sous-liste tab[i..n-1]
        indice_min = i
        for j in range(i+1, n):
            if tab[j] < tab[indice_min]:
                indice_min = j
        # Échanger
        tab[i], tab[indice_min] = tab[indice_min], tab[i]
    return tab

# Tests
liste_test = [11, 3, 5, 7, 9, 1]
print(tri_selection(liste_test))  # Doit être triée : [1, 3, 5, 7, 9, 11]

[1, 3, 5, 7, 9, 11]

Exercice 3 : Tri par insertion dichotomique

Dans cet exercice, nous allons mettre en œuvre un tri par insertion amélioré grâce à la recherche dichotomique.

Nous allons découper le travail en deux parties :

Partie A : Écrire la fonction qui détermine la position d’insertion par recherche dichotomique.
Partie B : Écrire le tri par insertion lui-même, qui utilisera la fonction de la Partie A.

Partie A

Position d’insertion par recherche dichotomique

Nous voulons une fonction position_insertion_dichotomique(tab, debut, fin, valeur) qui recherche la position d’insertion appropriée de valeur dans la sous-liste déjà triée tab[debut..fin].

Rappel de la recherche dichotomique

On compare la valeur avec l’élément central de la sous-liste courante.
Si valeur est plus petite, on réduit la recherche à la moitié gauche. Si elle est plus grande, on réduit à la moitié droite.
On itère jusqu’à ce que debut > fin.
Lorsque la boucle se termine, l’indice debut représente l’endroit où insérer la valeur (si elle n’est pas déjà présente).

Consignes

Complétez la fonction ci-dessous pour qu’elle renvoie l’indice où insérer valeur dans l’ordre croissant.
Faites quelques tests simples (vous pouvez utiliser une cellule en dessous) pour valider votre fonction.

def position_insertion_dichotomique(tab, debut, fin, valeur):
    """Retourne l'indice où insérer 'valeur' dans la sous-liste triée tab[debut..fin],
    en utilisant une recherche dichotomique."""
    # TODO : À compléter
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == valeur:
            return milieu
        elif tab[milieu] < valeur:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return debut

Tests (Partie A)

# Exemple de tests simples
sous_liste = [1, 3, 5, 7, 9]
print(position_insertion_dichotomique(sous_liste, 0, 4, 4))  # Attendu 2
print(position_insertion_dichotomique(sous_liste, 0, 4, 10)) # Attendu 5 (en fin)
print(position_insertion_dichotomique(sous_liste, 0, 4, 0))  # Attendu 0 (en début)
print(position_insertion_dichotomique(sous_liste, 0, 4, 7))  # Attendu 3 (7 déjà présent)

Partie B

Tri par insertion dichotomique

On va maintenant utiliser notre fonction position_insertion_dichotomique pour créer un algorithme de tri par insertion :

On considère que la partie [tab(0)] (le premier élément) est "déjà triée".
On parcourt le tableau de l'indice i = 1 jusqu’à n-1.
Pour l’élément tab[i] :
- On trouve sa position d’insertion pos dans la sous-liste tab[0..i-1] (déjà triée) grâce à position_insertion_dichotomique.
- On décale les éléments pour laisser la place à la valeur_a_inserer.
- On insère valeur_a_inserer à l’indice pos.

Travail à faire

Compléter la fonction insertion_dichotomique(tab) ci-dessous.
Tester le résultat sur plusieurs listes différentes.

def insertion_dichotomique(tab):
    """Trie la liste 'tab' en place en utilisant
    le tri par insertion et la recherche dichotomique."""
    # TODO : À compléter
    n = len(tab)
    for i in range(1, n):
        valeur_a_inserer = tab[i]
        # Trouver la position d'insertion dans la sous-liste triée tab[0..i-1]
        pos = position_insertion_dichotomique(tab, 0, i-1, valeur_a_inserer)
        
        # Décaler les éléments vers la droite pour faire de la place
        j = i
        while j > pos:
            tab[j] = tab[j - 1]
            j -= 1
        # Insérer la valeur dans la bonne position
        tab[pos] = valeur_a_inserer
    return tab

Tests (Partie B)

Essayez plusieurs exemples et vérifiez si la liste est réellement triée à la fin.

liste_test1 = [5, 2, 9, 1, 3, 8]
print("Liste triée :", insertion_dichotomique(liste_test1))  # [1, 2, 3, 5, 8, 9]

liste_test2 = [10, 9, 8, 7, 2, 0]
print("Liste triée :", insertion_dichotomique(liste_test2))  # [0, 2, 7, 8, 9, 10]

liste_test3 = [1]
print("Liste triée :", insertion_dichotomique(liste_test3))  # [1]

liste_test4 = []
print("Liste triée :", insertion_dichotomique(liste_test4))  # []

Liste triée : [1, 2, 3, 5, 8, 9]
Liste triée : [0, 2, 7, 8, 9, 10]
Liste triée : [1]
Liste triée : []

Devoirs Première