Algorithmes de tri, recherche et efficacité

Une recherche détermine si une valeur recherchée apparaît et où elle apparaît. Une liste possède des positions numérotées appelées indices. Python compte à partir de zéro : dans [7, 3, 9, 3, 5], l’indice 0 contient 7 et l’indice 4 contient 5. La valeur et son indice répondent à des questions différentes.

Vérifier un élément à la fois

La recherche séquentielle commence au premier élément et compare chaque élément à la valeur recherchée. Elle renvoie immédiatement l’indice lorsqu’elle trouve une correspondance. Si la liste se termine sans correspondance, elle renvoie -1, notre signal pour « non trouvé ».

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

len(items) donne le nombre d’éléments. range(len(items)) fournit tous les indices valides, à partir de 0 et jusqu’à la valeur juste avant la longueur. items[i] lit la valeur à l’indice courant. Un return met fin à la fonction : une correspondance ultérieure ne remplace donc jamais la première.

La recherche de 3 dans la liste ci-dessus se déroule ainsi :

1. À l’indice 0, compare 7 à 3. Ils diffèrent, donc continue.
2. À l’indice 1, compare 3 à 3. Ils correspondent, donc renvoie l’indice 1.

Le résultat est l’indice 1 après deux comparaisons. Le second 3, à l’indice 3, n’est jamais vérifié. Chercher 4 vérifie au contraire 7, 3, 9, 3 et 5, puis renvoie -1 après cinq comparaisons. Un indice renvoyé égal à 1 désigne le deuxième élément, pas un élément de valeur 1.

Compter le travail

Soit $n$ le nombre d’éléments. Pour une liste non vide, le meilleur cas demande une comparaison : le premier élément correspond. Le pire cas demande $n$ comparaisons : la valeur recherchée est en dernier ou absente. Une liste vide ne nécessite aucune comparaison et renvoie -1.

Si une valeur recherchée apparaît une fois et a autant de chances d’occuper chaque position, son nombre moyen de comparaisons est

Pour 1 000 éléments, cela représente 500,5 comparaisons. Une moyenne peut être fractionnaire même si chaque recherche individuelle effectue un nombre entier de comparaisons. Cette moyenne décrit cette distribution particulière de recherches fructueuses ; des recherches infructueuses fréquentes augmenteraient la moyenne globale.

Placer l’échec après la boucle

Un else: return -1 dans la boucle abandonnerait dès la première absence de correspondance. Sur [7, 3, 9], il rejetterait une recherche de 3 après avoir vu seulement 7. Le retour indiquant l’échec doit se trouver après la boucle, quand toutes les positions ont été écartées.

La recherche séquentielle ne nécessite ni ordre trié ni préparation. Elle fonctionne avec des nombres, des mots ou des enregistrements comparés selon un identifiant. Une version conçue pour des données triées peut s’arrêter lorsqu’elle dépasse la position possible de la valeur recherchée : dans [2, 5, 8, 12], voir 8 suffit à exclure 6. Le code ci-dessus poursuit volontairement le parcours jusqu’à trouver une correspondance ou atteindre la fin.

Des tâches apparentées utilisent le même parcours mais une règle d’arrêt différente. Compter toutes les occurrences, recueillir tous les indices correspondants et trouver un plus grand élément exigent d’examiner toute la liste ; trouver la première correspondance permet un retour anticipé.

La recherche dichotomique utilise l’ordre des données triées pour écarter des positions sans les vérifier individuellement. Son entrée doit être triée par ordre croissant. Elle nécessite aussi un accès rapide à un élément d’indice choisi, comme le permet un tableau ou une liste Python.

Conserver un intervalle bornes comprises

low et high indiquent la première et la dernière position encore possibles, bornes comprises. Commence avec low = 0 et high = len(items) - 1. Choisis l’indice médian en arrondissant à l’entier inférieur. Si la valeur médiane est trop petite, toutes les valeurs à sa gauche sont aussi trop petites ; déplace low après le milieu. Si elle est trop grande, déplace high juste avant le milieu.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

// divise et arrondit à l’entier inférieur. La boucle inclut le cas low == high car il reste une position non vérifiée. Lorsque low > high, l’intervalle est vide.

Suivre une recherche fructueuse et une recherche infructueuse

Utilise [3, 8, 12, 17, 23, 31, 42, 56, 64, 77, 85], dont les indices vont de 0 à 10. Pour trouver 64, le premier indice médian est 5, qui contient 31. Comme 31 est trop petit, fixe low = 6. L’indice médian suivant est 8, qui contient 64. Renvoie 8 après deux vérifications d’éléments médians.

Pour chercher 20 dans la même liste :

L’intervalle est maintenant vide : renvoie donc -1. Cet échec est justifié : l’ordre de la liste a permis d’écarter chaque partie.

Pourquoi la méthode est rapide

Chaque vérification infructueuse laisse au plus la moitié de l’intervalle. Pour une liste non vide, le nombre maximal de vérifications d’éléments médians est $\lfloor {\log }_{2}n\rfloor +1$. Le logarithme en base 2 décrit les divisions successives par deux : $2^{10}=1024$, donc un millier d’éléments nécessite au plus 10 vérifications ; un million en nécessite au plus 20. Une vérification dans ce code Python peut effectuer deux comparaisons, == et <. Les vérifications et les comparaisons sont deux unités de comptage différentes.

Conditions et bogues aux limites

L’ordre trié est indispensable. Chercher 2 dans [9, 2, 7, 4, 1] rencontre d’abord 7 et écarte la partie droite, puis rencontre 9 et écarte la correspondance restante à l’indice 1. Un accès rapide au milieu compte aussi : suivre les liens pour atteindre le milieu d’une liste chaînée fait perdre l’avantage de vitesse de la version sur tableau.

Exclus toujours le milieu testé après une absence de correspondance. Utiliser low = mid peut laisser [10, 20] inchangée indéfiniment lors de la recherche de 20. Utiliser while low < high saute le dernier élément candidat et échoue en cherchant 5 dans [5]. Sur une liste vide, high = -1 : la boucle correcte ne démarre donc jamais.

En présence de doublons, cette version renvoie un indice correspondant quelconque. Chercher 4 dans [2, 4, 4, 4, 9] renvoie immédiatement l’indice 2 ; trouver la première occurrence nécessite une recherche modifiée qui continue à gauche après une correspondance.

Trier consiste à réorganiser des éléments selon une clé choisie. Pour des nombres en ordre croissant, chaque élément est inférieur ou égal au suivant. L’expression « non décroissant » autorise des voisins égaux : [2, 5, 5, 9] est triée. L’ordre décroissant inverse le sens.

Vérifier deux conditions

Un tri correct doit produire une sortie ordonnée contenant exactement les éléments d’origine, en conservant chaque répétition. Trier [3, 1, 2] en [1, 2, 3] réussit. Les deux résultats [1, 2] et [1, 1, 3] échouent, même si leurs éléments voisins sont dans l’ordre. Le premier perd un élément ; le second modifie les éléments présents. Un réarrangement qui conserve toutes les occurrences est appelé une permutation.

Pour un enregistrement, la clé est uniquement le champ utilisé pour la comparaison. Des villes pourraient être triées par nom ou par population. L’enregistrement entier d’une ville se déplace lorsque sa clé de population se déplace ; détacher le nom corromprait les données.

L’ordre du texte dépend de la clé

Une comparaison simple de texte suit les codes de caractères, un caractère à la fois. En ASCII et en Unicode, les lettres de A à Z utilisent les codes de 65 à 90 et celles de a à z les codes de 97 à 122. Une comparaison simple place donc « Zèbre » avant « abeille ». Comparer des copies en minuscules peut fournir un ordre insensible à la casse pour ces exemples.

Les chiffres sous forme de texte se comportent aussi comme des caractères. « 10 » est trié avant « 9 » car son premier caractère est « 1 ». Une clé numérique convertit ces chaînes en nombres qu’elles représentent, ce qui place 9 avant 10. Détermine ce que signifient les données avant de choisir la comparaison.

Déplacer des valeurs sans les perdre

Un échange permute deux positions. Une variable temporaire protège la valeur qui serait sinon écrasée :

temp = items[i]
items[i] = items[j]
items[j] = temp

Python permet aussi items[i], items[j] = items[j], items[i]. Écrire les deux affectations sans sauvegarder la première valeur transforme [4, 7] en [7, 7]. Les tris à bulles et par sélection déplacent les éléments par échange ; le tri fusion les copie dans une sortie fusionnée.

Stabilité et mémoire

Un tri stable conserve l’ordre initial des enregistrements dont les clés sont égales. Partons de Ana 85, Ben 92, Cara 85, par ordre alphabétique. Un tri stable par note décroissante produit Ben 92, Ana 85, Cara 85. Ana reste avant Cara. Un tri ultérieur par note peut ainsi conserver un ordre alphabétique antérieur au sein de chaque groupe de même note. Le tri intégré de Python est stable.

Un tri en place réorganise la liste existante avec seulement quelques variables supplémentaires, quelle que soit sa longueur. Les méthodes à bulles et par sélection enseignées ici sont en place. Le tri fusion habituel nécessite un espace de stockage supplémentaire proportionnel au nombre d’éléments. La stabilité et la mémoire décrivent des propriétés différentes : un tri peut être en place tout en étant instable.

Mesurer le désordre avec les inversions

Une inversion est une paire de positions où la clé d’un élément situé avant est supérieure à celle d’un élément situé après. Dans [5, 1, 4, 2, 8], les inversions sont (5, 1), (5, 4), (5, 2) et (4, 2) : quatre au total. Les éléments d’une paire ne sont pas nécessairement voisins.

Une liste triée a zéro inversion. Une liste de $n$ éléments distincts en ordre inverse en a $n(n-1)\mathrm{/}2$, le maximum. Des clés égales ne forment jamais une inversion : [3, 3, 1] en a deux, une pour chaque 3 placé avant 1. Compter les inversions est utile pour expliquer le nombre d’échanges du tri à bulles.

Le tri à bulles compare les éléments voisins de gauche à droite. Lorsque celui de gauche est plus grand, il échange la paire. Chaque parcours est un passage. Un grand élément peut se déplacer plusieurs fois vers la droite pendant un passage, jusqu’à ce que le plus grand élément restant atteigne sa position finale.

Suivre le premier passage

Partons de [5, 1, 4, 2, 8] :

1. Compare 5 et 1 ; échange-les pour obtenir [1, 5, 4, 2, 8].
2. Compare 5 et 4 ; échange-les pour obtenir [1, 4, 5, 2, 8].
3. Compare 5 et 2 ; échange-les pour obtenir [1, 4, 2, 5, 8].
4. Compare 5 et 8 ; laisse-les en place.

Le passage effectue quatre comparaisons et trois échanges. Le plus grand élément, 8, est placé. Le reste n’est pas encore trié : 4 précède 2. Un passage garantit la position finale du maximum, mais pas l’ordre de tous les éléments.

Le passage 2 ne nécessite que les quatre premières positions. Compare 1 à 4, puis échange 4 et 2, puis compare 4 à 5. Cela donne [1, 2, 4, 5, 8] après trois comparaisons supplémentaires et un échange. Le passage 3 compare 1 à 2 et 2 à 4. Il ne fait aucun échange, ce qui confirme que la liste est triée. Totaux : neuf comparaisons et quatre échanges.

Raccourcir chaque passage et s’arrêter tôt

def bubble_sort(items):
    n = len(items)
    for p in range(n - 1):
        swapped = False
        for j in range(n - 1 - p):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break

Le compteur de passages p commence à zéro. La plus grande valeur de j est n - 2 - p, donc j + 1 reste dans la partie non triée. Réinitialise swapped au début de chaque passage ; un échange lors d’un passage précédent ne dit rien sur le déplacement éventuel d’un élément au passage actuel.

Après chaque passage, une position supplémentaire à droite est définitive. Un passage sans échange prouve que tous les voisins comparés sont dans l’ordre. Le suffixe déjà placé est également dans l’ordre : l’algorithme peut donc s’arrêter. Le passage de confirmation compte tout de même comme travail.

Comparer le meilleur et le pire cas

Pour une liste non vide triée, la version avec arrêt anticipé effectue $n-1$ comparaisons et zéro échange. Sur une liste d’éléments distincts en ordre inverse, elle effectue

comparaisons et le même nombre d’échanges. Cinq éléments en nécessitent 10 ; 1 000 éléments en nécessitent 499 500. Sans arrêt anticipé, l’exemple de cinq éléments effectuerait aussi son dernier passage d’une comparaison, pour atteindre 10 comparaisons.

Chaque échange supprime exactement une inversion. Les quatre inversions de la liste initiale de l’exemple expliquent ses quatre échanges. Les voisins égaux restent en place car le test utilise >, ce qui rend cette version stable et en place. Remplacer > par >= peut inverser des enregistrements de même clé.

La position compte même lorsqu’il y a peu d’inversions. [5, 1, 2, 3, 4] utilise quatre échanges et un deuxième passage pour confirmer l’ordre, soit sept comparaisons. [2, 3, 4, 5, 1] nécessite aussi quatre échanges, mais son 1 ne peut avancer vers la gauche qu’une fois par passage. Elle nécessite les quatre passages et 10 comparaisons.

Le tri par sélection construit un préfixe trié à gauche. Chaque passage trouve le plus petit élément dans le suffixe restant, puis l’échange pour le placer à la position suivante du préfixe. Le parcours trouve la position ; l’échange a lieu après le parcours.

Retenir un indice

À la position i, commence avec smallest = i. Compare chaque élément suivant à items[smallest]. Mets à jour smallest seulement lorsqu’un élément plus petit apparaît. À la fin du parcours, échange items[i] et items[smallest].

def selection_sort(items):
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]

Ne retenir que la plus petite valeur ne donnerait pas sa position pour l’échange. Commencer le parcours à l’indice 0 ferait examiner à nouveau les éléments déjà placés ; la recherche dans la partie restante commence juste après i.

Suivre les passages

Partons de [29, 10, 14, 37, 13].

Le troisième minimum est déjà à sa place : aucune valeur ne bouge. Après quatre passages, le dernier élément est nécessairement le plus grand ; il ne nécessite pas de passage distinct. On compte 10 comparaisons et trois échanges qui déplacent des éléments. La condition dans le code évite les échanges d’une position avec elle-même ; l’omettre ne change pas le résultat.

Comparaisons et échanges ont des coûts différents

Le tri par sélection effectue toujours $n(n-1)\mathrm{/}2$ comparaisons d’éléments : chaque passage doit examiner tout le suffixe restant pour en déterminer le minimum. Le total est de 10 pour cinq éléments ou de 499 500 pour 1 000, même si l’entrée est déjà triée. Un parcours qui ne modifie pas l’indice retenu détermine le minimum de ce passage, mais ne garantit pas en général que le suffixe restant soit ordonné.

Pour une liste non vide, il y a au plus un échange qui déplace des éléments par passage, donc au plus $n-1$ au total. Une entrée vide ne nécessite ni passage ni échange. Le tri à bulles peut nécessiter $n(n-1)\mathrm{/}2$ échanges sur une liste d’éléments distincts en ordre inverse. Si déplacer de grands enregistrements coûte beaucoup plus cher que comparer leurs clés, le faible nombre d’échanges du tri par sélection peut compter malgré ses nombreuses comparaisons. Échanger chaque fois qu’un nouveau minimum apparaît pendant le parcours fait perdre cet avantage.

Des clés égales peuvent changer d’ordre

Cette méthode fondée sur les échanges est en place mais instable. Notons 4a et 4b des enregistrements de même clé afin de les distinguer. En partant de [4a, 4b, 1], le premier passage échange 4a et 1, ce qui produit [1, 4b, 4a]. Les éléments de même clé ont inversé leur ordre initial, même si l’algorithme ne les a jamais comparés directement comme étant différents. Conserver le premier minimum trouvé pendant un parcours n’empêche pas un échange à distance de faire passer un élément devant un enregistrement de même clé.

La fusion combine deux listes déjà triées en une seule sortie triée. Place un curseur sur le premier élément inutilisé de chaque entrée. Compare ces deux éléments de tête, copie le plus petit et avance uniquement son curseur.

Choisir le plus petit élément suivant

Fusionne [3, 27, 38, 43] avec [9, 10, 82] :

La liste de gauche est maintenant épuisée. Copie le 82 restant sans autre comparaison d’éléments. Le résultat est [3, 9, 10, 27, 38, 43, 82], avec six comparaisons. Copier la queue fait partie de l’algorithme : s’arrêter lorsque les comparaisons s’arrêtent ferait perdre des données.

Pourquoi la méthode peut-elle ignorer les éléments derrière ceux de tête ? Chaque élément de tête est le plus petit élément restant de sa propre liste. Le plus petit des éléments de tête est donc le plus petit élément restant au total. Ce raisonnement reste valable après chaque déplacement d’un curseur car les parties inutilisées restent triées.

Lire le code de fusion

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

append ajoute un élément. Une tranche comme left[i:] contient la queue inutilisée, et extend en copie les éléments. Une seule queue inutilisée peut être non vide à la fin de la boucle. Si une entrée est vide au départ, la boucle effectue zéro comparaison et l’autre liste est copiée intacte.

Compter les comparaisons et l’espace de stockage

Pour deux listes non vides de longueurs $m$ et $k$, il faut au plus $m+k-1$ comparaisons d’éléments de tête. Chaque comparaison place un élément et au moins le dernier élément peut être copié sans comparaison. Le plus petit nombre possible de comparaisons pour une fusion est la longueur de la liste la plus courte : fusionner [1, 2, 3] avec [4, 5, 6] utilise trois comparaisons avant que la partie gauche soit épuisée.

Le travail total de copie augmente avec $m+k$ même lorsque les comparaisons se terminent tôt, car chaque élément doit apparaître dans la sortie. La nouvelle liste nécessite aussi de la place pour $m+k$ éléments. Le nombre de comparaisons, le travail de copie et l’espace supplémentaire mesurent différentes parties d’une même opération.

Traiter les égalités et l’ordre des entrées

Le test <= prend l’élément de gauche lorsque les clés sont égales. Si les deux entrées proviennent de parties consécutives d’une liste d’origine, cela maintient l’enregistrement antérieur avant l’enregistrement ultérieur de même clé. C’est la règle en cas d’égalité nécessaire à un tri fusion stable.

L’exigence d’entrées triées est impérative. Fusionner [5, 1] avec [3] copie 3, puis la queue [5, 1], ce qui produit [3, 5, 1]. La règle des éléments de tête a échoué car 5 n’était pas la plus petite valeur restante dans sa propre entrée.

Le tri fusion résout une grande tâche de tri en la divisant en tâches de tri plus petites. C’est le principe diviser pour régner : diviser la liste, trier chaque moitié et fusionner les moitiés triées.

Arrêter la division au cas de base

Une fonction est récursive lorsqu’elle s’appelle elle-même. Le tri fusion s’appelle sur des listes plus courtes. Son cas de base renvoie une liste de zéro ou un élément sans modification, puisqu’une telle liste est déjà triée.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

Les tranches divisent l’entrée sans perdre d’éléments. Pour une longueur impaire, la partie droite contient un élément de plus : [6, 2, 9, 4, 1, 7, 3] se divise en [6, 2, 9] et [4, 1, 7, 3]. Les deux moitiés sont plus courtes : les appels récursifs atteignent donc finalement le cas de base. Un cas de base seul ne garantirait pas la terminaison si un appel continuait à se transmettre la liste d’origine.

Reconstruire la liste triée

Suis [38, 27, 43, 3, 9, 82, 10, 15]. La liste se divise en deux moitiés de quatre éléments, puis en quatre morceaux de deux éléments, puis en éléments isolés. La division ne réorganise pas les valeurs. L’ordre se construit pendant les fusions :

1. Fusionne les éléments isolés en [27, 38], [3, 43], [9, 82] et [10, 15]. Chaque fusion utilise une comparaison : quatre au total.
2. Fusionne les paires en [3, 27, 38, 43] et [9, 10, 15, 82]. Chaque fusion utilise trois comparaisons : six au total.
3. Fusionne ces moitiés en [3, 9, 10, 15, 27, 38, 43, 82]. Cette fusion utilise sept comparaisons.

Le tri complet utilise $4+6+7=17$ comparaisons d’éléments. Ne compte pas seulement la fusion finale : il a d’abord fallu produire les moitiés triées. Avec cette règle de division, l’exemple de sept éléments ci-dessus est trié en [1, 2, 3, 4, 6, 7, 9] en utilisant 14 comparaisons.

Compter les niveaux et le travail par niveau

Pour huit éléments, les divisions par deux aboutissent à des éléments isolés après trois niveaux car $2^3=8$. En général, il y a environ ${\log }_{2}n$ niveaux de fusion. Sur un niveau complet, les fusions traitent collectivement les $n$ éléments. Chaque niveau effectue donc un travail proportionnel à $n$, ce qui conduit à une croissance en $n{\log }_{2}n$.

Pour huit éléments, $n{\log }_{2}n=24$ est une borne supérieure approximative utile pour les comparaisons, pas le nombre exact. La liste de l’exemple en a utilisé 17 ; une liste de huit éléments déjà triée ou en ordre inverse en utilise 12. L’ordre de l’entrée change le moment où une fusion épuise un côté, mais chaque liste passe tout de même par les niveaux de division et de fusion. Pour cette version, la croissance des comparaisons reste en $n\log n$ dans le meilleur comme dans le pire cas.

Pour un million d’éléments, environ 20 niveaux donnent environ 20 millions de comparaisons comme estimation supérieure de l’ordre de grandeur. Le tri par sélection en utilise environ 500 milliards. La différence augmente rapidement avec la taille de l’entrée.

Prévoir l’espace supplémentaire pour la sortie

Le tri fusion ordinaire sur des listes nécessite un espace de stockage supplémentaire proportionnel à $n$. Choisir l’élément de tête gauche en cas d’égalité le rend stable.

Un temps d’exécution mesuré dépend de la machine et du programme. Un nombre d’étapes décrit le travail de l’algorithme à l’aide d’une opération répétée choisie. La taille de l’entrée, notée $n$, est le nombre d’éléments traités.

Choisir l’opération avant de compter

Pour la recherche et le tri, les comparaisons entre valeurs d’éléments constituent généralement une opération élémentaire utile. Compte les échanges séparément lorsque le déplacement des données compte. Pour la recherche dichotomique, il est pratique de compter les vérifications d’un élément médian. Dans la version Python, une vérification médiane infructueuse teste à la fois l’égalité et l’inégalité stricte : elle peut donc comporter deux comparaisons d’éléments.

Ces nombres décrivent des opérations répétées, pas des lignes de code. Une ligne dans une boucle peut s’exécuter un million de fois ; plusieurs lignes de préparation peuvent chacune ne s’exécuter qu’une fois.

Distinguer les cas pour une même taille

Le meilleur cas prend le moins d’étapes parmi les entrées valides de taille $n$. Le pire cas en prend le plus et fournit une garantie. Le cas moyen correspond à une moyenne calculée selon une distribution d’entrées précisée.

Pour une liste non vide, la recherche séquentielle nécessite une comparaison si la valeur recherchée est en tête et $n$ si elle est en dernière position ou absente. Sa moyenne pour une recherche fructueuse est $(n+1)\mathrm{/}2$ lorsque la première position correspondante a autant de chances d’être n’importe quelle position. Le mot « moyenne » suppose cette distribution ; il ne désigne pas le milieu entre les nombres du meilleur et du pire cas pour tout algorithme.

Traduire les boucles en nombres d’étapes

Une comparaison par élément lors d’un parcours complet donne $n$ comparaisons. Deux boucles complètes imbriquées, chacune exécutée $n$ fois, exécutent leur corps commun $n^2$ fois. Une autre structure de boucles imbriquées ne compare chaque paire qu’une fois :

for i in range(n):
    for j in range(i + 1, n):
        compare(items[i], items[j])

La première itération externe compare son élément aux $n-1$ éléments suivants. La suivante le compare à $n-2$ éléments, et la dernière à aucun. Le total est

Écris la somme dans les deux sens. Chaque paire de termes alignés donne $n$, et il y a $n-1$ paires de ce type. Leur total est $n(n-1)$, soit deux fois la somme initiale. Pour cinq éléments, $4+3+2+1=10$ ; pour 1 000, le nombre de paires est de 499 500.

Reconnaître les divisions successives par deux

Une boucle qui divise le travail restant par deux nécessite environ ${\log }_{2}n$ répétitions. Un million atteint pour la première fois 1 ou moins après 20 divisions par deux : $2^{19}=524288$ est inférieur à un million et $2^{20}=1048576$ lui est supérieur. C’est très différent de retirer un seul élément à chaque fois.

Pour comparer les croissances, garde le terme qui augmente le plus vite. Le nombre de paires est $n^2\mathrm{/}2-n\mathrm{/}2$. Pour $n=1000$, ses termes valent 500 000 et 500 : le terme quadratique détermine donc la croissance. Omettre le terme plus petit et le facteur constant décrit la famille de croissance ; cela ne transforme pas le nombre exact de 499 500 en un nombre exact d’un million.

Un ordre de croissance décrit comment la quantité de travail change lorsque l’entrée grandit. Il aide à comparer les algorithmes au-delà de la taille particulière utilisée dans un suivi d’exécution.

Lire les familles courantes

Pour une croissance exponentielle, ajouter un seul élément double déjà le nombre : $2^{n+1}=2\times 2^n$. Doubler l’entrée est un changement bien plus grand qu’en ajouter un.

Comparer les tailles par des nombres

Pour des entrées de 10, 100, 1 000 et un million d’éléments, ${\log }_{2}n$ vaut environ 3,3 ; 6,6 ; 10 et 20. Les valeurs correspondantes de $n{\log }_{2}n$ sont environ 33, 664, 9 966 et 20 millions. Les valeurs quadratiques sont 100, 10 000, un million et mille milliards.

Une croissance logarithmique ne correspond pas à « la moitié de la liste ». Pour un million d’éléments, les divisions successives par deux ne demandent qu’environ 20 étapes. Lorsque l’entrée passe de 1 000 à 2 000, $n{\log }_{2}n$ passe d’environ 9 966 à 21 932, soit un facteur d’environ 2,2. Le logarithme change lui aussi : le nombre augmente donc un peu plus vite que de façon linéaire.

Le travail exponentiel devient rapidement considérable. $2^{10}=1024$ et $2^{20}$ vaut environ un million. À raison d’un milliard d’étapes par seconde, $2^{50}$ étapes prennent tout de même environ 13 jours. Ajouter un élément de plus double ce temps.

Utiliser les notations O informelles

Les programmeurs désignent couramment ces familles par $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^2)$ et $O(2^n)$. Ici, ces notations indiquent la famille de croissance habituelle dans le pire cas. Lis $O(n^2)$ comme « de l’ordre de n au carré ». La notation omet les facteurs constants et les termes de moindre ordre : $n(n-1)\mathrm{/}2$ comparaisons appartient à la famille quadratique.

Une notation O n’est ni un temps d’exécution exact ni un nombre de secondes. Elle ne prétend pas non plus que chaque entrée nécessite le nombre d’étapes du pire cas. Le tri à bulles avec arrêt anticipé a un meilleur cas linéaire mais un pire cas quadratique.

Trouver le point de croisement

Supposons que la méthode A prenne $100n$ étapes et la méthode B, $n^2$. Pour 50 éléments, A prend 5 000 étapes et B en prend 2 500. Pour 100, les deux en prennent 10 000. Pour 1 000, A en prend 100 000 et B un million. La croissance plus lente de A finit par compenser son facteur constant plus élevé.

La vitesse du matériel change l’échelle sans changer la famille. Un ordinateur 100 fois plus rapide permet à une méthode quadratique de traiter seulement 10 fois plus d’éléments dans le même temps, puisque $(10n{)}^2=100n^2$. Une méthode linéaire pourrait en traiter 100 fois plus. Pour une petite tâche, la préparation et les constantes peuvent dominer ; pour de grandes entrées, la croissance devient décisive.

Un temps d’exécution connu et un profil de croissance permettent de prévoir comment se comportera une tâche plus grande. La prévision est une estimation, car le temps réel dépend aussi de l’implémentation, de la mémoire, du matériel et des autres tâches de la machine.

Modifier la taille de l’entrée, puis le temps

Pour un travail linéaire, multiplie le temps par le rapport des tailles d’entrée. Si une recherche dans le pire cas sur un million d’éléments prend 3 millisecondes, dix millions d’éléments prennent environ 30 millisecondes dans des conditions comparables.

Pour un travail quadratique, élève le rapport au carré. Supposons que le tri par sélection prenne 2 secondes pour 50 000 éléments. Doubler à 100 000 éléments donne

secondes. Passer à 500 000 éléments multiplie la taille de l’entrée par 10 : le temps estimé est donc de $2\times {10}^2=200$ secondes. Multiplier le temps par 10 reviendrait à traiter l’algorithme à tort comme linéaire.

Pour une croissance en $n{\log }_{2}n$, utilise le rapport des deux expressions complètes. Doubler une grande entrée coûte un peu plus de deux fois plus, car le logarithme augmente avec le nombre d’éléments.

Remonter à partir d’un budget de temps

Utilise le même temps de référence quadratique : 2 secondes pour 50 000 éléments. Un budget de 32 secondes permet de multiplier le temps par 16. L’entrée peut croître d’un facteur égal à la racine carrée de 16, soit 4, ce qui donne environ 200 000 éléments. Vérifie le sens par substitution : quadrupler l’entrée prévoit un temps 16 fois plus grand, qui passe de 2 à 32 secondes.

Comparer les algorithmes pour une grande taille

Pour un million d’éléments, le tri par sélection effectue 499 999 500 000 comparaisons, soit environ 500 milliards. Le tri fusion en nécessite au plus environ 20 millions. À raison d’un milliard hypothétique de comparaisons par seconde, ces nombres correspondent à environ 500 secondes contre 0,02 seconde, soit une différence d’un facteur proche de 25 000. Ce calcul suppose un coût égal par comparaison pour isoler l’effet de l’algorithme ; les programmes mesurés paient aussi le coût des déplacements et des accès mémoire.

Tester une prévision de croissance

Chronomètre le même programme pour plusieurs tailles qui doublent, comme 10 000, 20 000 et 40 000 éléments. Divise chaque temps par le précédent. Des rapports proches de 2 suggèrent une croissance linéaire ; un peu au-dessus de 2 suggère $n\log n$ ; près de 4 suggère une croissance quadratique.

Garde la même machine et la même méthode de mesure. Répète les exécutions et utilise des tailles assez grandes pour que le temps de démarrage ne domine pas. Compare des cas semblables : chercher en première position pour une taille et chercher sans succès pour une autre mélangerait les effets des entrées et de la croissance. Pour le tri à bulles, les listes triées et les listes en ordre inverse nécessitent des indications de cas différentes.

Si des tailles qui doublent donnent 0,04 ; 0,16 et 0,64 seconde, les deux rapports valent 4, ce qui étaye un modèle quadratique sur cet intervalle. Un rapport perturbé est un indice moins solide qu’un profil répété. Les nombres d’étapes d’un suivi précis peuvent être exacts ; une prévision en secondes doit être présentée comme approximative et vérifiée par des mesures.

Un algorithme correct s’arrête pour toute entrée valide et produit la sortie requise. Une spécification énonce la condition sur l’entrée et le résultat promis. Pour la recherche dichotomique, la précondition est que l’entrée soit triée par ordre croissant. La postcondition est un indice correspondant, ou -1 exactement lorsque la valeur recherchée est absente.

Utiliser un invariant pour relier les étapes

Un invariant de boucle est une propriété vraie avant le début de la boucle et conservée à chaque répétition. Un argument de correction vérifie qu’elle est vraie au départ, qu’elle est conservée et ce qu’elle implique à la fin de la boucle. Un argument distinct de terminaison montre que la boucle finit par s’arrêter.

Pour le tri par sélection, utilise cet invariant : avant le passage i, les i premières positions contiennent les i plus petits éléments dans l’ordre.

1. Départ : avant le passage 0, le préfixe est vide. Il satisfait déjà la propriété.
2. Conservation : le passage trouve le plus petit élément restant. Le placer à la suite allonge le préfixe trié d’un élément, et cet élément est au moins aussi grand que tous ceux qui ont été placés avant lui.
3. Fin : après au plus $n-1$ passages, seul le plus grand élément reste hors du préfixe. Toute la liste est triée.

Chaque déplacement est un échange : le multiensemble des éléments reste donc lui aussi inchangé. Une sortie ordonnée ne suffirait pas à satisfaire toute la spécification du tri.

Le tri à bulles utilise un invariant sur le suffixe : après $k$ passages, les $k$ dernières positions contiennent les $k$ plus grands éléments dans l’ordre. Le passage suivant transporte le plus grand élément non trié jusqu’à ce suffixe. Un passage sans échange établit que toute la partie restante est ordonnée, ce qui permet un arrêt anticipé.

Expliquer les intervalles écartés par la recherche dichotomique

Utilise l’invariant suivant : si la valeur recherchée apparaît, au moins une occurrence se trouve dans l’intervalle de low à high, bornes comprises. Au départ, cet intervalle couvre toute la liste. Si la valeur médiane est trop petite, l’ordre de la liste rend trop petite toute valeur située à mid ou à sa gauche. Mettre low à mid + 1 conserve toute correspondance possible. La mise à jour high = mid - 1 suit le même raisonnement pour les valeurs trop grandes.

Lorsqu’une correspondance est trouvée, la position renvoyée satisfait directement la postcondition. Si l’intervalle devient vide, l’invariant exclut la présence de la valeur recherchée partout dans la liste. L’entrée reste triée car la recherche ne la modifie jamais.

Montrer pourquoi l’exécution s’arrête

Une mesure entière positive ou nulle qui diminue prouve que l’exécution progresse vers une fin. Dans la recherche dichotomique, le nombre de positions candidates diminue strictement après chaque absence de correspondance. L’indice médian testé est exclu : la boucle ne peut donc pas conserver indéfiniment le même intervalle. Les tris à bulles et par sélection effectuent au plus $n-1$ passages pour une entrée non vide et aucun passage pour une entrée vide.

Le tri fusion atteint des listes de zéro ou un élément car chaque appel récursif utilise une liste plus courte. Ces cas de base sont triés. En supposant que les appels sur des listes plus courtes renvoient des moitiés correctement triées, la fusion prend à chaque fois le plus petit élément restant et conserve tous les éléments. Cela transmet la correction jusqu’à l’appel initial.

Utiliser les tests pour une autre tâche

Un test compare un résultat réel à un résultat attendu. Réussir de nombreux tests choisis renforce la confiance, tandis qu’une seule entrée valide qui échoue est un contre-exemple qui réfute la correction. Un argument général par invariant couvre la famille non bornée d’entrées possibles qu’un ensemble fini de tests sur des exemples laisse sans vérification. Les tests sont particulièrement utiles pour vérifier que le code réel implémente la méthode utilisée dans l’argument.

Un cas limite est une entrée valide proche d’une limite, où il est facile de se tromper dans les hypothèses et les bornes des boucles. Prévois le résultat attendu à partir de la spécification avant d’exécuter le code. Sinon, la sortie erronée d’un programme peut devenir discrètement ta réponse attendue.

Choisir des listes qui mettent les limites à l’épreuve

Teste des listes vides, à un élément et à deux éléments ; des listes déjà triées et en ordre inverse ; des valeurs répétées et toutes égales ; des nombres négatifs ; et des longueurs impaires et paires. Pour les recherches, inclus la première position, la dernière position et des valeurs recherchées absentes, respectivement inférieures, supérieures et intermédiaires aux valeurs stockées.

Une recherche dichotomique dans une liste vide doit renvoyer -1 sans accéder à un élément : low = 0 et high = -1 rendent l’intervalle initial vide. Trier [3, 3, 3] doit renvoyer trois exemplaires de 3. Une sortie [3] serait ordonnée mais ne conserverait pas les éléments.

Suivre le plus petit échec

Une recherche dichotomique utilisant while low < high n’entre pas dans sa boucle pour [5] avec la valeur recherchée 5. La correction est low <= high, puisqu’un intervalle à une position contient encore un élément candidat. Ce test à un élément isole la limite plus clairement qu’une longue liste.

Avec low = mid, chercher 20 dans [10, 20] fixe l’indice médian à 0, rencontre 10 et laisse low à 0. L’intervalle reste inchangé à la répétition suivante. Utilise low = mid + 1 pour exclure une position déjà vérifiée. Une liste à deux éléments avec la valeur recherchée en dernier révèle cette boucle infinie.

Le tri à bulles compare items[j] à items[j + 1]. Au premier passage, le dernier indice gauche valide est n - 2. Continuer jusqu’à n - 1 lit au-delà de la liste et déclenche une IndexError de Python. Une telle erreur d’une position à la limite est appelée erreur de décalage d’une unité.

Vérifier les deux garanties sur la sortie

Pour un tri, vérifie l’ordre des éléments adjacents et le nombre d’occurrences de chaque élément d’origine. Utilise des enregistrements identifiés pour tester la stabilité. Ana 85, Ben 92, Cara 85 doit conserver Ana avant Cara lorsqu’un tri stable par note regroupe les notes égales. Une vérification des seules notes ne révélerait pas un échange de ces deux enregistrements.

Génère aussi des listes aléatoires. Compare leurs résultats à ceux d’une implémentation fiable comme sorted de Python. Conserve des doublons et des longueurs différentes dans les entrées générées. Lorsqu’un test échoue, réduis l’entrée tout en conservant l’échec, puis suis son exécution à la main. Garde le petit exemple comme test de non-régression pour que le bogue réparé reste détectable.

Éviter le dépassement dans le calcul de l’indice médian

Les entiers Python grandissent selon les besoins : (low + high) // 2 ne provoque donc pas de dépassement de capacité. Certains langages utilisent des entiers de taille fixe. Pour de très grands indices positifs ou nuls, leur somme peut dépasser la plage représentable. L’addition d’entiers en Java reboucle ; le dépassement de capacité d’un entier signé en C a un comportement indéfini.

Avec des indices valides et low <= high, calcule plutôt low + (high - low) // 2. La différence est positive ou nulle et le résultat reste entre les bornes. Cela calcule le même indice médian arrondi à l’entier inférieur sans former la somme qui pourrait provoquer un dépassement. Les tests aux limites et le raisonnement sur la représentation des nombres dans le langage se complètent ici.

Un algorithme convient à une tâche lorsque ses exigences et ses coûts correspondent aux données et au travail à effectuer. Prends en compte l’ordre de l’entrée, l’accès aux positions, le nombre d’opérations futures, la mémoire supplémentaire, la stabilité et le coût du déplacement des enregistrements.

Comparer les méthodes

La recherche dichotomique nécessite aussi un ordre trié et un accès rapide au milieu. Une bonne comparaison inclut ces prérequis ; un faible nombre de recherches seul ne tient pas compte du coût de préparation de données inadaptées.

Déterminer si trier d’abord est rentable

Pour une recherche dans un million d’éléments non triés, la recherche séquentielle coûte au plus un million de comparaisons. Trier d’abord par tri fusion coûte environ 20 millions de comparaisons avant la première recherche dichotomique, qui nécessite ensuite au plus 20 vérifications médianes. La préparation dépasse largement le gain pour cette seule requête.

Pour 100 requêtes sur une liste inchangée, des recherches séquentielles répétées peuvent coûter 100 millions de comparaisons. Trier une fois puis effectuer 100 recherches dichotomiques coûte environ 20 millions de comparaisons plus 2 000 vérifications médianes. La préparation est réutilisée, ce qui rend le second plan intéressant. Avec ce modèle de coût approximatif, le seuil de rentabilité se situe autour de 20 recherches. L’estimation suppose des coûts d’opération comparables et des parcours dans le pire cas ; ce n’est pas un seuil universel de requêtes.

Évaluer l’ordre, les déplacements et la mémoire

Le tri à bulles peut finir rapidement lorsqu’une seule paire voisine est mal placée. [1, 2, 4, 3, 5] nécessite un échange au premier passage et un deuxième passage pour confirmer l’ordre : sept comparaisons. Mais « presque trié » ne garantit pas un petit nombre de passages. Une petite valeur tout à droite ne peut se déplacer que d’une position vers la gauche à chaque passage.

Le petit nombre d’échanges du tri par sélection est utile lorsque les enregistrements coûtent cher à déplacer. Le tri par sélection et le tri à bulles utilisent tous deux une quantité fixe d’espace supplémentaire. Le tri fusion traite les grandes listes avec une croissance du temps bien plus lente, mais sa forme habituelle sur des listes nécessite de la place pour environ autant d’éléments qu’une liste supplémentaire.

Si les enregistrements de même clé doivent conserver leur ordre antérieur, choisis une méthode stable. Une liste déjà alphabétique par nom peut être triée de façon stable par note tout en restant alphabétique dans chaque groupe de même note. Le tri par sélection ordinaire peut perturber cet ordre entre éléments de même clé.

Utiliser des outils de bibliothèque testés

Les programmes réels utilisent généralement le tri intégré du langage. Le tri stable de Python utilise une méthode adaptative fondée sur la fusion, couramment appelée Timsort, qui tire parti de l’ordre déjà présent dans l’entrée. sorted(items) renvoie une nouvelle liste, tandis que items.sort() modifie la liste existante. Une méthode qui modifie une liste en place du point de vue de son interface peut tout de même utiliser une mémoire de travail temporaire en interne ; elle ne satisfait pas nécessairement la définition à espace supplémentaire fixe utilisée pour les tris simples ci-dessus.

Pour une poignée d’éléments, un code simple et clair peut compter davantage que la croissance. Pour de grandes collections, compare le comportement dans le pire cas et la mémoire, ainsi que les propriétés réellement requises par la tâche.