Tris simples : tri par sélection et tri par insertion

En 30 secondes

• Trier un tableau, c'est ranger ses éléments en ordre croissant (ou décroissant) ; sélection et insertion donnent le même résultat par des chemins différents.
• Tri par sélection : à chaque étape, le minimum de la partie non triée est placé en tête de cette partie (échange).
• Tri par insertion : chaque élément est glissé à sa place parmi les précédents déjà triés ; très rapide si le tableau est presque trié.

Ce que tu sauras faire

• Comprendre ce que signifie trier un tableau et distinguer le tri par sélection du tri par insertion.
• Dérouler à la main un tri par sélection en cherchant le minimum de la partie non triée à chaque étape.
• Dérouler à la main un tri par insertion en insérant chaque élément à sa place parmi les précédents.

Les mots à connaître

Tableau

une structure de données qui stocke une suite de valeurs, chacune repérée par son indice (sa position).

Indice

la position d'un élément dans un tableau, en commençant à 0 pour le premier élément.

Tri

l'opération qui range les éléments d'un tableau dans l'ordre croissant (ou décroissant).

Le piège classique

Confondre tri par sélection (chercher le minimum de la partie non triée et l'échanger en tête) et tri par insertion (insérer chaque élément à sa place parmi les précédents).

L'astuce

Tri par SÉLECTION : à chaque étape, je cherche le plus petit de ce qui RESTE à trier et je le mets en tête. La partie triée grandit à gauche.