COMPTE RENDU

TP N°1,2,3,4,5,6 :
ALGORITHMES DE TRI

Préparé Par :
Encadré Par :
 SADQI Fadl Allah
 Mr BACHAR Anouar
 TP N°1 :
1. Tri à bulles récursif
Principe général

Le tri à bulles est un algorithme de tri par échange qui compare des éléments adjacents
et les permute lorsqu’ils sont dans le mauvais ordre. À chaque passage dans le tableau,
le plus grand élément est progressivement déplacé vers la fin, « comme une bulle qui
remonte à la surface ».

Approche récursive
Dans la version récursive du tri à bulles, l’algorithme est décomposé en deux fonctions
récursives :

 Une première fonction réalise un seul passage dans le tableau, en comparant et

échangeant les éléments adjacents.
 Une seconde fonction appelle récursivement ce passage sur une portion de
tableau de plus en plus réduite.

À chaque appel récursif, la taille du tableau à trier diminue d’une unité, car le dernier
élément est déjà à sa position définitive.

Condition d’arrêt

La récursion s’arrête lorsque la taille du tableau devient inférieure ou égale à 1, ce qui

signifie que le tableau est déjà trié.

Avantages et limites

Ce tri est simple à comprendre et à implémenter, ce qui le rend pédagogique.

Cependant, il reste peu performant, avec une complexité temporelle en O(n²), ce qui le
rend inadapté aux grands volumes de données.
  Fonctions utilitaires communes (lecture, affichage, échange)

1. Tri à bulles récursif

Principe récursif

 Un passage place le plus grand élément à la fin

 On relance le tri sur n-1
2. Tri par sélection récursif
Principe général

Le tri par sélection consiste à rechercher, à chaque étape, le plus petit élément du
tableau et à le placer à sa position correcte. Le tableau est ainsi divisé en deux parties :

 Une partie déjà triée au début

 Une partie non triée contenant les éléments restants

Approche récursive

Dans la version récursive, l’algorithme fonctionne de la manière suivante :

 On recherche récursivement l’indice du plus petit élément dans la partie non

triée du tableau.
 Cet élément est ensuite échangé avec l’élément situé au début de la partie non
triée.
 L’algorithme est alors rappelé récursivement sur la sous-partie restante du
tableau.

À chaque appel récursif, la frontière entre la partie triée et la partie non triée avance
d’une position.

Condition d’arrêt

La récursion se termine lorsque l’indice de départ atteint l’avant-dernier élément du

tableau, ce qui signifie que tous les éléments sont correctement positionnés.

Avantages et limites

Le tri par sélection est facile à analyser et à mettre en œuvre. Il effectue peu d’échanges,
mais son temps d’exécution reste quadratique (O(n²)), indépendamment de l’ordre
initial des données.

Principe récursif

 Trouver le minimum
 Le placer au début
 Trier le reste
3. Tri par insertion récursif
Principe général

Le tri par insertion repose sur l’idée d’insérer chaque élément du tableau à sa position
correcte dans une partie déjà triée. Ce mécanisme est similaire à la manière dont on
classe des cartes à jouer dans la main.

Approche récursive

Dans la version récursive :

 L’algorithme commence par trier récursivement les n-1 premiers éléments du

tableau.
 Une fois cette partie triée, le dernier élément est inséré à sa place correcte dans
la sous-liste ordonnée.

L’insertion se fait par décalage des éléments plus grands vers la droite jusqu’à trouver la
position adéquate.

Condition d’arrêt

La récursion s’arrête lorsque la taille du tableau est égale à 1, car un seul élément est
considéré comme déjà trié.

Avantages et limites

Le tri par insertion est particulièrement efficace pour les petits tableaux ou les tableaux
presque triés. Sa complexité est O(n²) dans le pire des cas, mais elle peut être bien
meilleure lorsque les données sont déjà partiellement ordonnées.

Principe récursif

 Trier les n-1 premiers

 Insérer le dernier élément à sa place
4. Tri rapide (Quicksort récursif)
Principe général

Le tri rapide est un algorithme basé sur le paradigme « diviser pour régner ». Il consiste
à choisir un élément pivot, puis à partitionner le tableau en deux sous-tableaux :

 Un sous-tableau contenant les éléments inférieurs ou égaux au pivot

 Un sous-tableau contenant les éléments strictement supérieurs au pivot

Le pivot est alors placé à sa position définitive.

Approche récursive

Dans la version récursive du tri rapide :

 La fonction de partitionnement place le pivot à la bonne position et retourne son

indice.
 L’algorithme est ensuite appelé récursivement sur les deux sous-tableaux
obtenus (gauche et droite du pivot).

Ce processus se répète jusqu’à ce que tous les sous-tableaux soient réduits à une taille
minimale.

Condition d’arrêt

La récursion s’arrête lorsque les indices de début et de fin se croisent ou deviennent

égaux, ce qui signifie que le sous-tableau contient zéro ou un seul élément.

Avantages et limites

Le tri rapide est l’un des algorithmes de tri les plus performants en pratique, avec une
complexité moyenne en O(n log n). Toutefois, dans le pire des cas (mauvais choix de
pivot), sa complexité peut atteindre O(n²).

Partitionnement
Quicksort récursif

Fonction principale main() (exemple complet)

Conclusion générale
L’utilisation de la récursivité dans les algorithmes de tri permet une meilleure
structuration du code et une correspondance directe avec les principes algorithmiques
théoriques. Bien que certains algorithmes comme le tri à bulles ou le tri par sélection
restent peu performants, ils jouent un rôle pédagogique essentiel pour comprendre les
mécanismes fondamentaux du tri. Le tri rapide, quant à lui, illustre parfaitement la
puissance de la récursivité et du paradigme « diviser pour régner ».
 TP N°2 :
Recherche dichotomique récursive :

1. Principe général de la recherche dichotomique

La recherche dichotomique est un algorithme de recherche rapide qui s’applique
uniquement aux tableaux triés. Son principe repose sur une stratégie de division
successive du tableau en deux parties.

À chaque étape, l’algorithme compare la valeur recherchée avec l’élément situé au

milieu du tableau :

 Si la valeur est égale à l’élément central, la recherche s’arrête avec succès.

 Si la valeur est plus petite, la recherche continue dans la moitié gauche.
 Si la valeur est plus grande, la recherche continue dans la moitié droite.

Ce mécanisme permet de réduire l’espace de recherche de moitié à chaque étape, ce qui

rend l’algorithme très performant.

2. Passage de la version itérative à la version récursive

Dans la version récursive, la boucle TantQue est remplacée par :

 un appel récursif sur une sous-partie du tableau,

 avec des bornes mises à jour (début et fin).

Chaque appel récursif traite un sous-tableau plus petit, jusqu’à atteindre une condition
d’arrêt.

3. Recherche dichotomique récursive – tableau trié en

ordre croissant
Principe récursif

La fonction récursive reçoit :

 le tableau,
 l’indice de début,
 l’indice de fin,
 la valeur recherchée.

À chaque appel :

1. On calcule l’indice du milieu.

2. On compare la valeur recherchée avec l’élément du milieu.
3. On appelle récursivement la fonction sur la moitié pertinente.

Condition d’arrêt
  Si début > fin → la valeur n’existe pas dans le tableau.
 Si tableau[milieu] == valeur → la valeur est trouvée.

Implémentation en C (version récursive)

4. Recherche dichotomique récursive – tableau trié en

ordre décroissant
Particularité du cas décroissant

Dans un tableau trié en ordre décroissant, les comparaisons sont inversées :

 Les valeurs les plus grandes se trouvent à gauche.

 Les valeurs plus petites se trouvent à droite.

Le principe récursif reste le même, mais la logique de comparaison est adaptée.

Implémentation en C (version récursive)

5. Avantages de la version récursive
La version récursive de la recherche dichotomique présente plusieurs avantages :

 Elle correspond directement à la définition théorique de l’algorithme.

 Elle rend le code plus lisible et plus structuré.
 Elle illustre clairement le principe de division du problème en sous-problèmes.

Cependant, elle utilise la pile d’exécution, ce qui peut être légèrement moins optimal
que la version itérative pour de très grands tableaux.

6. Complexité temporelle
La recherche dichotomique récursive a une complexité :

 O(log n) dans tous les cas (meilleur, moyen et pire cas).

Cela signifie que le nombre d’opérations augmente très lentement même lorsque la taille
du tableau devient grande, ce qui en fait un algorithme très efficace.
  Puis on a le programme principale

7. Conclusion pour le compte rendu

La recherche dichotomique récursive est une méthode efficace et élégante pour
rechercher un élément dans un tableau trié. En exploitant le principe de récursivité,
l’algorithme divise le problème initial en sous-problèmes de taille réduite, ce qui permet
d’obtenir un temps d’exécution logarithmique. Cette approche met en évidence
l’importance du tri préalable des données et illustre parfaitement l’application du
paradigme « diviser pour régner » dans les algorithmes de recherche.
 TP N°3:
Les Structures :
En langage C, une structure permet de regrouper plusieurs variables de types différents
sous un même nom. Elle est utilisée pour représenter des objets complexes du monde
réel, comme un point géométrique, un étudiant ou un produit dans un magasin.

Dans ce TP, les structures sont utilisées pour :

 représenter un point avec ses coordonnées (x, y),

 stocker les informations d’un étudiant (nom, âge, note),
 gérer un stock de produits à l’aide de structures imbriquées.

L’utilisation des structures rend le programme plus organisé, lisible et facilite la

manipulation des données complexes, notamment lorsqu’on travaille avec des
tableaux et des fonctions.

Réponse à l’Exercice 4 (Travail à faire) :

Objectif de l’exercice

 Manipuler des structures (Produit et Magasin)

 Utiliser des fonctions avec pointeurs
 Mettre à jour la quantité d’un produit existant dans le stock

 Structures utilisées
 Fonction rechercher_produit

 Fonction Update_Stock

 Fonction main()
Toute l’exercice :
conclusion pour le TP N°3 :
Ce TP nous a permis de comprendre l’utilisation des structures en langage C, ainsi que
leur manipulation à travers des fonctions et des pointeurs. La gestion du stock à l’aide
de structures imbriquées illustre un cas réel d’application des structures, tout en
renforçant les notions de modularité et de réutilisation du code.
 TP N°4 :
Introduction : Concept de la gestion des fichiers
La gestion des fichiers en langage C permet de stocker et de manipuler des données de
manière persistante, c’est-à-dire indépendante de l’exécution du programme.
Contrairement aux variables en mémoire qui sont perdues à la fin du programme, les
fichiers permettent de conserver les informations sur le disque dur pour une utilisation
ultérieure.

Les fichiers jouent un rôle essentiel dans les applications informatiques pour :

 sauvegarder des données (bases de données simples, inventaires,

configurations),
 échanger des informations entre programmes,
 traiter de grands volumes de données sans surcharge mémoire.

En C, la gestion des fichiers repose principalement sur :

 l’ouverture d’un fichier (fopen),

 la lecture et l’écriture (fscanf, fprintf),
 le positionnement dans le fichier (fseek, ftell),
 la fermeture du fichier (fclose).

Ce TP illustre ces concepts à travers la création, la lecture, la modification et le filtrage

de données stockées dans un fichier texte représentant un magasin de produits.

Travail à faire – Partie 2 : Gestion d’un magasin

Objectif
Créer un programme en C permettant :

 de gérer un fichier [Link],

 d’ajouter des produits,
 de modifier et nettoyer les données à l’aide des fichiers.

Structure utilisée :
 Travail à faire :
Code C complet (toutes les étapes réunies) :
 TP N°5 :
Les listes chainées :
Introduction : Les listes chaînées (pour le compte
rendu)
Une liste chaînée est une structure de données dynamique composée d’un ensemble
d’éléments appelés maillons. Chaque maillon contient :

 une partie information (les données),

 une partie pointeur qui référence le maillon suivant dans la liste.

Contrairement aux tableaux, les listes chaînées :

 n’ont pas de taille fixe,

 permettent des insertions et suppressions faciles sans décaler les éléments,
 utilisent la mémoire de façon dynamique grâce à l’allocation (malloc) et la
libération (free).

Dans une liste simplement chaînée, chaque élément pointe uniquement vers le suivant.
Cette structure est très utilisée pour gérer des collections dynamiques comme des
bibliothèques, des files d’attente ou des historiques.

Dans ce TP, la liste chaînée est utilisée pour gérer une bibliothèque de livres, avec des
opérations d’ajout, de suppression, de recherche et de comptage.

Énoncé 2 : Gestion d’une bibliothèque (Liste chaînée)

Structure Livre
Fonctions demandées
Vérification de l’unicité du code

1. Ajouter en tête

2. Ajouter en fin
3. Afficher tous les livres

4. Rechercher un livre
5. Supprimer un livre par code

6. Compter les doublons de titres

Programme principale :
Conclusion (compte rendu)
Ce TP a permis de maîtriser la manipulation des listes chaînées en langage C,
notamment l’allocation dynamique de la mémoire et la gestion des pointeurs. La mise
en place d’un menu interactif a facilité l’utilisation des différentes opérations de gestion
d’une bibliothèque. Cette structure de données s’avère très efficace pour gérer des
ensembles dynamiques d’informations.