Parcours et tris

Un parcours séquentiel examine les éléments d’un tableau dans un ordre déterminé. Pour rechercher une occurrence de x, on compare x à chaque valeur jusqu’à trouver une égalité ou atteindre la fin. La spécification peut demander un booléen, un indice ou toutes les positions : ces résultats ne sont pas équivalents. Si on renvoie un indice particulier pour l’absence, il faut l’annoncer. Le nombre de comparaisons dépend de la position trouvée ; dans le pire cas, n cases doivent être examinées.

Pour un minimum, on suppose le tableau non vide et on initialise le meilleur candidat avec la première valeur. Chaque case suivante est comparée au candidat ; une valeur plus petite le remplace. Initialiser à 0 serait faux pour un tableau composé seulement de nombres positifs. Pour une somme, on initialise au contraire un total à 0, valeur neutre de l’addition. Une moyenne exige ensuite de diviser par l’effectif, ce qui impose un tableau non vide.

Le tri par sélection construit un préfixe définitivement rangé. À l’étape i, il cherche l’indice du plus petit élément dans la partie allant de i à n − 1, puis échange cet élément avec t[i]. La recherche du minimum porte sur toute la partie encore non traitée, même si le candidat change plusieurs fois. Après l’échange, la case i contient la valeur attendue dans l’ordre croissant. L’échange conserve les valeurs du tableau ; il change seulement leurs positions.

L’invariant de la boucle externe décrit le préfixe avant l’étape i : il est trié, contient les i plus petites valeurs avec leurs répétitions et ne dépasse aucune valeur restante. Il est vrai au départ pour le préfixe vide. Le choix du minimum préserve cette propriété en ajoutant une valeur. Quand les étapes se terminent, il ne reste qu’une case et tout le tableau est rangé. Les boucles for parcourent des ensembles finis d’indices : la terminaison est assurée.

Le tri par insertion maintient lui aussi un préfixe trié, mais il l’agrandit différemment. À l’étape i, on mémorise la valeur v = t[i]. On décale vers la droite les valeurs du préfixe qui sont strictement supérieures à v, puis on place v dans l’emplacement libéré. Il ne faut pas perdre v pendant les décalages : le tableau peut contenir momentanément des valeurs répétées, mais la valeur à insérer reste conservée dans une variable.

Pour justifier la correction, on annonce que le préfixe avant i est trié et contient les mêmes valeurs que le préfixe initial correspondant. Les décalages déplacent sans perdre les valeurs supérieures à v ; l’insertion de v les remet dans l’ordre avec les autres. Le préfixe s’agrandit donc d’une case en préservant cette propriété. La boucle externe est bornée ; la boucle interne termine car j diminue et ne peut pas continuer après être devenu négatif.

Un coût algorithmique compte une opération choisie en fonction de la taille n, plutôt que le temps d’une seule mesure sur un ordinateur. Le parcours séquentiel a un coût linéaire : au plus un nombre proportionnel à n d’examens. Le tri par sélection effectue (n − 1) + (n − 2) + … + 1 comparaisons, soit n(n − 1)/2. Le terme dominant est proportionnel à n² : le coût est quadratique. Doubler n fait approcher le nombre de comparaisons d’un facteur quatre lorsque n devient grand.

Pour l’insertion, le pire cas est notamment un tableau strictement décroissant : chaque nouvelle valeur traverse tout le préfixe. Le nombre de comparaisons de valeurs atteint aussi n(n − 1)/2. Sur un tableau déjà trié, une comparaison de valeurs par étape suffit dans cette version, donc n − 1 au total. Il faut annoncer le cas étudié et l’opération comptée. Les tests d’indices et les affectations donnent d’autres comptes exacts, sans changer ici les ordres de grandeur du pire cas.

Ces outils peuvent aussi servir à une classification par les k plus proches voisins. On calcule une distance entre un objet à classer et les exemples connus, on trie selon cette distance, puis on choisit la classe majoritaire parmi les k premiers. Il faut annoncer la distance, k et la règle de départage. Avec k = 3 et les classes voisines A, B, A, la prédiction est A. Cette prédiction dépend des exemples et de la mesure de proximité ; elle ne constitue pas une preuve que la classe réelle est A.

Retrouve S’entraîner à l’adresse /exercices. Compare les deux tris sur un tableau déjà rangé, un tableau inversé et un tableau comportant des répétitions.