Pensée computationnelle et résolution de problèmes

Une recherche trouve une valeur cible dans un ensemble (souvent un tableau 数组) et retourne sa position, ou "non trouvé".

Recherche linéaire

Une recherche linéaire 线性查找 parcourt du début à la fin, comparant chaque élément avec la cible :

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1   // not found

Aucune préparation n'est nécessaire, donc cela fonctionne sur n'importe quelle liste. Cas le plus défavorable O($n$) (cible à la fin ou absente) ; meilleur cas 1 comparaison. Utilisez-le sur des données non triées ou de petites listes. (La ⟨-1⟩ retournée est une valeur sentinelle — une position impossible qui signifie "non trouvé" ; l'appelant teste IF result = -1.)

La version de l'examen. Paper 3 vous demande de compléter une recherche linéaire écrite avec un indicateur et une boucle WHILE, et Paper 4 d'écrire une fonction qui retourne l'index ou un compteur. Tous deux ressemblent à ceci :

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // how many times Target occurs; 0 means not found
ENDFUNCTION

Pour s'arrêter à la première correspondance au lieu de cela, utilisez une boucle WHILE Index <= 100 AND NOT Found qui définit Found ← TRUE et mémorise l'index. Les points sont pour la boucle sur chaque élément, la comparaison, et ce qui est retourné lorsque la valeur est absente.

Recherche binaire

Une recherche binaire 二分查找 nécessite que les données soient triées. Regardez l'élément central ; s'il est la cible, c'est fini ; si la cible est plus petite, cherchez dans la moitié gauche, sinon dans la moitié droite — divisant la plage par deux à chaque fois :

low ← 1
high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

Cas le plus défavorable O($\log_{2} n$) — pour un million d'éléments, environ 20 comparaisons. Beaucoup plus rapide que la recherche linéaire sur de grands tableaux triés, mais vous devez d'abord trier (un coût ponctuel O($n \log n$)), ce qui vaut le coup si vous recherchez de nombreuses fois.

"Énoncez la condition nécessaire pour une recherche binaire." Les données doivent être ordonnées (triées, croissantes ou décroissantes, sur la clé recherchée). "Décrivez comment effectuer une recherche binaire" (trois points) : (1) trouvez l'élément central de la liste (ou de la plage actuelle) et comparez-le avec la cible ; (2) s'il correspond, la recherche se termine ; si la cible est plus petite, répétez sur la moitié inférieure, si plus grande, sur la moitié supérieure ; (3) continuez à diviser par deux la plage jusqu'à ce que l'élément soit trouvé ou que la plage soit vide, ce qui signifie qu'il n'est pas présent.

La version de l'examen, avec les bornes et un indicateur, est celle à reproduire lorsque l'on vous demande de compléter l'algorithme :

DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    Mid ← (Lower + Upper) DIV 2
    IF Names[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[Mid] < Target THEN
            Lower ← Mid + 1
        ELSE
            Upper ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN
    OUTPUT Mid
ELSE
    OUTPUT "Not found"
ENDIF

"Expliquez comment les performances varient avec le nombre d'éléments." Chaque comparaison réduit de moitié le nombre d'éléments restants, donc le nombre maximum de comparaisons est environ $\log_{2} n$ : doubler la taille de la liste ajoute seulement non comparaison de plus. C'est O($\log n$). "Comparez la recherche linéaire et binaire" : une recherche linéaire nécessite jusqu'à $n$ comparaisons (O($n$)) et, en moyenne, la moitié, mais fonctionne sur des données non triées ; une recherche binaire nécessite au maximum $\log_{2} n$ (O($\log n$)) et est beaucoup plus rapide pour de grandes listes, mais les données doivent d'abord être triées et elle doit permettre l'accès direct à l'élément central (un tableau, pas une liste chaînée). Pour $1000$ éléments : $1000$ contre $10$ comparaisons.

Tri à bulles

Un tri à bulles 冒泡排序 parcourt répétément le tableau, échangeant les paires adjacentes qui ne sont pas dans l'ordre, de sorte que le plus grand élément "bulle" vers la fin à chaque passage :

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

Cas optimal O($n$) (déjà trié, avec sortie anticipée) ; moyen/mauvais cas O($n^{2}$). Simple mais lent pour de grands $n$.

Tri par insertion

Un tri par insertion 插入排序 construit un préfixe trié à partir de la gauche, insérant chaque nouvel élément à sa place en décalant les éléments plus grands vers la droite :

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

Cas optimal O($n$) (déjà trié) ; pire cas O($n^{2}$). Bon pour les tableaux petits ou presque triés. Il trie in place 原地 et est stable 稳定 (conserve l'ordre des éléments égaux).

Suivi d'un tri

Une tâche courante consiste à montrer le tableau après chaque passe externe. Pour [D, T, H, R] avec le tri par insertion : passe 1 (clé T) pas de changement ; passe 2 (clé H) → [D, H, T, R] ; passe 3 (clé R) → [D, H, R, T].

Écrire un tri de zéro. "Écrivez un pseudocode pour trier DataArray[1:1000] par ordre croissant" est répondu par un tri à bulles complet avec le indicateur de sortie anticipée, ou un tri par insertion, déclaré et indenté ; les deux obtiennent la note maximale s'ils fonctionnent pour toute entrée :

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

Pour un ordre décroissant, remplacez > par < ; pour trier des enregistrements ou un tableau 2D par un champ, comparez ce champ mais échangez l'enregistrement entier (ou toutes les colonnes). On vous demande d'écrire un tri par insertion "qui effectue la même tâche" qu'un tri à bulles donné : gardez le même nom de tableau et la même direction et reproduisez le tri par insertion ci-dessus avec la comparaison inversée si l'ordre est décroissant.

"Décrivez deux façons dont les performances d'un tri sont affectées par les données" (deux points). (1) Le nombre d'éléments : un tri $O(n^{2})$ prend quatre fois plus longtemps pour deux fois plus d'éléments. (2) Dans quelle mesure les données sont déjà en ordre : un tri à bulles avec un indicateur, ou un tri par insertion, se termine en une seule passe sur des données déjà triées ($O(n)$) et fait le plus de travail sur des données en ordre inverse ; le nombre d'échanges dépend du nombre de paires désordonnées. (Aussi accepté : la plage ou le nombre de valeurs dupliquées, et si les éléments sont de grands enregistrements coûteux à déplacer.) Les tris à bulles et par insertion sont tous deux O($n^{2}$) dans les pire et cas moyens et O($n$) au mieux ; les tris rapides et par fusion sont O($n \log n$), c'est pourquoi ils sont utilisés pour les grandes données.

Les Types de Données Abstraits (ADT) du Topic 10 apparaissent à l'intérieur de nombreux algorithmes : une pile 栈 guide la traversal en profondeur et l'undo ; une fichier 队列 guide la traversal en largeur et l'ordre d'impression ; une liste chaînée 链表 permet aux données de croître et de diminuer.

Les ADT peuvent être construits à partir d'autres ADT, pas seulement à partir de tableaux : une file à partir de deux piles ; une pile à partir d'une liste chaînée (push = ajouter une tête nœud 节点) ; une file à partir d'une liste chaînée avec des pointeurs de tête et de queue pointers 指针 ; un arbre binaire 二叉树 à partir de nœuds avec deux pointeurs enfants ; un dictionnaire 字典 stocke des paires clé→valeur (souvent sur une table de hachage). Empiler ainsi sépare les préoccupations — l'algorithme utilisant l'ADT n'a pas besoin de savoir comment il est construit.

Les ADT que l'examen vous demande de décrire et d'implémenter

Pile (last in, first out) : les éléments sont ajoutés (pushed) et retirés (popped) à la même extrémité, le sommet ; un pointeur TopOfStack garde l'index de l'élément du sommet. Implémenté avec un tableau et ce seul pointeur : push vérifie que la pile n'est pas pleine, incrémente le pointeur et stocke l'élément ; pop vérifie qu'elle n'est pas vide, retourne l'élément du sommet et décrémente le pointeur.

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN      // full (array 0 to 9)
        RETURN FALSE
    ENDIF
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN      // empty
        RETURN -1
    ENDIF
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

File (first in, first out) : les éléments rejoignent à l'arrière (enfiler) et partent de l'avant (défiler) ; deux pointeurs et un compteur. Dans une file linéaire, le pointeur avant glisse le long du tableau jusqu'à ce que l'espace au début soit gaspillé ; une file circulaire 循环队列 fait tourner les deux pointeurs autour avec MOD, de sorte que chaque cellule est réutilisée.

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN      // full
        RETURN FALSE
    ENDIF
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN      // empty
        RETURN ""
    ENDIF
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

Liste chaînée : une séquence de nœuds, chacun contenant un élément de données et un pointeur vers le nœud suivant ; un pointeur de départ donne le premier nœud et un pointeur nul (0 ou $-1$) termine la liste. Dans une implémentation par tableau, deux tableaux parallèles contiennent les données et les pointeurs, et les cellules inutilisées sont enchaînées dans une liste libre 空闲列表 de sorte qu'une insertion sait où placer le nouveau nœud.

FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // index, or 0 if absent
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN
            RETURN Current
        ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

Pour insérer dans une liste ordonnée : prenez la première cellule libre (NewNode ← FreeList, FreeList ← Pointer[FreeList]), stockez l'élément, puis parcourez la liste avec un pointeur Previous et Current jusqu'à Data[Current] > Item ou la fin ; définissez Pointer[NewNode] ← Current et Pointer[Previous] ← NewNode (ou Start ← NewNode si cela va en premier). Pour supprimer, relier le nœud précédent au-delà de celui supprimé et retourner la cellule à la liste libre.

Arbre binaire : un nœud racine, chaque nœud contenant des données, un pointeur gauche vers un sous-arbre de valeurs plus petites et un pointeur droit vers un sous-arbre de valeurs plus grandes. Implémenté comme un tableau 2D (ou trois tableaux 1D) Tree[Index, 0..2] pour le pointeur gauche, les données, le pointeur droit, avec un pointeur racine et un pointeur next-free.

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // index, or -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN
            RETURN Current
        ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // go left
        ELSE
            Current ← Tree[Current, 2]      // go right
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Pour insérer : stockez l'élément dans le prochain nœud libre avec les deux pointeurs $-1$ ; si l'arbre est vide, faites-en la racine ; sinon, descendez depuis la racine, allez à gauche ou à droite par comparaison, jusqu'à ce que le pointeur que vous suivriez soit $-1$, et définissez ce pointeur vers le nouveau nœud. Un ADT à partir d'un autre ADT : une pile est une liste chaînée où push et pop fonctionnent tous deux au début ; une file est une liste chaînée avec un pointeur de départ et un pointeur de fin ; une file peut être faite à partir de deux piles (push sur l'une, pop de l'autre, tout déplacer quand la seconde est vide) ; les nœuds d'un arbre binaire sont des enregistrements ou objets liés par des pointeurs, donc il est construit à partir d'une structure de liste de nœuds. Dites quelles opérations du nouveau ADT correspondent à quelles opérations de l'ancien.

Complexité temporelle

La complexité temporelle 时间复杂度 est la façon dont le temps d'exécution augmente avec la taille de l'entrée $n$, écrite en notation Big-O 大O表示法 (le terme dominant) : O(1) constant, O($\log n$) recherche binaire, O($n$) recherche linéaire, O($n \log n$) bons tris, O($n^{2}$) tri à bulles/tri par insertion. Un ordre inférieur est meilleur à grande échelle, même si un autre algorithme est plus rapide pour de petites $n$.

Pour rendre cela concret : pour trier un million d'éléments, un tri $O(n \log n)$ se termine en une fraction de seconde, tandis qu'un tri $O(n^{2})$ peut prendre des minutes.

Exemple résolu. Une liste triée contient $1000$ éléments. Combien de comparaisons chaque recherche nécessite-t-elle dans le pire cas ?

Une recherche linéaire vérifie les éléments un par un, donc elle peut nécessiter jusqu'à $1000$ comparaisons — c'est $O(n)$. Une recherche binaire réduit la liste de moitié à chaque étape, donc elle nécessite au maximum $\lceil \log_2 1000 \rceil = 10$ comparaisons — c'est $O(\log n)$. Doubler la liste à $2000$ éléments ajoute seulement non comparaison à la recherche binaire, mais jusqu'à un autre $1000$ à la recherche linéaire — c'est pourquoi l'ordre de croissance, pas la vitesse brute, décide du gagnant à grande échelle.

Décrire un ordre. O(1): le temps est constante, indépendant du nombre d'éléments (ajout dans une pile, lecture d'un élément de tableau). O($\log n$): le temps croît avec le logarithme du nombre d'éléments, donc doubler les données n'ajoute qu'une étape fixe supplémentaire (recherche binaire). O($n$): le temps croît proportionnellement au nombre d'éléments (recherche linéaire, un seul parcours d'une liste). O($n \log n$): un peu pire que linéaire (tri efficaces). O($n^{2}$): le temps croît avec le carré du nombre d'éléments, donc doubler les données quadruple le temps (tri à bulles et tri par insertion). "Donner la complexité Big O d'une recherche binaire de Names[0:99]" est répondu $O(\log n)$, et "décrire sa signification" comme ci-dessus ; la notation Big O mesure comment le temps ou la mémoire s'échelle, pas le temps réel.

Complexité spatiale

Complexité spatiale 空间复杂度 est la mémoire supplémentaire nécessaire. Le tri à bulles et le tri par insertion utilisent O(1) d'espace supplémentaire (en place) ; le tri fusion utilise O($n$) ; la récursion utilise de la mémoire de pile proportionnelle à sa profondeur. Il existe souvent un compromis temps-mémoire.

Autres critères

Simplicité (plus facile à coder et à maintenir), stabilité et adaptativité (plus rapide sur des données presque triées). Le bon algorithme dépend des données et des contraintes.

Les algorithmes récursifs utilisent la récursivité 递归 : une routine s'appelle elle-même avec une version plus petite du même problème, jusqu'à ce qu'un cas de base 基本情形 arrête la chaîne. Elle comporte deux parties : le cas de base (assez petit pour être résolu directement — sans lui, la récursivité ne s'arrête jamais) et le cas récursif 递归情形 (réduire l'entrée et s'appeler elle-même).

Factorielle 阶乘:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

La récursivité est naturelle pour les problèmes auto-similaires : arbres, diviser pour régner 分治 (recherche binaire, tri fusion) et structures de données imbriquées. Lorsqu'elle est mal adaptée, une boucle est généralement plus propre.

"Décrivez ce que signifie la récursivité" (deux points). Une fonction ou une procédure définie en termes d'elle-même : elle s'appelle elle-même depuis son propre corps, avec une version plus petite du problème à chaque fois, jusqu'à ce qu'un cas de base soit atteint. "Énoncez trois caractéristiques essentielles de la récursivité" : (1) un cas de base (condition d'arrêt) qui retourne une valeur sans appel ultérieur ; (2) un cas général 一般情形 dans lequel la routine s'appelle elle-même ; (3) chaque appel rapproche le problème du cas de base (le paramètre est réduit), afin que la récursivité se termine. Certains schémas ajoutent : les valeurs sont retournées lorsque les appels se déroulent.

"Décrivez quand l'utilisation de la récursivité est bénéfique, et donnez un exemple." Lorsque le problème est défini naturellement en termes de versions plus petites de lui-même, de sorte que la solution récursive est plus courte, plus claire et plus proche de la définition mathématique qu'une boucle ne pourrait l'être : factorielle ou nombre de Fibonacci, recherche binaire, parcours d'un arbre binaire, tri fusion ou quicksort, et traitement de structures imbriquées telles que des dossiers contenant des dossiers. C'est un mauvais choix lorsque la profondeur est grande (la pile peut déborder) ou lorsqu'un sous-problème identique est calculé de nombreuses fois (Fibonacci naïf).

Tracé d'un appel récursif

Pour Factorial(4) : les appels descendent jusqu'à Factorial(1)=1, puis le déroulement multiplie vers le haut : 2*1=2, 3*2=6, 4*6=24. Résultat final 24. Suivez chaque appel en attente sur une pile.

Exemple corrigé. La fonction ci-dessous est donnée sans explication. Tracez Unknown(3, 5) et indiquez sa sortie et sa valeur de retour.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

Appel 1 : $X = 3, Y = 5$ : $3 < 5$, sortie 8, appel Unknown(4, 4). Appel 2 : $4 < 4$ est faux, retour 0. Déroulement : l'appel 1 retourne $0 + 1 = 1$. Sortie 8, valeur de retour 1. Écrivez le tracé sous forme de tableau avec une ligne par appel (paramètres, condition, sortie, ce qu'il retourne), et effectuez les retours depuis l'appel le plus profond vers le haut : c'est-à-dire le déroulement que cherche le barème.

Exemple corrigé (Fibonacci). Fib(n) retourne n lorsque n < 2, sinon Fib(n - 1) + Fib(n - 2). Trouvez Fib(5).

Fib(5) = Fib(4) + Fib(3) ; Fib(4) = Fib(3) + Fib(2) ; Fib(3) = Fib(2) + Fib(1) ; Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. Donc Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. Le cas de base est atteint beaucoup de fois (Fib(2) est calculé trois fois), c'est pourquoi cette version est lente : elle effectue 15 appels pour $n = 5$ et double approximativement le nombre d'appels pour chaque augmentation de $n$.

Conversion de la récursivité en itération. Chaque routine récursive peut être réécrite avec une boucle, ce qui utilise moins de mémoire et est plus rapide : conservez un résultat accumulé et boulez du cas de base vers le haut. Factorielle sous forme de boucle :

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

Interpellé pour convertir un tri par insertion ou une recherche récursive en une version itérative, remplacez l'appel à soi-même par une boucle sur l'index que la récursivité parcourait, et transformez le cas de base en condition de sortie de boucle.

Risques

• récursivité infinie si le cas de base est manqué — plantage avec une débordement de pile 栈溢出.
• forte consommation de mémoire pour une récursivité profonde.
• lent si cela répète des travaux (Fibonacci naïf est exponentiel — utilisez une boucle ou la mémoïsaion 记忆化).

La récursivité nécessite que chaque appel dispose de sa propre copie de ses paramètres 参数 et variables locales 局部变量. Le compilateur conserve ces éléments sur la pile d'appels 调用栈. Pour chaque appel, il pousse une trame de pile 栈帧 contenant les paramètres, les variables locales et l'adresse de retour 返回地址 (où reprendre chez l'appelant). Quand la fonction retourne, la valeur de retour est rendue, la trame est retirée, et le contrôle reprend à l'adresse de retour.

Parce que chaque appel a sa propre trame, les appels récursifs ne s'écrasent pas mutuellement leurs variables. La pile peut devenir grande pour une récursivité profonde, ce qui explique pourquoi une récursivité très profonde peut la faire déborder. C'est le même mécanisme d'appel et de retour utilisé pour les appels ordinaires (non récursifs) — il n'y a pas de "mécanisme spécial de récursivité".

"Expliquez pourquoi une pile est appropriée pour implémenter la récursivité" (trois points). Chaque appel récursif doit sauvegarder son adresse de retour, ses paramètres et ses variables locales, et les appels sont terminés dans l'ordre inverse de celui dans lequel ils ont été faits (le dernier appel fait est le premier à terminer), ce qui correspond exactement au comportement dernier entré, premier sorti d'une pile : chaque nouvel appel pousse une trame, et chaque retour retire la trame la plus récente, restaurant l'état de l'appelant et lui indiquant où continuer. C'est le travail du compilateur lorsqu'il traduit le code récursif : il génère la poussée d'une trame de pile à chaque appel et le retrait à chaque retour, et les trames se déroulent alors que les résultats reviennent.

Une question de définition est notée selon un libellé fixe. Apprenez-les exactement et ne donnez qu'une seule réponse.

• Recherches : la recherche linéaire ne nécessite aucun ordre et O($n$) ; la recherche binaire nécessite un tableau trié, divise par deux à chaque étape et est en O($\log n$). Connaître les deux algorithmes par cœur, y compris les bornes et le drapeau.
• Tries : tri à bulles avec indicateur d'échange, tri par insertion avec une clé qui décale les éléments plus grands vers la droite ; tous deux en O($n^{2}$) dans le pire des cas, O($n$) sur des données déjà triées. Les performances dépendent du nombre d'éléments et de leur degré de tri.
• Les implémentations de TDA sont une gestion de pointeurs : un pointeur supérieur ; avant, arrière et compteur avec MOD ; début, pointeurs et liste libre ; racine avec pointeurs gauche et droit. Toujours vérifier les états plein et vide.
• Big O concerne l'échelle : constant, logarithmique, linéaire, carré. Dire "doublester les données ajoute une comparaison" pour une recherche binaire.
• Récursivité : cas de base, cas général, progression vers le cas de base ; bénéfique lorsque le problème est défini en termes de lui-même ; une pile contient les adresses de retour et les variables car les appels retournent dans l'ordre inverse. Tracez avec un tableau et déroulez depuis l'appel le plus profond.

Erreurs courantes

• Utiliser une recherche binaire sur des données non triées, ou sur une liste chaînée ; et définir Lower ← Mid au lieu de Mid + 1, ce qui boucle indéfiniment.
• Une boucle intérieure de tri à bulles qui parcourt toute le tableau à chaque passe, ou un échange sans variable temporaire.
• Un push ou enqueue qui ne teste pas l'état plein, ou un pop ou dequeue qui ne teste pas l'état vide.
• Déplacer le pointeur avant de la file sans MOD dans une file circulaire, ou considérer front = rear comme signifiant toujours vide.
• Insérer dans une liste chaînée en décalant le contenu du tableau ; seuls les pointeurs changent.
• Une fonction récursive sans cas de base, ou dont l'appel récursif ne rend pas le problème plus petit.
• Tracer un appel récursif mais oublier d'ajouter le travail en attente sur le chemin retour.
• Répondre "pourquoi une pile" par "parce que c'est rapide" ; la raison est l'ordre dernier entré, premier sorti des retours.