Tri par insertion
La méthode du tri par insertion repose sur un double parcours de la liste à trier :
- un parcours de gauche à droite commençant au deuxième élément avec un indice \(i\). On a la garantie que la liste jusqu'à l'indice \(i\) exclu est triée ;
- un parcours de droite à gauche du début de la liste jusqu'à l'indice \(i\) pour y insérer à la bonne place l'élément d'indice \(i\). Ce parcours utilise un indice \(j\).
La fonction tri_insertion suivante prend en paramètre un tableau de nombres tableau et le trie dans l'ordre croissant en utilisant cette méthode.
Il s'agit d'un tri en place ce qui signifie que le tableau passé en paramètre sera directement modifié. Il est inutile de le renvoyer.
Compléter la fonction pour qu'elle réponde à la spécification demandée.
Exemples
>>> tableau_0 = [9, 5, 8, 7, 6]
>>> tri_insertion(tableau_0)
>>> tableau_0
[5, 6, 7, 8, 9]
>>> tableau_1 = [2, 5, -1, 7, 0, 28]
>>> tri_insertion(tableau_1)
>>> tableau_1
[-1, 0, 2, 5, 7, 28]
>>> un_seul = [9]
>>> tri_insertion(un_seul)
>>> un_seul
[9]
>>> tableau_vide = []
>>> tri_insertion(tableau_vide)
>>> tableau_vide
[]
def tripy-undinsertion(tableau):bksl-nl n = len(tableau)bksl-nl for i in range(1, n):bksl-nl j = ...bksl-nl valeurpy-undapy-undinserer = tableau[...]bksl-nl while j > ... and valeurpy-undapy-undinserer < tableau[...]:bksl-nl tableau[j] = tableau[j - 1]bksl-nl j = ...bksl-nl tableau[j] = ...bksl-nlbksl-nlbksl-nl# Testsbksl-nltableaupy-und0 = [9, 5, 8, 7, 6]bksl-nltripy-undinsertion(tableaupy-und0)bksl-nlassert tableaupy-und0 == [5, 6, 7, 8, 9]bksl-nlbksl-nltableaupy-und1 = [2, 5, -1, 7, 0, 28]bksl-nltripy-undinsertion(tableaupy-und1)bksl-nlassert tableaupy-und1 == [-1, 0, 2, 5, 7, 28]bksl-nlbksl-nlunpy-undseul = [9]bksl-nltripy-undinsertion(unpy-undseul)bksl-nlassert unpy-undseul == [9]bksl-nlbksl-nltableaupy-undvide = []bksl-nltripy-undinsertion(tableaupy-undvide)bksl-nlassert tableaupy-undvide == []bksl-nlbksl-nldef tripy-undinsertion(tableau):bksl-nl n = len(tableau)bksl-nl for i in range(1, n):bksl-nl j = ibksl-nl valeurpy-undapy-undinserer = tableau[i]bksl-nl while j > 0 and valeurpy-undapy-undinserer < tableau[j - 1]:bksl-nl tableau[j] = tableau[j - 1]bksl-nl j = j - 1bksl-nl tableau[j] = valeurpy-undapy-undinsererbksl-nlbksl-nl
A
L'algorithme du tri par insertion est un algorithme classique à connaître.
La variable ici nommée valeur_a_inserer est souvent nommée cle.
Z