C6 Algorithmes de tri

Tri par sélection

Activité

Commencer par télécharger une application Python :
- Tri par sélection
- Copier ce fichier dans le répertoire de votre choix
- Faire un clic droit sur le fichier compressé et choisir Extraire ici
Dans cette activité, on doit ranger des cartes par ordre croissant mais sans les voir, on dispose par contre de deux boutons :
- Un bouton Trouver la plus petit carte depuis l'emplacement qui permet de savoir quelle carte est la plus petite à partir de l'emplacement qu'on sélectionne dans le menu déroulant à côté.
- Un bouton Echanger les cartes situés aux emplacements qui permet d'échanger les cartes situés aux emplacements sélectionnés dans les menus déroulants.
Voici une capture d'écran de l'application dans laquelle on vient de sélectionner la plus petite carte depuis l'emplacement 0, elle est alors indiquée par une flèche rouge au-dessus (emplacement 6) :
Proposer un algorithme permettant à un ordinateur de ranger une suite de nombres par ordre croissant.
Implémentation en python
1. Ecrire une fonction echange(liste,i,j) qui échange les éléments d'indice i et j de la liste liste par exemple si liste=[12,17,10,11,32] alors après echange(liste,0,2) le contenu de liste sera [10,17,12,11,32].
2. Ecrire une fonction min_depuis(liste,i) qui renvoie le minimum de la liste liste à partir de l'indice i par exemple min_depuis([10,17,12,11,32],2) renvoie 11.
3. En utilisant ces deux fonctions, proposer une implémentation en Python de l'algorithme du tri par sélection.

Cours

Vous pouvez télécharger une copie au format pdf du diaporama de synthèse de cours présenté en classe :

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

QCM

1. On applique l'algorithme du tri par sélection à la liste [9,11,7,16], après la première étape, le contenu de la liste sera :

2. On applique l'algorithme du tri par insertion à la liste [9,11,7,16], quel sera le contenu de la liste après le premier échange ?

3. L'algorithme du tri par insertion a une complexité :

4. Un programme de tri par insertion prend environ 1 seconde pour trier une liste de $10 000$ éléments, combien de temps prendra-t-il environ pour trier une liste de $100 000$ éléments ?

5. Quelles sont les deux lignes manquantes dans la fonction ci-dessus qui renvoie le minimum d'une liste non vide :

def min_liste(liste):
    elt_min = ....
    for elt in liste:
        if elt<elt_min:
            ......
    return elt_min

Exercices

Exercice 1 : Fonctionnement du tri par sélection

Ecrire les étapes du tri par sélection pour la liste [12,19,10,13,11,15,9,14]
Même question pour la liste `["P","R","O","G","R","A","M","M","E"]

Exercice 2 : Fonctionnement du tri par insertion

Ecrire les étapes du tri par insertion pour la liste [12,19,10,13,11,15,9,14]
Même question pour la liste `["P","R","O","G","R","A","M","M","E"]

Exercice 3 : Tri par ordre décroissant

On donne ci-dessous l'implémentation du tri par sélection vu en cours :

def tri_selection(liste):
    longueur = len(liste)
    for ind in range(longueur):
        ind_min = min_liste(liste,ind)
        echange(liste,ind,ind_min)

Modifier cette fonction afin d'effectuer un tri dans l'ordre décroissant.

Même question pour l'algorithme du tri par insertion ci-dessous :

def tri_insertion(liste):
    for ind in range(1,len(liste)-1):
        j = ind
        while liste[j+1]<liste[j] and j>=0:
            echange(liste,j,j+1)
            j=j-1

Exercice 4 : Tri dans une nouvelle liste

Les algorithmes vus en cours modifient la liste donnée en paramètre, on dit qu'on effectue un tri en place c'est à dire directement dans la liste.

Modifier la fonction de tri par sélection vu en classe afin d'effectuer le tri en créant une nouvelle liste (et donc sans modifier la liste de départ)
Même question pour le tri par insertion

Aide

Comme une nouvelle liste est crée, on utilisera l'instruction return pour la renvoyer vers le programme principal.

Exercice 5 : Liste triée

Ecrire une fonction est_triee qui prend en argument une liste et qui renvoie True si liste est triée par ordre croissant et False dans le cas contraire.

Attention

On ne doit pas trier la liste, simplement vérifier si elle l'est déjà ou pas.
Ajouter un paramètre reverse à cette fonction de façon à vérifier si la liste est trié par ordre croissant (reverse=False) ou décroissant (reverse=True).