19. Insertion Sort (Tri par Insertion) : Concept et Implémentation (O(N²))

L'Insertion Sort est souvent comparé au tri d'une main de cartes à jouer. Il est très efficace pour les petits tableaux ou les tableaux presque triés.

Concept

Il itère à travers le tableau, prenant un élément à la fois (la 'clé') et l'insérant à sa position correcte au sein de la partie déjà triée du tableau.

Étapes d'Implémentation

1. Commencer avec le deuxième élément (supposer que le premier est trié).
2. Prendre cet élément (la clé).
3. Décaler les éléments de la partie triée qui sont supérieurs à la clé d'une position vers la droite.
4. Insérer la clé dans l'espace libre.

python def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 # Move elements of arr[0..i-1], that are greater than key, # to one position ahead of their current position while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr