Trier

Problématique

Comment trier dans l'ordre croissant des nombres dans une liste (ou des noms dans une liste?)

Comment définir une fonction qui à partir de [7,6,2,5,4] retourne [2,4,5,6,7] ?

Comment définir une fonction qui à partir de ['Char','Céline','Camus','Chateaubriand','Colette'] retourne ['Camus','Céline','Char','Chateaubriand','Colette'] ?

Par la suite on travaille avec des listes de nombres ou (exclusif) des listes de noms

Tri par sélection (par ordre croissant)

L'idée est de parcourir le tableau du début à la fin afin de sélectionner le plus petit élément puis d'échanger les places du premier élément du tableau avec celle du plus petit élément

Ensuite on parcourt le tableau de la deuxième place jusqu'à la fin pour sélectionner le plus petit élément puis d'échanger les places du deuxième élément du tableau avec celle du plus petit élément

Voici sur un exemple le tri par sélection

L'algorithme en pseudo-code est 


Pour i de 0 jusqu'à n (le dernier indice de la liste)
     j <- sélectionner le plus petit élément de la liste entre les éléments d'indice i et n
     échanger les élements d'indice i et j de la liste

Exercices

  1. Définir une fonction minimum(liste) qui retourne le premier indice de la plus petite valeur de la liste

    Par exemple minimum([3,2,5,2,7]) retourne l'indice 1 de la plus petite valeur 2

  2. Définir une nouvelle fonction selection(liste,i) (en modifiant légèrement la fonction précédente) qui retourne le premier indice de la plus petite valeur de la liste à partir de l'indice i

    Par exemple selection([3,2,5,2,7],2) retourne l'indice 3 de la plus petite valeur 2

  3. Définir une fonction echange(i,j,liste) qui échange les positions des éléments d'indice i et j de la liste

    Par exemple echange(0,1,[3,2,5,2,7]) modifie la liste et celle-ci devient [2,3,5,2,7]

  4. Traduire l'algorithme du tri par sélection en définissant une fonction triSelection(liste)

    Par exemple triSelection([3,2,5,2,7]) transforme la liste [3,2,5,2,7] en [2,2,3,5,7]

    Utiliser la fonction sur des listes de nombres ou de noms

  5. Simplifier la fonction en n'utilisant pas la variable j