Algorithme : Tri de SHELL du tableau des entiers

Bac SC 30-08-26

15 0

Plan de tutoriel

1- Principe du tri de SHELL

2- Algorithme du tri de SHELL

3- Programme Python

Principe du tri de SHELL

Le tri de Shell est une amélioration du tri par insertion. Son principe consiste à comparer et à déplacer des éléments qui ne sont pas forcément voisins. Pour cela, on utilise une valeur appelée intervalle p, qui représente le nombre de positions séparant deux éléments comparés.

Au début de l'algorithme, on choisit un grand intervalle p. Les éléments séparés par cet intervalle sont comparés et déplacés afin de rapprocher progressivement les éléments de leur position correcte. Cela permet de déplacer rapidement les éléments qui sont très éloignés de leur place finale.

Ensuite, l'intervalle p est réduit progressivement. Dans cet algorithme, il est calculé à partir de la suite 1, 4, 13, 40, ..., puis réduit en le divisant par 3. Le tableau est donc trié plusieurs fois avec des intervalles de plus en plus petits.

À chaque intervalle, l'algorithme utilise un fonctionnement similaire au tri par insertion. L'élément e est mémorisé, puis les éléments plus grands situés à p positions avant sont décalés vers la droite. L'élément e est ensuite placé à la position où il doit être inséré.

Enfin, lorsque p = 1, l'algorithme effectue un dernier passage qui correspond à un tri par insertion classique. Comme les éléments sont déjà en grande partie ordonnés grâce aux passages précédents, ce dernier passage est beaucoup plus rapide. Le tableau est alors complètement trié dans l'ordre croissant.

Algorithme du tri de SHELL

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

- la fonction saisie

- la procédure remplir

- la procédure SHELL

Algorithme du programme Principal

Le programme principal permet d’exécuter les différentes étapes du programme dans l’ordre. Il commence par demander le nombre d’éléments du tableau, puis remplit le tableau avec les valeurs saisies par l’utilisateur. Ensuite, il appelle la procédure SHELL(t, n) pour trier les éléments du tableau dans l’ordre croissant. Enfin, il affiche le tableau après le tri.

Algorithme tri_shell
Debut 
     # Appeler la fonction saisie() pour obtenir
     # le nombre d'éléments du tableau.
     n <-- saisie()
     # Afficher un message avant le remplissage du tableau.
     Ecrire("***Remplissage du tableau***")
     # Appeler la fonction remplir() pour saisir
     # les n éléments du tableau.
     remplir(t, n)
     # Trier les n éléments du tableau dans l'ordre croissant
     # en utilisant l'algorithme du tri de Shell.
     SHELL(t, n)
     # Afficher un message après le tri.
     Ecrire("***Tableau trié***")
     # Afficher les n éléments du tableau après le tri.
     afficher(t, n) 
Fin

Algorithme tri_shell

Debut

# Appeler la fonction saisie() pour obtenir

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

n <-- saisie()

# Afficher un message avant le remplissage du tableau.

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

# Appeler la fonction remplir() pour saisir

# les n éléments du tableau.

remplir(t, n)

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

# en utilisant l'algorithme du tri de Shell.

SHELL(t, n)

# Afficher un message après le tri.

Ecrire("***Tableau trié***")

# Afficher les n éléments du tableau après le tri.

afficher(t, n)

Fin

Déclaration des objets

Objet	Type / Nature
n	entier
t	tableau des entiers

La fonction saisie

La fonction saisie() 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():entier
    # Demander à l'utilisateur de saisir le nombre d'éléments 
    # La valeur doit être comprise entre 2 et 14.
    Ecrire ("donner n entre 2 et 14")
    Lire(n)
    # Vérifier que n appartient à l'intervalle [2, 14] 
    # Tant que la valeur est incorrecte, on redemande la saisie.
    Tant que Non (2<=n<=14) faire
       Ecrire ("donner n entre 2 et 14")
       Lire(n)
    Fin tant que
    # Retourner la valeur correcte de n
    Retourner n 
Fin

Fonction saisie():entier

# Demander à l'utilisateur de saisir le nombre d'éléments

# La valeur doit être comprise entre 2 et 14.

Ecrire ("donner n entre 2 et 14")

Lire(n)

# Vérifier que n appartient à l'intervalle [2, 14]

# Tant que la valeur est incorrecte, on redemande la saisie.

Tant que Non (2<=n<=14) faire

Ecrire ("donner n entre 2 et 14")

Lire(n)

Fin tant que

# Retourner la valeur correcte de n

Retourner n

Fin

Déclaration des objets

Objet	Type / Nature
n	entier

La procédure remplir

La procédure remplir permet de remplir le tableau t avec n entiers saisis par l’utilisateur.

Procédure remplir(var t:tab; n:entier)
  # Parcourir les n premières cases du tableau
  Pour i de 0 à n-1 faire
      # Demander à l'utilisateur de saisir un élément 
      # et le placer dans la case t[i].
      Ecrire('Donner un élément du tableau')
      Lire(t[i])
  Finpour 
Fin

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

# Parcourir les n premières cases du tableau

Pour i de 0 à n-1 faire

# Demander à l'utilisateur de saisir un élément

# et le placer dans la case t[i].

Ecrire('Donner un élément du tableau')

Lire(t[i])

Finpour

Fin

Déclaration des objets

Objet	Type / Nature
binaire	chaîne des caractères

La procédure SHELL

La procédure Shell consiste à trier progressivement le tableau en utilisant des intervalles p de plus en plus petits. À chaque passage, les éléments séparés de p positions sont comparés et les éléments plus grands sont décalés vers la droite. L'intervalle est ensuite réduit jusqu'à p = 1, ce qui permet de terminer le tri dans l'ordre croissant.

Procédure SHELL(var t:tab;n:entier) :     
  # ==========================================================
  # Calcul du premier intervalle p
  # ==========================================================
  # Initialiser l'intervalle p à 0.
  p <-- 0
  # Calculer progressivement les intervalles selon la formule :
  # p = 3 * p + 1
  #
  # Cette formule produit la suite :
  # 1, 4, 13, 40, ...
  #
  # On cherche le plus grand intervalle adapté
  # à la taille n du tableau.
  Tant que (p < n-1) faire
      # Calculer l'intervalle suivant.
      p <-- 3*p+1 
  Fin tant que 
  # Réduction progressive de l'intervalle 
  # Réduire l'intervalle p progressivement. 
  # À chaque passage, p est divisé par 3. 
  # Exemple :  p = 13 → p = 4 → p = 1 
  # Lorsque p = 1, on réalise le dernier passage 
  #avec un principe similaire au tri par insertion. 
  Tant que (p > 1) faire
    # Passer à l'intervalle précédent.
    p <-- p div 3
    # ========================================================
    # Parcours du tableau
    # ========================================================
    # Parcourir les éléments du tableau à partir
    #de la position p jusqu'à la position n-1.
    Pour i de p à n-1 faire
      # j représente la position actuelle de l'élément
      # que l'on cherche à placer.
      j <-- i
      // Mémoriser l'élément à insérer.
      e <-- t[i] 
      # Recherche de la bonne position de e 
      # Comparer e avec l'élément situé p positions 
      # avant la position j. 
      # Tant que l'élément précédent est plus grand que e 
      # et qu'il existe une position située p cases avant, 
      # on décale cet élément vers la droite. 
      Tant que (j >= p) et (t[j-p] > e) faire
          # Décaler l'élément t[j-p] vers la droite.
          t[j] <-- t[j-p]
          # Reculer de p positions pour continuer
          # la recherche de la bonne position.
          j <-- j-p
      Fin tant que
      # ======================================================
      # Insertion de e
      # ======================================================
      # Lorsque la bonne position est trouvée,
      # placer l'élément e dans cette position.
      t[j] <-- e
    Fin pour
  Fin tant que
Fin

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

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

# Calcul du premier intervalle p

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

# Initialiser l'intervalle p à 0.

p <-- 0

# Calculer progressivement les intervalles selon la formule :

# p = 3 * p + 1

# Cette formule produit la suite :

# 1, 4, 13, 40, ...

# On cherche le plus grand intervalle adapté

# à la taille n du tableau.

Tant que (p < n-1) faire

# Calculer l'intervalle suivant.

p <-- 3*p+1

Fin tant que

# Réduction progressive de l'intervalle

# Réduire l'intervalle p progressivement.

# À chaque passage, p est divisé par 3.

# Exemple : p = 13 → p = 4 → p = 1

# Lorsque p = 1, on réalise le dernier passage

#avec un principe similaire au tri par insertion.

Tant que (p > 1) faire

# Passer à l'intervalle précédent.

p <-- p div 3

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

# Parcours du tableau

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

# Parcourir les éléments du tableau à partir

#de la position p jusqu'à la position n-1.

Pour i de p à n-1 faire

# j représente la position actuelle de l'élément

# que l'on cherche à placer.

j <-- i

// Mémoriser l'élément à insérer.

e <-- t[i]

# Recherche de la bonne position de e

# Comparer e avec l'élément situé p positions

# avant la position j.

# Tant que l'élément précédent est plus grand que e

# et qu'il existe une position située p cases avant,

# on décale cet élément vers la droite.

Tant que (j >= p) et (t[j-p] > e) faire

# Décaler l'élément t[j-p] vers la droite.

t[j] <-- t[j-p]

# Reculer de p positions pour continuer

# la recherche de la bonne position.

j <-- j-p

Fin tant que

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

# Insertion de e

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

# Lorsque la bonne position est trouvée,

# placer l'élément e dans cette position.

t[j] <-- e

Fin pour

Fin tant que

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
j	entier
e	entier
p	entier

La procédure afficher

La procédure afficher(t, n) permet d’afficher les n premiers éléments du tableau t.

Elle parcourt les cases du tableau à l’aide de la boucle for, de l’indice 0 jusqu’à n-1. À chaque passage, l’instruction print(t[i]) affiche la valeur contenue dans la case t[i].

Procédure afficher(t:tab; n:entier)
  # Parcourir les n premières cases du tableau
  Pour i de 0 à n-1 faire 
      # Afficher chaque élément du tableau
      Ecrire(t[i]) 
  Finpour 
Fin

Procédure afficher(t:tab; n:entier)

# Parcourir les n premières cases du tableau

Pour i de 0 à n-1 faire

# Afficher chaque élément du tableau

Ecrire(t[i])

Finpour

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.
# Seules les n premières cases seront utilisées.
t = array([int()] * 100)


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

def saisie():

    # Demander à l'utilisateur de saisir le nombre
    # d'éléments du tableau.
    n = int(input("donner n entre 2 et 14: "))

    # Vérifier que n est compris entre 2 et 14.
    # Tant que n n'est pas valide, demander une nouvelle saisie.
    while not (2 <= n <= 14):

        # Demander à nouveau la valeur de n.
        n = int(input("donner n entre 2 et 14: "))

    # Retourner la valeur correcte de n.
    return n


# ==========================================================
# Fonction de remplissage du tableau
# ==========================================================

def remplir(t, n):

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

        # Demander à l'utilisateur de saisir un élément.
        # La valeur saisie est convertie en entier
        # puis stockée dans la case t[i].
        t[i] = int(input("donner un element du tableau : "))


# ==========================================================
# Procédure de tri de Shell
# ==========================================================

def SHELL(t, n):

    # ------------------------------------------------------
    # Calcul du premier intervalle
    # ------------------------------------------------------

    # Initialiser l'intervalle p à 1.
    p = 1

    # Calculer les intervalles selon la formule :
    # p = 3 * p + 1
    #
    # Cette formule produit la suite :
    # 1, 4, 13, 40, ...
    #
    # On cherche le plus grand intervalle inférieur
    # ou égal à n - 1.
    while 3 * p + 1 < n:
        p = 3 * p + 1


    # ------------------------------------------------------
    # Réduction progressive de l'intervalle
    # ------------------------------------------------------

    # Réduire progressivement l'intervalle p.
    # À chaque passage, p est divisé par 3.
    #
    # Exemple :
    # p = 13  →  p = 4  →  p = 1
    while p > 1:

        # Passer à l'intervalle précédent.
        p = p // 3

        # Si p devient 0, arrêter le tri.
        if p == 0:
            break


        # --------------------------------------------------
        # Parcours des éléments du tableau
        # --------------------------------------------------

        # Parcourir le tableau à partir de la position p.
        for i in range(p, n):

            # j représente la position actuelle
            # de l'élément à insérer.
            j = i

            # Mémoriser l'élément à insérer.
            e = t[i]


            # --------------------------------------------------
            # Recherche de la bonne position
            # --------------------------------------------------

            # Comparer e avec l'élément situé p positions
            # avant la position j.
            #
            # Tant que l'élément précédent est plus grand
            # que e, le décaler vers la droite.
            while (j >= p) and (t[j - p] > e):

                # Décaler l'élément situé à j-p
                # vers la position j.
                t[j] = t[j - p]

                # Reculer de p positions.
                j = j - p


            # --------------------------------------------------
            # Insertion de l'élément
            # --------------------------------------------------

            # Lorsque la bonne position est trouvée,
            # placer l'élément e dans la case t[j].
            t[j] = e


# ==========================================================
# 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() pour obtenir
# le nombre d'éléments du tableau.
n = saisie()


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


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


# Trier les n éléments du tableau dans l'ordre croissant
# en utilisant l'algorithme du tri de Shell.
SHELL(t, n)


# Afficher un message après le tri.
print("***Tableau trié***")


# Afficher les n éléments du tableau après le tri.
afficher(t, n)

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

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

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

# 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.

# Seules les n premières cases seront utilisées.

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

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

# Fonction de saisie de la taille du tableau

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

def saisie():

# Demander à l'utilisateur de saisir le nombre

# d'éléments du tableau.

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

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

# Tant que n n'est pas valide, demander une nouvelle saisie.

while not (2 <= n <= 14):

# Demander à nouveau la valeur de n.

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

# Retourner la valeur correcte de n.

return n

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

# Fonction de remplissage du tableau

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

def remplir(t, n):

# Parcourir les n premières cases du tableau.

for i in range(n):

# Demander à l'utilisateur de saisir un élément.

# La valeur saisie est convertie en entier

# puis stockée dans la case t[i].

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

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

# Procédure de tri de Shell

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

def SHELL(t, n):

# ------------------------------------------------------

# Calcul du premier intervalle

# ------------------------------------------------------

# Initialiser l'intervalle p à 1.

p = 1

# Calculer les intervalles selon la formule :

# p = 3 * p + 1

# Cette formule produit la suite :

# 1, 4, 13, 40, ...

# On cherche le plus grand intervalle inférieur

# ou égal à n - 1.

while 3 * p + 1 < n:

p = 3 * p + 1

# ------------------------------------------------------

# Réduction progressive de l'intervalle

# ------------------------------------------------------

# Réduire progressivement l'intervalle p.

# À chaque passage, p est divisé par 3.

# Exemple :

# p = 13 → p = 4 → p = 1

while p > 1:

# Passer à l'intervalle précédent.

p = p // 3

# Si p devient 0, arrêter le tri.

if p == 0:

break

# --------------------------------------------------

# Parcours des éléments du tableau

# --------------------------------------------------

# Parcourir le tableau à partir de la position p.

for i in range(p, n):

# j représente la position actuelle

# de l'élément à insérer.

j = i

# Mémoriser l'élément à insérer.

e = t[i]

# --------------------------------------------------

# Recherche de la bonne position

# --------------------------------------------------

# Comparer e avec l'élément situé p positions

# avant la position j.

# Tant que l'élément précédent est plus grand

# que e, le décaler vers la droite.

while (j >= p) and (t[j - p] > e):

# Décaler l'élément situé à j-p

# vers la position j.

t[j] = t[j - p]

# Reculer de p positions.

j = j - p

# --------------------------------------------------

# Insertion de l'élément

# --------------------------------------------------

# Lorsque la bonne position est trouvée,

# placer l'élément e dans la case t[j].

t[j] = e

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

# 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() pour obtenir

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

n = saisie()

# Afficher un message avant le remplissage du tableau.

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

# Appeler la fonction remplir() pour saisir

# les n éléments du tableau.

remplir(t, n)

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

# en utilisant l'algorithme du tri de Shell.

SHELL(t, n)

# Afficher un message après le tri.

print("***Tableau trié***")

# Afficher les n éléments du tableau après le tri.

afficher(t, n)

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 : 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

Algorithme : Tri par sélection du tableau des entiers

Bac SC 19-08-26

Apprendre à programmer un robot Maqueen avec Micro:bit

Micro:bit 31-07-26

Atelier robotique

Tutoriels populaires

Présentation de la carte ESP32

ESP32 13802vues

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

Arduino 13265vues

La carte ESP32 et l’afficheur LCD I2C 1602

ESP32 11137vues

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

Arduino 10617vues

Allumer une LED par la carte ESP32

ESP32 10407vues

Construction des robots

Tutoriels plus commentés

Balance électronique avec Arduino UNO et module HX711

Arduino 117 commentaires

Construire un GPS commandé par Arduino

Arduino 105 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 : Tri de SHELL du tableau des entiers

Plan de tutoriel

1- Principe du tri de SHELL

2- Algorithme du tri de SHELL

3- Programme Python

Principe du tri de SHELL

Algorithme du tri de SHELL

Algorithme du programme Principal

La fonction saisie

La procédure remplir

La procédure SHELL

La procédure afficher

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