Fiche de révision : Tableaux et tri par sélection

Plan du Cours

  1. Coût des instructions
  2. Tableaux statiques unidimensionnels
  3. Entrées et sorties des tableaux
  4. Tableaux multidimensionnels
  5. Objectifs des méthodes de tri
  6. Principe du tri par sélection
  7. Tri à bulles
  8. Tri par insertion
  9. Recherche et insertion avec sentinelle
  10. Principes de performance des tris

1. Coût des instructions

Points essentiels

  • Du moins coûteux au plus coûteux en temps, les opérations citées sont : le test d’une expression booléenne, l’affectation, l’appel d’un sous-programme, l’accès en lecture ou en écriture à un fichier ou à un périphérique

2. Tableaux statiques unidimensionnels

Notions clés & Définitions

  • Tableau : Sert à représenter une collection de données de même type.
  • Tableau unidimensionnel : Variable structurée composée d’un nombre entier N de variables de même type, appelées composantes, et N est sa dimension.

★ À maîtriser

📌 Les composantes d’un tableau C de dimension N sont accessibles directement par un indice de 0 à N−1, de sorte que la première est nom_tableau[0] et la dernière nom_tableau[dimension−1].

📌 Le nom d’un tableau représente son adresse mémoire constante, si bien qu’un tableau ne peut pas être affecté à un autre dans les instructions d’une fonction ; seule son initialisation à la déclaration est permise.

Compléments

  • En C, un tableau statique unidimensionnel se déclare sous la forme « <type> <nom_tableau>[dimension] », et sa dimension doit être une constante.

  • Le compilateur alloue pour un tableau statique un espace mémoire contigu suffisant pour ses composantes.

  • Le compilateur C ne contrôle pas le dépassement des limites d’un tableau ; accéder à nom_tableau[dimension] n’est pas détecté à la compilation et peut faire planter le programme si la mémoire correspondante est affectée à une autre variable.

  • Lors de l’initialisation d’un tableau à sa déclaration, les valeurs des composantes peuvent être données entre accolades et les composantes restantes, si la liste est incomplète, sont initialisées à zéro.

  • Si la dimension est omise dans l’initialisation d’un tableau, le compilateur réserve automatiquement l’espace nécessaire au nombre de valeurs initialisées.

3. Entrées et sorties des tableaux

Points essentiels

  • La saisie des composantes d’un tableau de N entiers en C se fait en parcourant les indices de 0 à N−1 et en lisant chaque valeur avec scanf, en transmettant son adresse.

  • L’affichage des composantes d’un tableau en C se fait en parcourant les indices de 0 à N−1, en affichant chaque valeur avec printf, puis en affichant un retour à la ligne.

4. Tableaux multidimensionnels

Notions clés & Définitions

  • Tableau multidimensionnel : Tableau de tableaux.

★ À maîtriser

📌 L’affectation d’un tableau multidimensionnel s’effectue composante par composante, par exemple M[2][5]=125.

Compléments

  • En C, un tableau statique à deux dimensions se déclare sous la forme « <type> <nom_tableau>[dim1][dim2] », par exemple int M[5][10].

📌 L’initialisation d’un tableau multidimensionnel en C peut donner les valeurs des composantes entre accolades, regroupées par sous-tableaux.

  • La saisie d’un tableau à deux dimensions se fait en parcourant les indices des deux dimensions avec deux boucles imbriquées, puis en lisant chaque composante.

5. Objectifs des méthodes de tri

Notions clés & Définitions

  • Tri d’un tableau : Ordonner une collection de données de même type rangées dans un tableau.

★ À maîtriser

  • Les états du tableau à considérer sont :
    • en désordre aléatoire
    • en ordre inverse
    • déjà ordonné

Compléments

  • La rapidité est un critère de classification des méthodes de tri.

6. Principe du tri par sélection

Notions clés & Définitions

  • Passe : Dans le tri par sélection, consiste à parcourir la partie non triée du tableau.

★ À maîtriser

  • Le tri par sélection effectue N−1 passes pour trier un tableau de N composantes.

  • À chaque passe du tri par sélection, on cherche l’indice du plus petit élément du sous-tableau non trié, puis on échange cet élément avec l’élément situé à la frontière du sous-tableau trié.

  • À chaque passe du tri par sélection, l’algorithme mémorise l’indice du minimum du sous-tableau non trié, puis l’échange avec l’élément en position i.

Compléments

  • Dans le programme de tri présenté, i parcourt les passes de 1 à N−1 et j parcourt, pour chaque passe, le sous-tableau de i+1 à N.

  • Le programme présenté comme tri par sélection échange les valeurs dès qu’il trouve T[j] < T[i], et le cours indique qu’il n’est pas optimal parce qu’il effectue trop de permutations inutiles.

  • Dans le tri par sélection, i parcourt les positions de 1 à N−1, j parcourt le sous-tableau de i+1 à N et min mémorise l’indice de la valeur minimale.

📌 Le tri par sélection évite l’échange lorsque i n’est pas inférieur à min, c’est-à-dire lorsque l’élément considéré est déjà à sa place.

7. Tri à bulles

★ À maîtriser

  • À chaque passe du tri à bulles, l’algorithme compare des éléments adjacents du sous-tableau non trié et échange leurs positions si le second est plus petit ; le plus grand finit à la fin de ce sous-tableau.

Compléments

📌 Le tri à bulles est aussi appelé tri échanges et fait remonter les grandes valeurs vers la fin du tableau, tandis que le tri par sélection cherche le minimum du sous-tableau non trié.

  • Le tri à bulles nécessite au plus N−1 passes pour trier un tableau de N composantes.

Astuce mémo

Des bulles remontent vers la surface : les grandes valeurs vont vers la fin du tableau.

8. Tri par insertion

★ À maîtriser

  • À chaque passe du tri par insertion, l’algorithme prend la première composante du sous-tableau non trié et l’insère à sa place dans le sous-tableau déjà trié en décalant vers la droite les éléments plus grands.

Compléments

  • À la passe i, le tri par insertion insère la composante i+1 dans le sous-tableau trié de i composantes.

  • Le tri par insertion nécessite N−1 passes pour trier un tableau de N composantes.

📌 Le tri par insertion est aussi appelé tri du joueur de cartes, par analogie avec l’insertion d’une carte dans un ensemble de cartes déjà trié selon sa couleur et sa valeur.

📌 Dans l’algorithme d’insertion présenté, la condition j>0 empêche le parcours de dépasser la limite du tableau, mais son test répété ralentit le traitement des grands tableaux.

Astuce mémo

Comme un joueur de cartes, on insère chaque nouvelle carte dans une main déjà triée.

9. Recherche et insertion avec sentinelle

★ À maîtriser

  • La recherche avec sentinelle consiste à placer la valeur recherchée en case 0, puis à parcourir le tableau de N à 0 jusqu’à trouver cette valeur ; un arrêt en 0 signifie qu’elle était absente du tableau initial.

Compléments

  • Pour rechercher une valeur dans un tableau non trié de N valeurs avec une sentinelle, le tableau comporte une case supplémentaire d’indice 0.

📌 La recherche sans sentinelle teste la limite du tableau à chaque itération, tandis que la sentinelle permet de supprimer ce test de limite dans la boucle de recherche.

  • Dans le tri par insertion avec sentinelle, T[0] reçoit l’élément à insérer et remplace le test j>0 pendant les décalages vers la droite du sous-tableau trié.

  • La sentinelle est présentée comme un moyen de réduire le nombre d’instructions exécutées.

Astuce mémo

Sans sentinelle, la boucle teste les limites ; avec sentinelle, la valeur recherchée garantit l’arrêt.

10. Principes de performance des tris

Points essentiels

📌 En langage C, il ne faut pas affecter un tableau, car cela provoque une erreur de compilation.

📌 Pour préserver les performances d’un algorithme de tri, il faut éviter les instructions inutiles et les appels de sous-programmes, notamment les fonctions de saisie et d’affichage.

  • Le tri de tableaux de grande taille est à la base du fonctionnement des bases de données et constitue un traitement fréquemment utilisé en informatique.

Teste tes connaissances

Teste tes connaissances sur Tableaux et tri par sélection avec 22 questions à choix multiples et corrections détaillées.

1. En analysant le coût temporel de quatre opérations, quel ordre les classe de la moins coûteuse à la plus coûteuse ?

2. Quel type de données une collection représentée par un tableau peut-elle réunir ?

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de Tableaux et tri par sélection avec 53 flashcards interactives.

Quelles opérations sont citées dans l’ordre croissant de leur coût en temps ?

Le test booléen, l’affectation, l’appel d’un sous-programme, puis l’accès à un fichier ou à un périphérique.

À quoi sert un tableau en programmation ?

À représenter une collection de données de même type.

De quoi un tableau unidimensionnel est-il composé ?

De N variables de même type appelées composantes.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches