Algorithme : Tri par sélection du tableau des entiers

Bac SC 19-08-26

561 2

Plan de tutoriel

1- Principe du tri par sélection

2- Algorithme du tri par sélection

3- Programme Python

Principe du tri par sélection

Le tri par sélection est un algorithme permettant de trier les éléments d’un tableau, généralement dans l’ordre croissant. Son principe consiste à parcourir le tableau et à rechercher, à chaque étape, le plus petit élément dans la partie qui n’est pas encore triée.

Une fois le plus petit élément trouvé, on l’échange avec le premier élément de la partie non triée. Cet élément est alors placé définitivement à sa position correcte. Le même processus est ensuite répété pour les éléments restants du tableau.

Par exemple, pour le tableau [64, 25, 12, 22, 11], le premier passage consiste à rechercher le plus petit élément, qui est 11, puis à l’échanger avec 64. Le tableau devient alors [11, 25, 12, 22, 64]. Au passage suivant, on recherche le minimum parmi [25, 12, 22, 64], qui est 12, et on l’échange avec 25.

Le processus continue jusqu’à ce que tous les éléments soient placés dans leur position définitive. Le tableau obtenu est alors [11, 12, 22, 25, 64]. Ainsi, à chaque passage, la partie triée du tableau augmente d’un élément tandis que la partie non triée diminue.

Algorithme du tri par sélection

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

- la fonction saisie

- la procédure remplir

- la procédure selection

Algorithme du programme Principal

L’algorithme principal tri_selection constitue le point de départ du programme. Il organise les différentes étapes nécessaires pour réaliser le tri par sélection d’un tableau d’entiers.

Au début, l’instruction n ← saisie() permet de saisir le nombre d’éléments du tableau. Ensuite, la procédure remplir(t,n) permet de remplir le tableau t avec les n entiers saisis par l’utilisateur. La procédure selection(t,n) applique ensuite l’algorithme du tri par sélection afin de classer les éléments du tableau dans l’ordre croissant. Enfin, l’instruction afficher(t,n) permet d’afficher le tableau après le tri.

Ainsi, l’algorithme principal assure l’enchaînement des différentes opérations : saisie du nombre d’éléments, remplissage du tableau, tri des éléments et affichage du résultat.

Algorithme tri_selection
Debut 
     # Saisir la taille du tableau 
     n <-- saisie() 
     # Afficher un message avant le remplissage 
     Ecrire("***Remplissage du tableau***") 
     # Remplir le tableau avec les valeurs saisies 
     remplir(t, n) 
     # Trier le tableau dans l'ordre croissant 
     # en utilisant la méthode du tri par sélection. 
     selection(t, n) 
     # Afficher un message indiquant que le tableau est trié 
     Ecrire("***Tableau trié***") 
     # Afficher les éléments du tableau trié 
     afficher(t, n) 
Fin

Algorithme tri_selection

Debut

# Saisir la taille du tableau

n <-- saisie()

# Afficher un message avant le remplissage

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

# Remplir le tableau avec les valeurs saisies

remplir(t, n)

# Trier le tableau dans l'ordre croissant

# en utilisant la méthode du tri par sélection.

selection(t, n)

# Afficher un message indiquant que le tableau est trié

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

# Afficher les éléments du tableau 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
i	entier

La procédure selection

La procédure selection permet de trier le tableau t dans l’ordre croissant en utilisant la méthode du tri par sélection.

Procédure selection(var t:tab;n:entier)
  # Parcourir le tableau jusqu'à l'avant-dernière position. 
  # À chaque étape, on cherche le plus petit élément 
  # dans la partie non encore triée.
  Pour i de 0 à n-2 faire
  # On considère au départ que l'élément situé à la position i
        # est le plus petit.
        min <-- i
        # Rechercher le plus petit élément dans la partie
        # du tableau située après la position i.
        Pour j de i+1 à n-1 faire
            # Comparer l'élément considéré comme minimum
            # avec l'élément situé à la position j.
            Si t[min] > t[j] alors
                # Si t[j] est plus petit, mémoriser sa position.
                min <-- j
            Fin si
        Fin pour
        # Si le minimum n'est pas déjà à la position i,
        # effectuer un échange entre les deux éléments.
        Si i != min alors
            temp <-- t[i]       # Sauvegarder temporairement t[i]
            t[i] <-- t[min]     # Placer le minimum à la position i
            t[min] <-- temp     # Placer l'ancien t[i] à la position du minimum
        Fin si
  Fin pour
Fin

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

# Parcourir le tableau jusqu'à l'avant-dernière position.

# À chaque étape, on cherche le plus petit élément

# dans la partie non encore triée.

Pour i de 0 à n-2 faire

# On considère au départ que l'élément situé à la position i

# est le plus petit.

min <-- i

# Rechercher le plus petit élément dans la partie

# du tableau située après la position i.

Pour j de i+1 à n-1 faire

# Comparer l'élément considéré comme minimum

# avec l'élément situé à la position j.

Si t[min] > t[j] alors

# Si t[j] est plus petit, mémoriser sa position.

min <-- j

Fin si

Fin pour

# Si le minimum n'est pas déjà à la position i,

# effectuer un échange entre les deux éléments.

Si i != min alors

temp <-- t[i] # Sauvegarder temporairement t[i]

t[i] <-- t[min] # Placer le minimum à la position i

t[min] <-- temp # Placer l'ancien t[i] à la position du minimum

Fin si

Fin pour

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
j	entier
min	entier
temp	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

Solution en Python

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

from numpy import array          # Permet de créer et manipuler des tableaux


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

# Création d'un tableau de 100 éléments initialisés à 0
# Le tableau permettra de stocker les valeurs saisies par l'utilisateur.
t = array([int()] * 100)


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

def saisie():
    # Demander à l'utilisateur de saisir le nombre d'éléments
    # La valeur doit être comprise entre 2 et 14.
    n = int(input("donner n entre 2 et 14: "))

    # Vérifier que n appartient à l'intervalle [2, 14]
    # Tant que la valeur est incorrecte, on redemande la saisie.
    while not (2 <= n <= 14):
        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
        # et le placer dans la case t[i].
        t[i] = int(input("donner un element du tableau : "))


# ==========================================================
# Fonction de tri par sélection
# ==========================================================

def selection(t, n):
    # Parcourir le tableau jusqu'à l'avant-dernière position.
    # À chaque étape, on cherche le plus petit élément
    # dans la partie non encore triée.
    for i in range(n - 1):

        # On considère au départ que l'élément situé à la position i
        # est le plus petit.
        min = i

        # Rechercher le plus petit élément dans la partie
        # du tableau située après la position i.
        for j in range(i + 1, n):

            # Comparer l'élément considéré comme minimum
            # avec l'élément situé à la position j.
            if t[min] > t[j]:
                # Si t[j] est plus petit, mémoriser sa position.
                min = j

        # Si le minimum n'est pas déjà à la position i,
        # effectuer un échange entre les deux éléments.
        if i != min:
            temp = t[i]       # Sauvegarder temporairement t[i]
            t[i] = t[min]     # Placer le minimum à la position i
            t[min] = temp     # Placer l'ancien t[i] à la position du minimum


# ==========================================================
# Fonction d'affichage du tableau
# ==========================================================

def afficher(t, n):
    # Parcourir les n premières cases du tableau
    for i in range(n):
        # Afficher chaque élément du tableau
        print(t[i])


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

# Saisir la taille du tableau
n = saisie()

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

# Remplir le tableau avec les valeurs saisies
remplir(t, n)

# Trier le tableau dans l'ordre croissant
# en utilisant la méthode du tri par sélection.
selection(t, n)

# Afficher un message indiquant que le tableau est trié
print("***Tableau trié***")

# Afficher les éléments du tableau trié
afficher(t, n)

100

101

102

103

104

105

106

107

108

109

110

111

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

# Importation de la bibliothèque NumPy

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

from numpy import array # Permet de créer et manipuler des tableaux

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

# Création du tableau

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

# Création d'un tableau de 100 éléments initialisés à 0

# Le tableau permettra de stocker les valeurs saisies par l'utilisateur.

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

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

# Fonction de saisie de la taille du tableau

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

def saisie():

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

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

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

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

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

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

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

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

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

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

# Fonction de tri par sélection

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

def selection(t, n):

# Parcourir le tableau jusqu'à l'avant-dernière position.

# À chaque étape, on cherche le plus petit élément

# dans la partie non encore triée.

for i in range(n - 1):

# On considère au départ que l'élément situé à la position i

# est le plus petit.

min = i

# Rechercher le plus petit élément dans la partie

# du tableau située après la position i.

for j in range(i + 1, n):

# Comparer l'élément considéré comme minimum

# avec l'élément situé à la position j.

if t[min] > t[j]:

# Si t[j] est plus petit, mémoriser sa position.

min = j

# Si le minimum n'est pas déjà à la position i,

# effectuer un échange entre les deux éléments.

if i != min:

temp = t[i] # Sauvegarder temporairement t[i]

t[i] = t[min] # Placer le minimum à la position i

t[min] = temp # Placer l'ancien t[i] à la position du minimum

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

# Fonction d'affichage du tableau

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

def afficher(t, n):

# Parcourir les n premières cases du tableau

for i in range(n):

# Afficher chaque élément du tableau

print(t[i])

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

# Programme principal

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

# Saisir la taille du tableau

n = saisie()

# Afficher un message avant le remplissage

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

# Remplir le tableau avec les valeurs saisies

remplir(t, n)

# Trier le tableau dans l'ordre croissant

# en utilisant la méthode du tri par sélection.

selection(t, n)

# Afficher un message indiquant que le tableau est trié

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

# Afficher les éléments du tableau trié

afficher(t, n)

Exécution du programme

2 commentaires

big penis pill 24-08-2626

Thank you for another great post. Where else may just anyone get that kind of info in such an ideal method of writing? I have a presentation subsequent week, and I am on the search for such information.

titan gell penis 24-08-2626

Thanks , I have just been looking for info about this subject for ages and yours is the greatest I have discovered till now. But, what about the bottom line? Are you sure concerning the supply?