Exercices: parcours séquentiel et tris

Écrire une fonction maximum(t) qui renvoie le plus grand élément d'un tableau non vide t d'entiers, en utilisant un parcours séquentiel. Donner le résultat pour [4, 9, 2, 9, 7].

Écrire une fonction moyenne(t) qui renvoie la moyenne des éléments d'un tableau non vide de nombres, puis une fonction occurrences(t, x) qui renvoie le nombre de fois où x apparaît dans t. Calculer moyenne([12, 15, 9, 14]).

On trie le tableau [5, 2, 4, 1] par ordre croissant avec le tri par sélection.

1. a) Donner le tableau après chaque étape (chaque passage de la boucle externe).

1. b) Combien de comparaisons d'éléments sont effectuées au total ?

Écrire en Python une fonction tri_insertion(t) qui trie un tableau en place par insertion. Dérouler ensuite l'algorithme sur [7, 3, 5, 1, 4] en donnant le tableau après chaque insertion.

Écrire une fonction indices_max(t) qui renvoie la liste de tous les indices où le maximum de t est atteint, en un seul parcours. Donner le résultat pour [3, 8, 1, 8, 5]. Préciser le nombre de comparaisons effectuées en fonction de la taille $n$ du tableau.

Le tri par sélection est appliqué à un tableau de $n$ éléments.

1. a) Exprimer en fonction de $n$ le nombre de comparaisons effectuées.

1. b) Calculer ce nombre pour $n = 100$, puis pour $n = 1\,000$. Par quel facteur est-il multiplié quand $n$ est multiplié par 10 ?

1. c) Que peut-on dire du nombre de comparaisons du tri par insertion sur un tableau déjà trié ? Et sur un tableau trié en ordre décroissant ?

On considère la fonction :

def tri_selection(t):

    n = len(t)

    for i in range(n - 1):

        m = i

        for j in range(i + 1, n):

            if t[j] < t[m]:

                m = j

        t[i], t[m] = t[m], t[i]

1. a) Énoncer un invariant de la boucle externe portant sur t[0..i-1] et sur le reste du tableau.

1. b) Démontrer cet invariant par récurrence.

1. c) En déduire la correction de l'algorithme et justifier sa terminaison.

On considère la fonction :

def tri_insertion(t):

    for i in range(1, len(t)):

        v = t[i]

        j = i

        while j > 0 and t[j - 1] > v:

            t[j] = t[j - 1]

            j = j - 1

        t[j] = v

1. a) Donner un invariant de la boucle for et un variant de la boucle while.

1. b) Justifier la terminaison de la boucle while.

1. c) Déterminer le nombre maximal de déplacements d'éléments en fonction de $n$ et indiquer pour quel type de tableau il est atteint.

Écrire une fonction tri_stable_notes(eleves) qui trie par insertion une liste de couples (nom, note) par note croissante, de façon stable.

1. a) Écrire la fonction.

1. b) Expliquer quelle modification de la condition de la boucle while ferait perdre la stabilité.

1. c) Appliquer la fonction à [("Ali", 12), ("Zoé", 9), ("Eva", 12), ("Tom", 9)].