Premiers tris

Exercice 4 du TP2

Dans toute activité scientifique, le classement est essentiel. Il s'agit de ranger les éléments dans un certain ordre, afin de pouvoir s'y retrouver plus facilement, plus rapidement. Cet ordre peut-être arbitraire, mais le plus souvent c'est

l'ordre naturel dans $\mathbb{N}$, $\mathbb{Z}$ ou $\mathbb{R}$,
l'ordre alphabétique pour le texte.

Dans le monde informatique,

les int et les float sont naturellement ordonnés,
les str également, selon l'ordre alphabétique mais attention : un A n'est pas un a – majuscule/minuscule fait une différence – et un texte peut contenir autre chose que des lettres !

Chaque caractère est associé à un nombre, c'est un encodage – car il n'y a que des nombres binaires dans les mémoires ! Pour connaître le nombre associé à un caractère c, on utilise ord(c). Pour info, Python utilise l'encodage Unicode qui permet d'obtenir à peu près n'importe quel caractère.

Nous allons tout au long de l’année étudier plusieurs fonctions, procédures, de tri et les comparer de divers points de vue. Pour simplifier cette première approche, on va se contenter de trier des tableaux – type list Python – d'entiers.

Pour commencer on étudie ici deux tris par comparaison qui utilisent des boucles imbriquées. Il y en a d'autres que l'on verra plus tard. Évidemment il y a au moins une fonction disponible dès l'ouverture de Python, qui fait le tri d’une liste – nous verrons aussi cela plus tard.

Tri par sélection

Ci-contre, l'animation – empruntée sur Wikipedia – montre le principe du tri par sélection :

Le tableau est séparé en une zone triée – en jaune – et une zone non triée.
On cherche dans la zone non trié l'élément le plus petit que l'on vient placé en à la suite de la zone triée.

FONCTION tri par sélection
ENTRÉE liste d'éléments comparables
DÉBUT
    soit n le nombre d'éléments de L
    POUR i allant de 0 à n-2 FAIRE
        # recherche de l'élément minimal dans L[i:]
        soit imin que l'on initialise à i
        et qui représente l'indice du min trouvé
        POUR j allant de i+1 à n-1 FAIRE
            SI L[j] < L[imin] ALORS
                imin prend la valeur j
            FIN
        FIN
        permutation des contenus de L[i] et L[imin]
    FIN
FIN

La fonction ne renvoie rien. Le tri est fait dans la liste fournie en entrée. On parle de tri en place. Cela peut être considéré comme un défaut car en général, une fonction ne modifie pas les arguments qu'on lui fournit. Il serait tout à fait possible de modifier la fonction pour qu'elle créer une copie de la liste de façon à trier la copie et à laisser l'originale inchangée.

La validité de l'algorithme – terminaison, correction – et le coût-complexité, seront étudiés plus tard.

Faites l'implémentation du tri par sélection dans une fonction tri_selection(L).

Tri à bulles

L'algorithme du tri à bulles d'une liste L de n élément, avec n > 1, consiste

à prendre successivement tous les couples d'indices (i - 1, i) pour 1 ≤ i ≤ n-1,
à comparer L[i] et L[i-1] et à les permuter s'ils ne sont pas dans le bon ordre.

Prenons l'exemple de L = [2, 3, 1, 7, 5, 1] on obtient les états successifs :

i = 1 : L[0] < L[1] sont dans le bon ordre,
i = 2 : L[1] > L[2] → permutation → L = [2, 1, 3, 7, 5, 1],
i = 3 : L[2] < L[3] → rien à faire,
i = 4 : L[3] > L[4] → permutation → L = [2, 1, 3, 5, 7, 1],
i = 5 : L[4] > L[5] → permutation → L = [2, 1, 3, 5, 1, 7]

À l'issue de cette boucle, on est certain que le plus grand élément est bien à droite. En revanche, le reste du tableau n'est pas trié. Il faut recommencer, mais il n'est plus nécessaire d'aller jusqu'au dernier élément. On peut parcourir 1 ≤ i ≤ n-2.

Suivra une 3e boucle avec 1 ≤ i ≤ n-3, et ainsi de suite jusqu'à 1 ≤ i ≤ 1.

Grâce à deux boucles imbriquées, implémenter cet algorithme en Python en une procédure tri_bulles d'argument L, une liste. tri_bulles trie L en place.
Pourquoi « tri à bulles » ?
Préciser le nombre de comparaisons effectuées.
On parle de coût (complexité) quadratique, comment justifier cela ?
Comment justifier que cet algorithme est conforme à sa spécification, c’est-à-dire ici qu'il trie la liste ?