Aller au contenu

Exercices sur les tris simples⚓︎

Quel tri ? (1)

On considère le tableau \([6,\,1,\,4,\,5,\,2,\,3]\). Après la première itération d'un tri, on obtient le tableau : \([1,\,6,\,4,\,5,\,2,\,3]\)

  • On a utilisé un tri par insertion
  • On a utilisé un tri par sélection
  • On a utilisé un tri à bulles
  • On a utilisé un tri par insertion ou par sélection
  • ✅ Lors de la première itération on échange les valeurs d'indices \(0\) et \(1\)
  • ✅ Lors de la première itération on insère le minimum, a valeur \(1\), à sa place correcte à gauche
  • ❌ On aurait déplacé le \(6\) à la fin du tableau
  • ✅ C'est juste, voir les deux premières questions
Quel tri ? (2)

On considère le tableau \([6,\,1,\,4,\,5,\,2,\,3]\). Après la première itération d'un tri, on a obtenu le tableau : \([1,\,6,\,4,\,5,\,2,\,3]\). Après la deuxième itération du tri :

  • par sélection, on obtient le tableau : \([1,\,2,\,6,\,4,\,5,\,3]\)
  • par sélection, on obtient le tableau : \([1,\,2,\,4,\,5,\,6,\,3]\)
  • par insertion, on obtient le tableau : \([1,\,4,\,6,\,5,\,2,\,3]\)
  • par insertion, on obtient le tableau : \([1,\,2,\,4,\,5,\,3,\,6]\)
  • ❌ On sélectionne la valeur minimale, le \(2\) à l'indice \(4\) et on l'échange avec le \(6\) à l'indice \(1\)
  • ✅ Voir réponse ci-dessus
  • ✅ On insère la valeur d'indice \(2\) au bon endroit
  • ❌ Voir réponse ci-dessus
Quel tri ? (3)

On considère le tableau \([5,\,4,\,3,\,2,\,1]\).

Après deux itérations :

  • du tri par sélection on obtient le tableau : \([1,\,2,\,3,\,4,\,5]\)
  • du tri par sélection on obtient le tableau : \([1,\,2,\,5,\,4,\,3]\)
  • du tri par insertion on obtient le tableau : \([3,\,4,\,5,\,2,\,1]\)
  • du tri par insertion on obtient le tableau : \([1,\,2,\,3,\,5,\,4]\)
  • ✅ étape 1 : \([1,\,4,\,3,\,2,\,5]\), étape 2 : \([1,\,2,\,3,\,4,\,5]\)
  • ❌
  • ✅ étape 1 : \([4,\,5,\,3,\,2,\,1]\), étape 2 : \([3,\,4,\,5,\,2,\,1]\)
  • ❌
Quel tri ? (4)

On considère les fonctions suivantes dont certaines sont incorrectes.

🐍 Script Python
def tri_A(tableau):
    for i in range(len(tableau) - 1):
        i_maxi = i
        for j in range(i + 1, len(tableau)):
            if tableau[j] < tableau[i_maxi]:
                i_maxi = j
        tableau[i], tableau[i_maxi] = tableau[i_maxi], tableau[i]

def tri_B(tableau):
    for i in range(len(tableau) - 1):
        i_maxi = i
        for j in range(i + 1, len(tableau) - 1):
            if tableau[j] < tableau[i_maxi]:
                i_maxi = j
        tableau[i], tableau[i_maxi] = tableau[i_maxi], tableau[i]

def tri_C(tableau):
    for i in range(1, len(tableau)):
        valeur_a_inserer = tableau[i]
        j = i
        while j > 0 and tableau[j - 1] > valeur_a_inserer:
            tableau[j] = tableau[j - 1]
            j = j + 1 
        tableau[j] = valeur_a_inserer

def tri_D(tableau):
    for i in range(1, len(tableau)):
        valeur_a_inserer = tableau[i]
        j = i
        while j > 0 and tableau[j - 1] > valeur_a_inserer:
            tableau[j] = tableau[j - 1]
            j = j - 1
        tableau[j] = valeur_a_inserer
  • La fonction tri_A met en œuvre un tri par sélection
  • La fonction tri_A met en œuvre un tri par insertion
  • La fonction tri_B met en œuvre un tri par sélection
  • La fonction tri_B met en œuvre un tri par insertion
  • La fonction tri_C met en œuvre un tri par sélection
  • La fonction tri_C met en œuvre un tri par insertion
  • La fonction tri_D met en œuvre un tri par sélection
  • La fonction tri_D met en œuvre un tri par insertion
  • ✅
  • ❌
  • ❌ Il faudrait for j in range(i + 1, len(tableau)): pour lire la dernière valeur du tableau
  • ❌
  • ❌
  • ❌ Il faudrait j = j - 1 car on prend la valeur se trouvant à gauche pour la décaler vers la droite
  • ❌
  • ✅
Quel tri ? (5)

On considère les fonctions suivantes mettant toutes en œuvre le tri par insertion ou par sélection mais dans d'autres langages que le Python.

Java
public static void tri_A(int[] A){
    for(int i = 1; i < A.length; i++){
        int value = A[i];
        int j = i - 1;
        while(j >= 0 && A[j] > value){
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j + 1] = value;
    }
}
Kotlin
fun <T : Comparable<T>> Array<T>.tri_B() {
    for (i in 0..size - 2) {
        var k = i
        for (j in i + 1..size - 1)
            if (this[j] < this[k])
                k = j

        if (k != i) {
            val tmp = this[i]
            this[i] = this[k]
            this[k] = tmp
        }
    }
}
C
#include <stdio.h>

void tri_C(int *a, const size_t n) {
    for(size_t i = 1; i < n; ++i) {
        int key = a[i];
        size_t j = i;
        while( (j > 0) && (key < a[j - 1]) ) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}
Haskell
import Data.List (delete)

tri_D :: (Ord a) => [a] -> [a]
tri_D [] = []
tri_D xs = tri_D (delete x xs) ++ [x]
where x = maximum xs
  • La fonction tri_A met en œuvre un tri par sélection
  • La fonction tri_A met en œuvre un tri par insertion
  • La fonction tri_B met en œuvre un tri par sélection
  • La fonction tri_B met en œuvre un tri par insertion
  • La fonction tri_C met en œuvre un tri par sélection
  • La fonction tri_C met en œuvre un tri par insertion
  • La fonction tri_D met en œuvre un tri par sélection
  • La fonction tri_D met en œuvre un tri par insertion
  • ❌ La fonction tri_A met en œuvre un tri par sélection
  • ✅ La fonction tri_A met en œuvre un tri par insertion
  • ✅ La fonction tri_B met en œuvre un tri par sélection
  • ❌ La fonction tri_B met en œuvre un tri par insertion
  • ❌ La fonction tri_C met en œuvre un tri par sélection
  • ✅ La fonction tri_C met en œuvre un tri par insertion
  • ✅ La fonction tri_D met en œuvre un tri par sélection
  • ❌ La fonction tri_D met en œuvre un tri par insertion
Coût des algorithmes

On rappelle que l'algorithme de recherche dichotomique est défini dans cette page.

On étudie les coûts des algorithmes en fonction de la longueur des données et dans le pire des cas.

  • Le coût de la recherche dichotomique est linéaire
  • Le coût de la recherche dichotomique est logarithmique
  • Le coût de la recherche dichotomique est quadratique
  • Le coût du tri par sélection est linéaire
  • Le coût du tri par sélection est logarithmique
  • Le coût du tri par sélection est quadratique
  • Pour une entrée de grande taille, un algorithme de coût linéaire est plus avantageux qu'un algorithme de coût logarithmique
  • Pour une entrée de grande taille, un algorithme de coût logarithmique est plus avantageux qu'un algorithme de coût quadratique
  • ❌
  • ✅
  • ❌
  • ❌
  • ❌
  • ✅
  • ❌
  • ✅
Combien d'échanges ?

On considère la fonction suivante triant un tableau. Le pire des cas de l'algorithme mis en œuvre est celui d'un tableau initialement trié dans l'ordre décroissant.

Combien d'échanges sont effectués pour trier un tableau de taille \(10\) dans le pire des cas ?

🐍 Script Python
def tri(tab) :
    for i in range (1, len(tab)) :
        for j in range (len(tab) - i) :
            if tab[j] > tab[j + 1] :
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
  • \(10\)
  • \(45\)
  • \(55\)
  • \(100\)
  • ❌
  • ✅
  • ❌
  • ❌

Lors de la première itération de la boucle principale il y aura \(9\) échanges, \(8\) dans la suivante puis \(7\), \(6\), ... \(1\).

Au total il y aura donc \(9+8+7+6+\dots+1=45\) échanges.

Tri par sélection dans l'ordre décroissant

Compléter la fonction tri_selection_decr prenant en argument un tableau et le triant en place à l'aide du tri par sélection dans l'ordre décroissant.

###
def tripy-undselectionpy-unddecr(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nltableau = [3, 1, 2]bksl-nltripy-undselectionpy-unddecr(tableau)bksl-nlassert tableau == [3, 2, 1], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableau = [1, 2, 3, 4]bksl-nltripy-undselectionpy-unddecr(tableau)bksl-nlassert tableau == [4, 3, 2, 1], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableau = [-2, -5]bksl-nltripy-undselectionpy-unddecr(tableau)bksl-nlassert tableau == [-2, -5], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableau = []bksl-nltripy-undselectionpy-unddecr(tableau)bksl-nlassert tableau == [], "Erreur avec un tableau vide"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def tri_selection_decr(tableau):
    for i in range(len(tableau) - 1):
        i_maxi = i
        for j in range(i + 1, len(tableau)):
            if tableau[j] > tableau[i_maxi]:
                i_maxi = j
        tableau[i], tableau[i_maxi] = tableau[i_maxi], tableau[i]
Tri par insertion dans l'ordre décroissant

Compléter la fonction tri_insertion_decr prenant en argument un tableau et le triant en place à l'aide du tri par insertion dans l'ordre décroissant.

###
def tripy-undinsertionpy-unddecr(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undinsertionpy-unddecr(tableaupy-und0)bksl-nlassert tableaupy-und0 == [3, 2, 1], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undinsertionpy-unddecr(tableaupy-und1)bksl-nlassert tableaupy-und1 == [4, 3, 2, 1], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undinsertionpy-unddecr(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-2, -5], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und3 = []bksl-nltripy-undinsertionpy-unddecr(tableaupy-und3)bksl-nlassert tableaupy-und3 == [], "Erreur avec un tableau vide"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def tri_insertion_decr(tableau):
    for i in range(1, len(tableau)):
        valeur_a_inserer = tableau[i]
        j = i
        while j > 0 and tableau[j - 1] < valeur_a_inserer:
            tableau[j] = tableau[j - 1]
            j = j - 1
        tableau[j] = valeur_a_inserer
Tri de couples de valeurs

Le secrétariat d'un collège souhaite établir la liste de ses élèves triée par niveau puis par ordre alphabétique.

Il veut ainsi obtenir une liste dans laquelle :

  • on rencontre tout d'abord les élèves de 6ème puis ceux de 5ème, de 4ème et enfin ceux de 3ème,
  • au sein de chaque niveau, les élèves sont triés dans l'ordre alphabétique de leur nom.

Chaque élève est décrit par un tuple Python dans lequel la première valeur est le niveau dans lequel il est scolarisé (entier allant de 3 à 6) et la seconde son nom (une chaîne de caractères).

On se propose d'utiliser le tri par sélection.

Par exemple :

🐍 Console Python
>>> eleves = [
...     (4, "Targeur Samia"),
...     (5, "Blennie Aymeric"),
...     (5, "Alose Tom"),
...     (6, "Targeur Samir"),
... ]
>>> tri_eleves(eleves)
>>> eleves
[(6, 'Targeur Samir'), (5, 'Alose Tom'), (5, 'Blennie Aymeric'), (4, 'Targeur Samia')]

On rappelle que Python trie nativement les chaînes de caractères dans l'ordre lexicographique :

🐍 Console Python
>>> "Alose Tom" < "Blennie Aymeric"
True
>>> "Targeur Samia" > "Targeur Samir"
False

Compléter les fonctions indice_prochain_depuis et tri_eleves ci-dessous afin d'effectuer le tri souhaité à l'aide du tri par sélection.

###
def indicepy-undprochainpy-unddepuis(tableau, i):bksl-nl ...bksl-nlbksl-nlbksl-nldef tripy-undeleves(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nleleves = [bksl-nl (4, "Targeur Samia"),bksl-nl (5, "Blennie Aymeric"),bksl-nl (5, "Alose Tom"),bksl-nl (6, "Targeur Samir"),bksl-nl]bksl-nltripy-undeleves(eleves)bksl-nlbksl-nl# Testsbksl-nlassert eleves == [bksl-nl (6, "Targeur Samir"),bksl-nl (5, "Alose Tom"),bksl-nl (5, "Blennie Aymeric"),bksl-nl (4, "Targeur Samia"),bksl-nl]bksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def indice_prochain_depuis(tableau, i):
    i_maxi = i
    for j in range(i + 1, len(tableau)):
        if tableau[j][0] > tableau[i_maxi][0]:
            i_maxi = j
        elif tableau[j][0] == tableau[i_maxi][0]:
            if tableau[j][1] < tableau[i_maxi][1]:
                i_maxi = j
    return i_maxi


def tri_eleves(tableau):
    for i in range(len(tableau) - 1):
        i_prochain = indice_prochain_depuis(tableau, i)
        tableau[i], tableau[i_prochain] = tableau[i_prochain], tableau[i]