Tri : Opération qui ordonne les éléments d'une structure de données selon un critère.
Algorithme de tri : Ensemble d'instructions pour réorganiser les éléments.
- Chercher le plus petit élément dans la partie non triée
- Échanger cet élément avec le premier élément non trié
- Répéter jusqu'à ce que tout le tableau soit trié
- Complexité : O(n²) dans le pire des cas
Tableau T = [64, 34, 25, 12, 22] - Taille n = 5
Chercher le minimum entre T[0] et T[4] : c'est T[3]=12
Échanger T[0] et T[3] → [12, 34, 25, 64, 22]
Chercher le minimum entre T[1] et T[4] : c'est T[4]=22
Échanger T[1] et T[4] → [12, 22, 25, 64, 34]
Chercher le minimum entre T[2] et T[4] : c'est T[2]=25 (déjà bon)
Aucun échange nécessaire → [12, 22, 25, 64, 34]
Chercher le minimum entre T[3] et T[4] : c'est T[4]=34
Échanger T[3] et T[4] → [12, 22, 25, 34, 64]
| Itération | État du tableau | Élément trié |
|---|---|---|
| 0 | [64, 34, 25, 12, 22] | - |
| 1 | [12, 34, 25, 64, 22] | 12 |
| 2 | [12, 22, 25, 64, 34] | 22 |
| 3 | [12, 22, 25, 64, 34] | 25 |
| 4 | [12, 22, 25, 34, 64] | 34 |
| Fini | [12, 22, 25, 34, 64] | 64 |
Le tableau trié par ordre croissant est [12, 22, 25, 34, 64].
• Tri par sélection : Trouver le minimum et l'échanger avec la position actuelle
• Complexité : O(n²) car pour chaque élément, on cherche le minimum dans le reste
• Invariance : Le nombre d'éléments ne change pas, seule l'ordre est modifié
Filtrage : Opération qui sélectionne certains éléments selon un critère prédéfini.
Predicat : Fonction booléenne qui détermine si un élément est conservé.
Tableau T = [10, 3, 25, 8, 15, 7] avec 6 éléments
Nous voulons conserver uniquement les éléments strictement supérieurs à 10
T[0]=10 → 10 > 10 ? Non → Exclu
T[1]=3 → 3 > 10 ? Non → Exclu
T[2]=25 → 25 > 10 ? Oui → Conservé
T[3]=8 → 8 > 10 ? Non → Exclu
T[4]=15 → 15 > 10 ? Oui → Conservé
T[5]=7 → 7 > 10 ? Non → Exclu
Les éléments conservés sont : [25, 15]
Après filtration, le tableau contient [25, 15].
• Filtrage : Conserver uniquement les éléments qui satisfont le critère
• Prédicat : Fonction booléenne qui retourne vrai pour les éléments à conserver
• Longueur variable : Le tableau résultant peut avoir moins d'éléments que l'original
Transformation : Opération qui modifie chaque élément selon une fonction.
Mapping : Application d'une fonction à chaque élément d'une structure.
Nous voulons doubler chaque élément : f(x) = 2x
T[0] = 1 → f(1) = 2×1 = 2
T[1] = 3 → f(3) = 2×3 = 6
T[2] = 5 → f(5) = 2×5 = 10
T[3] = 7 → f(7) = 2×7 = 14
Le tableau transformé est [2, 6, 10, 14]
On applique la fonction à chaque élément → Complexité O(n)
| Élément | Origine | Transformation | Résultat |
|---|---|---|---|
| T[0] | 1 | 2×1 | 2 |
| T[1] | 3 | 2×3 | 6 |
| T[2] | 5 | 2×5 | 10 |
| T[3] | 7 | 2×7 | 14 |
Après transformation, le tableau est [2, 6, 10, 14].
• Transformation : Appliquer une fonction à chaque élément
• Mapping : Le terme anglais pour transformation d'éléments
• Conservation : Le nombre d'éléments reste le même, seule la valeur change
Statistiques descriptives : Mesures qui résument les caractéristiques d'un ensemble de données.
Paramètres : Minimum, maximum, moyenne, médiane, écart-type.
Parcourir le tableau pour trouver la valeur la plus petite
Minimum = min([12, 15, 8, 17, 14]) = 8
Parcourir le tableau pour trouver la valeur la plus grande
Maximum = max([12, 15, 8, 17, 14]) = 17
Somme des valeurs divisée par le nombre d'éléments
Somme = 12 + 15 + 8 + 17 + 14 = 66
Moyenne = 66 ÷ 5 = 13.2
Médiane : Valeur centrale après tri = 14
Étendue : Maximum - Minimum = 17 - 8 = 9
| Mesure | Valeur | Calcul |
|---|---|---|
| Minimum | 8 | min(Notes) |
| Maximum | 17 | max(Notes) |
| Moyenne | 13.2 | ΣNotes/n |
| Médiane | 14 | valeur centrale |
| Étendue | 9 | Max-Min |
Minimum = 8, Maximum = 17, Moyenne = 13.2 pour le tableau [12, 15, 8, 17, 14].
• Statistiques : Calculer des mesures pour résumer les données
• Complexité : O(n) pour les statistiques de base (min, max, moyenne)
• Utilité : Aide à comprendre la distribution des valeurs
Recherche : Opération pour trouver des éléments qui répondent à un critère spécifique.
Indexation : Localisation de la position d'un élément dans une structure.
Tableau T = ['A', 'B', 'C', 'B', 'D'] avec 5 éléments
Nous cherchons toutes les positions où l'élément vaut 'B'
T[0]='A' → 'A' == 'B' ? Non → Passer
T[1]='B' → 'B' == 'B' ? Oui → Ajouter 1 à la liste des indices
T[2]='C' → 'C' == 'B' ? Non → Passer
T[3]='B' → 'B' == 'B' ? Oui → Ajouter 3 à la liste des indices
T[4]='D' → 'D' == 'B' ? Non → Passer
Les positions de 'B' sont [1, 3]
| Indice | Valeur | Correspondance |
|---|---|---|
| 0 | 'A' | false |
| 1 | 'B' | true |
| 2 | 'C' | false |
| 3 | 'B' | true |
| 4 | 'D' | false |
Les positions de 'B' dans le tableau sont [1, 3].
• Recherche : Parcourir la structure pour identifier les éléments correspondants
• Indexation : Stocker les positions des éléments trouvés
• Complexité : O(n) pour une recherche linéaire dans un tableau non trié
- Tri : Ordonner les éléments selon un critère (croissant/décroissant)
- Filtrage : Sélectionner les éléments qui satisfont un prédicat
- Transformation : Appliquer une fonction à chaque élément
- Agrégation : Calculer une valeur synthétique (somme, moyenne, etc.)
- Recherche : Localiser des éléments répondant à un critère
- Les manipulations de données transforment les structures existantes
- La complexité varie selon l'algorithme utilisé (O(n), O(n²), O(n log n))
- Les opérations peuvent être combinées pour des traitements avancés
- Il est important de valider les résultats obtenus
- • Les manipulations de données sont fondamentales en informatique
- • Chaque type d'opération a sa propre complexité et ses usages spécifiques
- • Il est crucial de choisir le bon algorithme pour optimiser les performances
- • Les opérations peuvent être combinées pour créer des traitements complexes
- • La validation des résultats est essentielle pour garantir la fiabilité
