QCM - tris

QCM 14

Pour s’entraîner

  1. Que fait cette fonction?
def mystere(tab: list, i: int, j: int) -> None:
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

Dans le tableau tab elle échange les valeurs d’indices i et j.

  1. Citer les trois tris vus en cours et dans les exercices.

Tri par sélection, tri par insertion, tri à bulles.

  1. On dispose de la fonction tri ci-dessous:
def tri(tab: list) -> None:
    for i in range(len(tab)):
        i_mini = i
        mini = tab[i]
        for j in range(i, len(tab)):
            if tab[j] < mini:
                i_mini = j
                mini = tab[j]
        tab[i], tab[i_mini] = tab[i_mini], tab[i]

De quel type de tri s’agit-il?

C’est un tri par sélection:

  • la boucle interne (variable j) effectue une recherche de minimum,
  • la dernière ligne échange les deux valeurs dans le tableau.
  1. Construire par compréhension un tableau de 20 entiers aléatoires, compris entre 50 et 100.
tab = [randint(50, 100) for _ in range(20)]
  1. Compléter la fonction inserer qui fait avancer l’élément de rang j vers la fin du tableau, tant que sa valeur est plus grande que celle de rang j+1.
def inserer(tab: list, j: int) -> None:
    while j+1 < ... and tab[...] < tab[...]:
        temp = tab[j]
        tab[j] = tab[j+1]
        tab[j+1] = temp
        j = ...
def inserer(tab: list, j: int) -> None:
    while j+1 < len(tab) and tab[j+1] < tab[j]:
        temp = tab[j]
        tab[j] = tab[j+1]
        tab[j+1] = temp
        j = j+1

La fonction inserer du cours effectuait la même opération, mais dans l’autre sens (vers le début du tableau).

  1. Quelle est le coût temporel du tri par sélection?

Le coût du tri par sélection est quadratique ($n^2$). En effet, ce tri est construit avec deux boucles imbriquées de taille n (ou presque pour la boucle interne).