Flashcards: Techniques de tri et recherche optimisée — 16 cards

Tri par sélection — définition ?

Méthode de tri en sélectionnant le minimum à chaque étape.

Fonction mini — rôle ?

Trouver la position du minimum dans une sous-liste.

Tri en place — avantage ?

Modifie la liste originale sans utiliser de mémoire supplémentaire.

Recherche de minimum — étape clé ?

Identifier le plus petit élément à partir d’un indice donné.

Tri en place — opération principale ?

Échange d’éléments dans la liste sans structure auxiliaire.

Recherche de couples proches — méthode naïve ?

Comparer toutes les paires avec double boucle.

Complexité du tri par sélection ?

O(n²), peu efficace pour grandes listes.

Recherche efficace — principe ?

Utiliser une liste triée pour limiter les comparaisons.

Suppression doublons — dans une liste triée ?

Éliminer les éléments identiques consécutifs.

Complexité recherche naïve couples ?

O(n²), par comparaison de toutes les paires.

Optimisation après tri — comment ?

Comparer uniquement éléments adjacents pour trouver la plus proche.

Suppression doublons — but ?

Obtenir une liste unique et ordonnée.

Complexité du tri par sélection ?

O(n²), à cause des boucles imbriquées.

Recherche efficace — avantage ?

Réduit la complexité à O(n) en utilisant le tri.

Tri en place — définition ?

Tri modifiant directement la liste sans structure supplémentaire.

Recherche de couples proches — méthode naïve ?

Double boucle pour comparer toutes les paires.