Algorithme d’insertion d’une valeur dans un tableau trié

Bac SC 03-09-26

37 0

Plan de tutoriel

1- Principe de l'algorithme d’insertion d’une valeur dans un tableau trié

2- Algorithme d’insertion d’une valeur dans un tableau trié

3- Programme Python

Principe de l'algorithme d’insertion d’une valeur dans un tableau trié

Le programme permet d’insérer une nouvelle valeur dans un tableau déjà trié dans l’ordre croissant, tout en conservant cet ordre après l’insertion. L’utilisateur commence par indiquer le nombre d’éléments du tableau, avec une taille comprise entre 2 et 14.

Ensuite, le programme demande à l’utilisateur de saisir les éléments du tableau. Lors de la saisie, chaque nouvel élément doit être supérieur à l’élément précédent. Cette vérification garantit que le tableau est construit directement dans l’ordre croissant.

Après le remplissage, l’utilisateur saisit la valeur x à insérer. Le programme doit alors trouver la position correcte de cette valeur sans effectuer un nouveau tri complet du tableau.

Pour réaliser cette insertion, le programme commence à partir de la fin du tableau. Il compare x avec l’élément qui la précède. Tant que cet élément est supérieur à x, il est décalé d’une position vers la droite. Le programme continue ainsi vers le début du tableau jusqu’à trouver la position où x doit être placée.

Lorsque la bonne position est trouvée, la valeur x y est insérée. Les éléments déplacés sont ainsi conservés et le tableau reste trié dans l’ordre croissant.

Enfin, le programme affiche le tableau contenant désormais n + 1 éléments, avec la nouvelle valeur correctement positionnée.

Algorithme d’insertion d’une valeur dans un tableau trié

Dans cet algorithme, On va utiliser deux fonctions et deux procédures :

- la fonction saisie_taille

- la procédure remplir

- la fonction saisie

- la procédure insertion

Algorithme du programme Principal

Le programme principal assure l’enchaînement des différentes étapes nécessaires pour insérer une nouvelle valeur dans un tableau déjà trié dans l’ordre croissant.

Tout d’abord, il appelle la fonction saisie_taille() afin de demander à l’utilisateur le nombre d’éléments du tableau. Ensuite, il appelle la fonction remplir(t, n) pour saisir les n éléments en respectant l’ordre croissant.

Le programme demande ensuite à l’utilisateur de saisir la valeur x à insérer dans le tableau. Il appelle la fonction insertion(t, n, x), qui recherche la position correcte de x en décalant vers la droite les éléments qui lui sont supérieurs.

Enfin, le programme affiche le message « Tableau après insertion » puis appelle afficher(t, n + 1) afin d’afficher le tableau contenant désormais n + 1 éléments, tout en conservant l’ordre croissant.

Algorithme INSERTION_TABLEAU
Debut  
     # Appeler la fonction saisie_taille()
     # pour obtenir le nombre d'éléments du tableau.
     n <-- saisie_taille()
     # Afficher un message avant le remplissage du tableau.
     Ecrire("***Remplissage du tableau***")
     # Appeler la fonction remplir() pour saisir
     # les n éléments du tableau dans l'ordre croissant.
     remplir(t, n)
     # Demander à l'utilisateur de saisir
     # la valeur à insérer dans le tableau.
     x <-- saisie()
     # ==========================================================
     # Insertion de la valeur dans le tableau
     # ==========================================================
     # Appeler la fonction insertion().
     # Elle insère x dans le tableau tout en conservant
     # l'ordre croissant des éléments.
     #
     # Le paramètre n représente le nombre d'éléments
     # présents avant l'insertion.
     insertion(t, n, x)
     # Afficher un message après l'insertion.
     Ecrire("***Tableau après insertion***")
     # Afficher les n+1 éléments du tableau.
     # Le tableau contient maintenant un élément supplémentaire :
     # la valeur x qui vient d'être insérée.
     afficher(t, n + 1) 
Fin

Algorithme INSERTION_TABLEAU

Debut

# Appeler la fonction saisie_taille()

# pour obtenir le nombre d'éléments du tableau.

n <-- saisie_taille()

# Afficher un message avant le remplissage du tableau.

Ecrire("***Remplissage du tableau***")

# Appeler la fonction remplir() pour saisir

# les n éléments du tableau dans l'ordre croissant.

remplir(t, n)

# Demander à l'utilisateur de saisir

# la valeur à insérer dans le tableau.

x <-- saisie()

# ==========================================================

# Insertion de la valeur dans le tableau

# ==========================================================

# Appeler la fonction insertion().

# Elle insère x dans le tableau tout en conservant

# l'ordre croissant des éléments.

# Le paramètre n représente le nombre d'éléments

# présents avant l'insertion.

insertion(t, n, x)

# Afficher un message après l'insertion.

Ecrire("***Tableau après insertion***")

# Afficher les n+1 éléments du tableau.

# Le tableau contient maintenant un élément supplémentaire :

# la valeur x qui vient d'être insérée.

afficher(t, n + 1)

Fin

Déclaration des objets

Objet	Type / Nature
n	entier
x	entier
t	tableau des entiers

La fonction saisie_taille

La fonction saisie_taille() permet de saisir et de contrôler le nombre d’éléments n du tableau. Elle demande à l’utilisateur de donner une valeur comprise entre 2 et 14.

Fonction saisie_taille():entier
    # La variable test permet de contrôler
    # si la taille saisie est correcte.
    test <-- Faux
    # Répéter la saisie tant que la valeur
    # n'est pas comprise entre 2 et 14.
    Tant que test = Faux faire
        # Demander à l'utilisateur de saisir
        # la taille du tableau.
        Ecrire("donner n entre 2 et 14: ")
        Lire(n) 
        # Vérifier que n est comprise entre 2 et 14.
        Si 2 <= n <= 14 alors
            # La taille saisie est correcte.
            test <-- Vrai
        Fin si
    Fin tant que 
    # Retourner la taille du tableau.
    retourner n 
Fin

Fonction saisie_taille():entier

# La variable test permet de contrôler

# si la taille saisie est correcte.

test <-- Faux

# Répéter la saisie tant que la valeur

# n'est pas comprise entre 2 et 14.

Tant que test = Faux faire

# Demander à l'utilisateur de saisir

# la taille du tableau.

Ecrire("donner n entre 2 et 14: ")

Lire(n)

# Vérifier que n est comprise entre 2 et 14.

Si 2 <= n <= 14 alors

# La taille saisie est correcte.

test <-- Vrai

Fin si

Fin tant que

# Retourner la taille du tableau.

retourner n

Fin

Déclaration des objets

Objet	Type / Nature
n	entier

La procédure remplir

La procédure remplir(t, n) permet de remplir les n premières cases du tableau t avec des entiers dans l’ordre croissant.

Le premier élément est saisi directement.

Pour chaque élément suivant, le programme vérifie qu’il est strictement supérieur à l’élément précédent. Si la valeur saisie ne respecte pas l’ordre croissant, une nouvelle saisie est demandée.

Ainsi, à la fin de la procédure, le tableau contient des éléments strictement croissants.

Procédure remplir(var t:tab; n:entier)
    # Saisir le premier élément du tableau.
    Ecrire("donner un element du tableau : ")
    Lire(t[0])
    # Parcourir les cases restantes du tableau.
    Pour i de 1 à n-1 faire
        # La variable test permet de vérifier
        # si l'élément saisi respecte l'ordre croissant.
        test <-- Faux
        # Répéter la saisie tant que l'élément
        # n'est pas supérieur à l'élément précédent.
        Tant que test = Faux:
            # Saisir un élément du tableau.
            Ecrire("donner un element du tableau : ")
            Lire(t[i]) 
            # Vérifier que l'élément courant est supérieur
            # à l'élément précédent.
            Si t[i] > t[i - 1] alors
                # L'ordre croissant est respecté.
                test <-- Vrai
            Finsi
        Fin tant que
    Fin pour  
Fin

Procédure remplir(var t:tab; n:entier)

# Saisir le premier élément du tableau.

Ecrire("donner un element du tableau : ")

Lire(t[0])

# Parcourir les cases restantes du tableau.

Pour i de 1 à n-1 faire

# La variable test permet de vérifier

# si l'élément saisi respecte l'ordre croissant.

test <-- Faux

# Répéter la saisie tant que l'élément

# n'est pas supérieur à l'élément précédent.

Tant que test = Faux:

# Saisir un élément du tableau.

Ecrire("donner un element du tableau : ")

Lire(t[i])

# Vérifier que l'élément courant est supérieur

# à l'élément précédent.

Si t[i] > t[i - 1] alors

# L'ordre croissant est respecté.

test <-- Vrai

Finsi

Fin tant que

Fin pour

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
test	booléen

La fonction saisie

La fonction saisie() permet de demander à l'utilisateur de saisir une valeur entière à insérer dans le tableau, puis de retourner cette valeur.

Fonction saisie():entier
    Ecrire("donner n entre 2 et 14: ")
    Lire(n) 
    retourner n 
Fin

Fonction saisie():entier

Ecrire("donner n entre 2 et 14: ")

Lire(n)

retourner n

Fin

Déclaration des objets

Objet	Type / Nature
n	entier

La procédure insertion

La procédure insertion(t, n, x) insère la valeur x dans un tableau t déjà trié dans l’ordre croissant, en conservant cet ordre. Elle compare x aux éléments précédents, décale vers la droite les éléments supérieurs à x, puis place x à sa position correcte.

Procédure TRI(var t:tab; g:entier; d:entier) :     
  # Commencer par la dernière position disponible.
    # La valeur x sera éventuellement placée
    # dans l'une des positions précédentes.
    i <-- n
    # Tant que l'élément précédent est supérieur à x
    # et que l'on n'est pas arrivé avant le début du tableau,
    # décaler l'élément vers la droite.
    Tant que (t[i - 1] > x) et (i > 0) faire
        # Copier l'élément précédent dans la case courante.
        # Cela permet de libérer une position pour x.
        t[i] <-- t[i - 1]
        # Reculer d'une position pour continuer
        # la recherche de la position de x.
        i <-- i - 1
    Fin tant que
    # Insérer x à sa position correcte.
    # Tous les éléments situés à gauche sont
    # inférieurs ou égaux à x.
    t[i] <-- x
Fin

Procédure TRI(var t:tab; g:entier; d:entier) :

# Commencer par la dernière position disponible.

# La valeur x sera éventuellement placée

# dans l'une des positions précédentes.

i <-- n

# Tant que l'élément précédent est supérieur à x

# et que l'on n'est pas arrivé avant le début du tableau,

# décaler l'élément vers la droite.

Tant que (t[i - 1] > x) et (i > 0) faire

# Copier l'élément précédent dans la case courante.

# Cela permet de libérer une position pour x.

t[i] <-- t[i - 1]

# Reculer d'une position pour continuer

# la recherche de la position de x.

i <-- i - 1

Fin tant que

# Insérer x à sa position correcte.

# Tous les éléments situés à gauche sont

# inférieurs ou égaux à x.

t[i] <-- x

Fin

Déclaration des objets

Objet	Type / Nature
i	entier

Programme en Python

# ==========================================================
# Importation de la bibliothèque NumPy
# ==========================================================

from numpy import array

# Importer la fonction array de NumPy.
# Elle permet de créer un tableau.


# ==========================================================
# Création du tableau
# ==========================================================

# Créer un tableau de 100 éléments.
# Toutes les cases sont initialisées à 0.
# Dans notre programme, seules les n premières cases
# contiendront les éléments du tableau.
t = array([int()] * 100)


# ==========================================================
# Fonction de saisie de la taille du tableau
# ==========================================================

def saisie_taille():

    # La variable test permet de contrôler
    # si la taille saisie est correcte.
    test = False

    # Répéter la saisie tant que la valeur
    # n'est pas comprise entre 2 et 14.
    while test == False:

        # Demander à l'utilisateur de saisir
        # la taille du tableau.
        n = int(input("donner n entre 2 et 14: "))

        # Vérifier que n est comprise entre 2 et 14.
        if 2 <= n <= 14: # La taille saisie est correcte. 
           test = True 
    # Retourner la taille du tableau. 
    return n 

# Fonction de saisie de la valeur à insérer 
def saisie(): 
    # Demander à l'utilisateur de saisir 
    # la valeur qui doit être insérée dans le tableau. 
    n = int(input("donner la valeur à insérer: ")) 
    # Retourner la valeur saisie. 
    return n 

# Procédure de remplissage du tableau 
def remplir(t, n): 
    # Saisir le premier élément du tableau. 
    t[0] = int(input("donner un element du tableau : ")) 
    # Parcourir les cases restantes du tableau. 
    for i in range(1, n): 
      # La variable test permet de vérifier 
      # si l'élément saisi respecte l'ordre croissant. 
      test = False 
      # Répéter la saisie tant que l'élément 
      # n'est pas supérieur à l'élément précédent. 
      while test == False: 
         # Saisir un élément du tableau. 
         t[i] = int(input("donner un element du tableau : ")) 
         # Vérifier que l'élément courant est supérieur 
         # à l'élément précédent. 
         if t[i] > t[i - 1]:
            # L'ordre croissant est respecté.
            test = True
    

# ==========================================================
# Procédure d'insertion d'une valeur dans un tableau trié
# ==========================================================

def insertion(t, n, x):

    # Commencer par la dernière position disponible.
    # La valeur x sera éventuellement placée
    # dans l'une des positions précédentes.
    i = n

    # Tant que l'élément précédent est supérieur à x
    # et que l'on n'est pas arrivé avant le début du tableau,
    # décaler l'élément vers la droite.
    while (t[i - 1] > x) and (i > 0):

        # Copier l'élément précédent dans la case courante.
        # Cela permet de libérer une position pour x.
        t[i] = t[i - 1]

        # Reculer d'une position pour continuer
        # la recherche de la position de x.
        i = i - 1

    # Insérer x à sa position correcte.
    # Tous les éléments situés à gauche sont
    # inférieurs ou égaux à x.
    t[i] = x


# ==========================================================
# Procédure d'affichage du tableau
# ==========================================================

def afficher(t, n):

    # Parcourir les n premières cases du tableau.
    for i in range(n):

        # Afficher la valeur contenue dans la case t[i].
        print(t[i])


# ==========================================================
# Programme principal
# ==========================================================

# Appeler la fonction saisie_taille()
# pour obtenir le nombre d'éléments du tableau.
n = saisie_taille()


# Afficher un message avant le remplissage du tableau.
print("***Remplissage du tableau***")


# Appeler la fonction remplir() pour saisir
# les n éléments du tableau dans l'ordre croissant.
remplir(t, n)


# Demander à l'utilisateur de saisir
# la valeur à insérer dans le tableau.
x = saisie()


# ==========================================================
# Insertion de la valeur dans le tableau
# ==========================================================

# Appeler la fonction insertion().
# Elle insère x dans le tableau tout en conservant
# l'ordre croissant des éléments.
#
# Le paramètre n représente le nombre d'éléments
# présents avant l'insertion.
insertion(t, n, x)


# Afficher un message après l'insertion.
print("***Tableau après insertion***")


# Afficher les n+1 éléments du tableau.
# Le tableau contient maintenant un élément supplémentaire :
# la valeur x qui vient d'être insérée.
afficher(t, n + 1)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

# ==========================================================

# Importation de la bibliothèque NumPy

# ==========================================================

from numpy import array

# Importer la fonction array de NumPy.

# Elle permet de créer un tableau.

# ==========================================================

# Création du tableau

# ==========================================================

# Créer un tableau de 100 éléments.

# Toutes les cases sont initialisées à 0.

# Dans notre programme, seules les n premières cases

# contiendront les éléments du tableau.

t = array([int()] * 100)

# ==========================================================

# Fonction de saisie de la taille du tableau

# ==========================================================

def saisie_taille():

# La variable test permet de contrôler

# si la taille saisie est correcte.

test = False

# Répéter la saisie tant que la valeur

# n'est pas comprise entre 2 et 14.

while test == False:

# Demander à l'utilisateur de saisir

# la taille du tableau.

n = int(input("donner n entre 2 et 14: "))

# Vérifier que n est comprise entre 2 et 14.

if 2 <= n <= 14: # La taille saisie est correcte.

test = True

# Retourner la taille du tableau.

return n

# Fonction de saisie de la valeur à insérer

def saisie():

# Demander à l'utilisateur de saisir

# la valeur qui doit être insérée dans le tableau.

n = int(input("donner la valeur à insérer: "))

# Retourner la valeur saisie.

return n

# Procédure de remplissage du tableau

def remplir(t, n):

# Saisir le premier élément du tableau.

t[0] = int(input("donner un element du tableau : "))

# Parcourir les cases restantes du tableau.

for i in range(1, n):

# La variable test permet de vérifier

# si l'élément saisi respecte l'ordre croissant.

test = False

# Répéter la saisie tant que l'élément

# n'est pas supérieur à l'élément précédent.

while test == False:

# Saisir un élément du tableau.

t[i] = int(input("donner un element du tableau : "))

# Vérifier que l'élément courant est supérieur

# à l'élément précédent.

if t[i] > t[i - 1]:

# L'ordre croissant est respecté.

test = True

# ==========================================================

# Procédure d'insertion d'une valeur dans un tableau trié

# ==========================================================

def insertion(t, n, x):

# Commencer par la dernière position disponible.

# La valeur x sera éventuellement placée

# dans l'une des positions précédentes.

i = n

# Tant que l'élément précédent est supérieur à x

# et que l'on n'est pas arrivé avant le début du tableau,

# décaler l'élément vers la droite.

while (t[i - 1] > x) and (i > 0):

# Copier l'élément précédent dans la case courante.

# Cela permet de libérer une position pour x.

t[i] = t[i - 1]

# Reculer d'une position pour continuer

# la recherche de la position de x.

i = i - 1

# Insérer x à sa position correcte.

# Tous les éléments situés à gauche sont

# inférieurs ou égaux à x.

t[i] = x

# ==========================================================

# Procédure d'affichage du tableau

# ==========================================================

def afficher(t, n):

# Parcourir les n premières cases du tableau.

for i in range(n):

# Afficher la valeur contenue dans la case t[i].

print(t[i])

# ==========================================================

# Programme principal

# ==========================================================

# Appeler la fonction saisie_taille()

# pour obtenir le nombre d'éléments du tableau.

n = saisie_taille()

# Afficher un message avant le remplissage du tableau.

print("***Remplissage du tableau***")

# Appeler la fonction remplir() pour saisir

# les n éléments du tableau dans l'ordre croissant.

remplir(t, n)

# Demander à l'utilisateur de saisir

# la valeur à insérer dans le tableau.

x = saisie()

# ==========================================================

# Insertion de la valeur dans le tableau

# ==========================================================

# Appeler la fonction insertion().

# Elle insère x dans le tableau tout en conservant

# l'ordre croissant des éléments.

# Le paramètre n représente le nombre d'éléments

# présents avant l'insertion.

insertion(t, n, x)

# Afficher un message après l'insertion.

print("***Tableau après insertion***")

# Afficher les n+1 éléments du tableau.

# Le tableau contient maintenant un élément supplémentaire :

# la valeur x qui vient d'être insérée.

afficher(t, n + 1)

Exécution du programme

0 commentaire

laisser un commentaire

Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Nom *

Email *

Message *

Passion de robotique

Tutoriels récents

Algorithme d’insertion d’une valeur dans un tableau trié

Bac SC 03-09-26

Algorithme : Tri RAPIDE du tableau des entiers

Bac SC 01-09-26

Algorithme : Tri de SHELL du tableau des entiers

Bac SC 30-08-26

Algorithme : Tri par insertion du tableau des entiers

Bac SC 29-08-26

Algorithme : Tri à Bulle du tableau des entiers

Bac SC 29-08-26

Atelier robotique

Tutoriels populaires

Présentation de la carte ESP32

ESP32 13840vues

Afficher la température et l’humidité mesurées par le capteur DHT11 connecté à Arduino sur l’afficheur LCD I2C

Arduino 13300vues

La carte ESP32 et l’afficheur LCD I2C 1602

ESP32 11160vues

La carte Arduino UNO et l’afficheur LCD I2C 2X16

Arduino 10646vues

Allumer une LED par la carte ESP32

ESP32 10430vues

Construction des robots

Tutoriels plus commentés

Balance électronique avec Arduino UNO et module HX711

Arduino 118 commentaires

Construire un GPS commandé par Arduino

Arduino 106 commentaires

Premiers pas avec Micro:bit et MakeCode

Micro:bit 58 commentaires

Afficher la température et l’humidité mesurées par le capteur DHT11 connecté à Arduino sur l’afficheur LCD I2C

Arduino 32 commentaires

Détection et suivi d’un objet en mouvement à l’aide de l’Arduino et Webcam

Arduino 29 commentaires

Algorithme d’insertion d’une valeur dans un tableau trié

Plan de tutoriel

1- Principe de l'algorithme d’insertion d’une valeur dans un tableau trié

2- Algorithme d’insertion d’une valeur dans un tableau trié

3- Programme Python

Principe de l'algorithme d’insertion d’une valeur dans un tableau trié

Algorithme d’insertion d’une valeur dans un tableau trié

Algorithme du programme Principal

La fonction saisie_taille

La procédure remplir

La fonction saisie

La procédure insertion

Programme en Python

0 commentaire

laisser un commentaire

Annuler la réponse

Passion de robotique

Tutoriels récents

Atelier robotique

Tutoriels populaires

Construction des robots

Tutoriels plus commentés

Bras robotique

Categories

Maison intelligente

But de ce site web

Coordonnées

Articles populaires

Photos des articles