Implementation (Part 2)

Leçon 6 sur 9 du cours Tri par insertion - Série DSA de Coddy.

Scénario : Tri de [5, 2, 9, 1, 5]

Étape 1 : État initial

Tableau d'origine : [5, 2, 9, 1, 5]
Imaginez ceci comme notre main de cartes (ou un tableau de nombres).

Étape 2 : Premier élément (i=1, key=2)

Nous commençons par la deuxième carte (élément) : key = 2.
Comparez 2 avec 5 (le seul élément trié jusqu'à présent).
Puisque 2 est plus petit, nous décalons 5 vers la droite et insérons 2 à sa place.
Tableau mis à jour : [2, 5, 9, 1, 5]

Étape 3 : Deuxième élément (i=2, key=9)

Passons à la carte suivante : key = 9.
Comparez 9 avec 5.
Puisque 9 est plus grand, il n'est pas nécessaire de décaler.
Tableau mis à jour : [2, 5, 9, 1, 5] (aucun changement)

Étape 4 : Troisième élément (i=3, key=1)

Passons à la carte suivante : key = 1.
Comparez 1 avec 9, puis avec 5.
Décalez 9 et 5 vers la droite, en faisant de la place pour 1.
Tableau mis à jour : [1, 2, 5, 9, 5]

Étape 5 : Quatrième élément (i=4, key=5)

Passons à la carte suivante : key = 5.
Comparez 5 avec 9.
Puisque 5 est plus petit, il n'est pas nécessaire de décaler.
Tableau mis à jour : [1, 2, 5, 9, 5] (aucun changement)

Étape 6 : Cinquième élément (i=5, key=5)

Passons à la dernière carte : key = 5.
Comparez 5 avec 9.
Puisque 5 est plus petit, il n'est pas nécessaire de décaler.
Tableau mis à jour : [1, 2, 5, 5, 9]

Résultat final :

Tableau trié : [1, 2, 5, 5, 9]

À chaque étape, nous choisissons une carte (élément), nous la comparons avec celles déjà triées et nous la plaçons au bon endroit, en décalant les autres si nécessaire. Nous répétons ce processus jusqu'à ce que l'ensemble du tableau soit trié.

Défi

Facile

Maintenant, implémentez la boucle interne, qui effectue le tri pour chaque élément.

Complétez le tri à l'intérieur de la fonction insertionSort.

La fonction doit également afficher les éléments du tableau à la fin, un par un, avec une nouvelle ligne entre chaque.

Utilisez les leçons précédentes et l'indice comme référence :)

Essayez vous-même

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        print(key)

Toutes les leçons de Tri par insertion - Série DSA

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Leçon de projet

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2