Introduction aux algorithmes de tri

Programme

Notions	Compétences	Remarques
Tris par insertion, par sélection	Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.	La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas.

Le tri en informatique

Dans la vie courante, les deux verbes trier et classer ne sont pas synonymes. - Trier ou effectuer un tri c’est répartir les éléments en paquets correspondant à un certain critère : par exemple séparer les déchets selon leur nature, les personnes d’une assemblée selon leur sexe ou selon leur langue maternelle.

Classer ou effectuer un classement c’est mettre des éléments selon un certain ordre : par exemple ranger les personnes d’une assemblée de la plus petite à la plus grande, ou de la plus jeune à la plus âgée.

Définition à retenir

En informatique le tri est à prendre avec le sens de classement.

Vidéo : Les algorithmes de tri

Animation : Différentes méthodes de tri

Changer le type de tri et cliquer sur commencer pour visualiser les étapes de l'algorithme.

Seuls les tris par insertion et sélection sont au programme en NSI.

Astuce Python : tri natif avec sorted() et sort()

Nouvelle liste triée avec sorted()Tri "en place" avec la méthode .sort()

En Python, nous pouvons utiliser la fonction built-in sorted() pour créer une nouvelle liste triée.

help(sorted)sorted(ma_liste)sorted(ma_liste, reverse = True)

Il est également possible d'utiliser la méthode .sort() des objets de type list pour les trier en place.

Compléments

Pour approfondir : Interstices