Actvité 1

Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Exercice 1 (6 points)¶

Tri par insertion¶

Le principe du tri par insertion est assez naturel. On prend les cartes une par une en commençant par la première.

Au départ la première est supposée à sa place. On regarde la deuxième et on compare à la premiere, on échange si besoin. Les deux premières cartes sont donc rangées dans l'ordre.
On regarde la troisième, on compare aux précédentes en partant de la plus proche à la première et on échange si l'ordre n'est pas bon. Si l'on n'échange pas cela signifie que l'on peut passer à la carte suivante. Maintenant les 3 premières cartes sont rangées.
On regarde la 4ème carte et on la fait ainsi descendre à la position qui lui correspond...les 4 premières cartes sont rangées.
On poursuit ainsi jusqu'à la dernière carte.

Vous pouvez regarder cette vidéo et essayez de comprendre le principe du tri par insertion : https://www.numerique-sciences-informatiques.fr/videos/triInsertion.mp4

On appelle procédure, une fonction qui ne retourne rien.

Implémentez ce pseudo-code correspondant au tri par insertion :

procédure TriInsertion(tableau T, entier n)
    Pour i allant de 1 à n-1
        e ← T[i]
        j ← i
        Tant que j > 0 et T[j-1] > e
            T[j] ← T[j-1]
            j ← j-1

        T[j] ← e

Exercice 2 (6 points)¶

Tri par sélection¶

On cherche le plus petit élément du tableau et on l'échange avec celui qui est au début. Le premier élément est maintenant le plus petit
Maintenant on cherche le plus petit élément du tableau mais en partant du 2nd élément et on l'échange avec celui qui est placé deuxième. Les deux premiers éléments sont les plus petits et sont rangés.
On poursuit ainsi.

Vous pouvez regarder cette vidéo et essayer de comprendre le principe du tri par selection : https://www.numerique-sciences-informatiques.fr/videos/triSelection.mp4

Soit le pseudo-code suivant :

procédure TriSelection(tableau T, entier n)
    Pour i allant de 0 à n - 2
        min ← i
        Pour j allant de i + 1 à n-1
            Si T[j] < T[min]
                min ← j
        Si min ≠ i
            temp←T[i]
            T[i] ← T[min]
            T[min] ← temp

Implémenter l’algorithme de tri par sélection (il peut être judicieux de découper le tri en deux fonctions, dont une fonction pour trouver l'indice du minimum de la liste)

Exercice (8 points)¶

Tri fusion¶

Implémentez ce pseudo-code vu en cours correspondant au tri fusion :

fonction fusionner(tableau_gauche T1, tableau_droite T2) :

    T ← tableau vide
    i_tableau_gauche ← 0
    i_tableau_droite ← 0

    Tant que i_tableau_gauche < taille du tableau T1 et i_tableau_droite < taille du tableau T2
        Si T1[i_tableau_gauche] < T2[i_tableau_droite]
            ajouter T1[i_tableau_gauche] à T
            i_tableau_gauche ←i_tableau_gauche + 1
        Sinon
            ajouter T2[i_tableau_droite] à T
            i_tableau_droite ← i_tableau_droite + 1
        FinSi
    FinTantQue

    Si i_tableau_gauche < taille du tableau T1
        Tant que i_tableau_gauche < taille du tableau T1
            ajouter T1[i_tableau_gauche] à T
            i_tableau_gauche ← i_tableau_gauche + 1
        FinTantque
    Sinon
        Tant que i_tableau_droite < taille du tableau T2
            ajouter T2[i_tableau_droite] à T
            i_tableau_droite ← i_tableau_droite + 1
        FinTantque
    FinSi

    Renvoyer T

fonction tri_fusion(tableau T) :

    Si taille du tableau T n’est pas égal à 1 :
        milieu ←  taille du tableau T / 2
        tableau_gauche ←  tri_fusion(T[0...milieu - 1])
        tableau_droite ←  tri_fusion(T[milieu...taille du tableau T - 1])
        Renvoyer fusionner(tableau_gauche T1, tableau_droite T2)
    Sinon :
        Renvoyer  tableau T
    FinSi