Tri par insertion

Le tri par insertion, c'est exactement ce que tu fais quand tu tries des cartes que tu recois une par une. Tu tiens les cartes deja triees dans ta main gauche, et a chaque nouvelle carte, tu l'inseres au bon endroit.

En pratique :
- Tu consideres que le premier élément est deja trie (une seule carte = triee)
- Tu prends l'élément suivant (la cle)
- Tu le compares aux éléments deja tries en partant de la droite
- Tu decales vers la droite tous les éléments plus grands que la cle
- Tu inseres la clé a la position liberee

C'est O(n²) dans le pire cas, mais O(n) si la liste est deja presque triee. C'est souvent le meilleur choix pour de petites listes.

Écris une fonction tri_insertion(lst) qui trie une liste en place.

Exemple :
lst = [9, 5, 1, 4, 3]
tri_insertion(lst)
Apres l'appel, lst vaut [1, 3, 4, 5, 9]

Tests (2/4)

Tri basique

lst = [9, 5, 1, 4, 3]
tri_insertion(lst)
assert lst == [1, 3, 4, 5, 9]

Deja trie

lst = [1, 2, 3, 4]
tri_insertion(lst)
assert lst == [1, 2, 3, 4]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def tri_insertion(lst):
    for i in range(1, len(lst)):
        clé = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > cle:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = cle

← Tri par selection Tri fusion (merge sort) →

solution.py

Bravo!

Tri par insertion

Tests (2/4)

Indices (3 disponibles)

Solution officielle