Méthode du tri par séléction
Énoncé

Écrire une marche à suivre qui permet de trier un tableau T
à N éléments en ordre décroissant. (N, T sont des données)

I) Préanalyse :

Données : 
..............- Le nombre d'éléments de T  (N=6);
..............- Un tableau T à N éléments de types entiers ;
T 17 12 50 10 33 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Résultat :

Un tableau trié

T 50 33 17 15 12 10 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10

Les étapes de résolution :

Etape 1 :

a) On se pointe à la 1ère case du tableau et on parcourt la totalité de T pour repérer l'indice

du maximum :

                 
T 17 12 50 10 33 15 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10

La recherche de la première position du maximum donne ppm = 3

b) On compare ce maximum T[posmax] avec T[1]. S'ils ne sont pas dans le bon ordre

on les permute :

Ici T[posmax]=50 > T[1] = 17 d'où permut ( T[posmax] , T[1] )

d'où le résultat suivant :

                   
T 50 12 17 10 33 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Le sous tableau de T allant de 2 à n est à priori non trié, On applique a) et b)

et ainsi de suite jusqu'à l'avant dernière (n-1) .

Etape 2 :

                 
T 50 12 17 10 33 15 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10

La recherche de la première position du maximum donne ppm = 5

T[posmax]=33 > T[2] = 12 d'où PERMUT ( T[ppm] , T[2] )

d'où le résultat suivant :

                   
T 50 33 17 10 12 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Etape 3 :

                   
T 50 12 17 10 12 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

La recherche de la première position du maximum donne ppm = 3

T[posmax]=17 > T[3] = 17 est Faux d'où pas de permutation

d'où le résultat suivant :

                   
T 50 33 17 10 12 15 ? ? ? ?
1
1
2
3
4
5
N=6
7
8
9
NMAX=10

Etape 4 :

                 
T 50 12 17 10 12 15 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

La recherche de la première position du maximum donne ppm = 6

T[posmax]=15 > T[4] = 10 d'où PERMUT ( T[posmax] , T[4] )

d'où le résultat suivant :

                   
T 50 33 17 15 12 10 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

Etape 5 :

                   
T 50 12 17 15 12 10 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

La recherche de la première position du maximum donne ppm = 5

T[posmax]=12 > T[5] = 12 est Faux d'où il n'aura pas de permutation

d'où le résultat suivant :

                     
T 50 33 17 15 12 10 ? ? ? ?
1
2
3
4
5
N=6
7
8
9
NMAX=10

.

..............................................................................................Les noms des modules (sous-programmes)

Saisir (Lire) le nombre d'éléments de T .................................................... Lecture(N)

Remplir le tableau T par N éléments ........................................................ Remplir(N,T)

Rechercher la première position du maximum............................................Premposmax(N,T)

Permuter le contenu de deux variables..................................................... Permut(A,B)

Afficher le tableau T après insertion..........................................................Affiche(N,T)

II) Analyses & Algorithmes :

1) Analyse du programme principal

Nom : Tri_methode_Par_selection
S.
LDE
O.U.

4

1

3

2

5

Résultat : Affiche ( N , Tr )

N = Lecture( N )

Tr= Tri_selection ( N , Ti)

Ti = Remplir ( N , Ti )

Fin Tri_methode_Par_selection

N, Tr, Ti

Affiche

Lecture

Tri_selection

Remplir

Tableau de déclaration des objets :

O.U.
Nature/Type
Rôle
N
var/Entier
 Le nombre d'éléments du tableau T
Ti
var/Tab
 Tableau des valeurs à l'état initial
Tr
var/Tab
 Tableau trié
Lecture
Procédure
 Lecture de N
Remplir
Procédure
 Remplit le tableau T par des valeurs
Tri_selection
Procédure
 Trie le tableau T en ordre décroissant
Affiche
Procédure
 Affiche les valeurs du tableau après le tri

Nouveau Type ................Tab = Tableau [1..NMax] d'entier

NMax est une constante égale à 10

1)Algorithme du programme principal :

0- Début Tri_methode_Par_selection
1- Lecture( N )
2- Remplir ( N , T )
3- Tri_selection ( N , P )
4- Affiche ( N , T )
5- Fin Tri_methode_Par_selection

2) Analyse de la procédure Lecture

DEF PROC Lecture (Var N : Entier)
S.
LDE
O.U.

 

 Résultat : N
1
 N= [ ] Répeter

N=donnée

Jusqu'à N dans [ 1 .. Nmax ]
2
 Fin Lecture 
Algorithme de la procédure Lecture :
0- DEF PROC Lecture (Var N : Entier)
1- Répeter
 
..........Lire( N )
  Jusqu'à N dans [ 1 .. Nmax ]
2- Fin Lecture

3) Analyse de la procédure Remplir

DEF PROC Remplir ( N : Entier ; Var T: Tab )
S.
LDE
O.U.

 

 Résultat : T

 

I

 
1
 T= [ ] Pour I de 1 à N Répéter

...................T[I]=donnée

..........Fin Pour

I = Compteur
2

Fin Remplir

Tableau de déclaration des objets :

O.U.
Nature/Type
Rôle
I
var/Entier
 Compteur 
Algorithme de la procédure Remplir :
0- DEF PROC Remplir ( N : Entier ; Var T : Tab )
1- Pour I de 1 a N Répéter
 
.......... Lire( T[I] )
 

Fin Pour
2- Fin Remplir

4) Analyse de la procédure Tri_selection

DEF PROC Tri_selection ( N : Entier ; Var T : Tab )
S.
LDE
O.U.

 

 Résultat : T

I

ppm

Premposmax

 

Permut
1
 T= [ ] Pour I de 1 à N Répéter
  ..........[ppm<-- Premposmax ( I, N, T )]
..................Si T[ppm] <> T[I]

...........................Alors
  ....................................Permut ( T[ppm], T[I] )
  ..................FinSi

..........Fin Pour

I = Compteur
2

Fin Tri_selection

Tableau de déclaration des objets :

O.U.
Nature/Type
Rôle
I
var/Entier
 Compteur
ppm
var/Entier
 Contiendra la première position du maximum
Permut
Procédure
 Permute le contenu de deux variables
premposmax
Fonction / Entier
 Renvoie la première position du maximum 
Algorithme de la Procédure Tri_selection :
0-

DEF PROC Tri_selection ( N : Entier ; Var T : Tab )
1
 Pour I de 1 à N Répéter
.......ppm<-- Premposmax ( I, N, T )
..................Si T[ppm] <> T[I]

...........................Alors
....................................Permut ( T[ppm], T[I] )
..................FinSi

..........Fin Pour
2

Fin Tri_selection

5) Analyse de la Fonction premposmax :

DEF FN Premposmax ( D , F : Entier ; T : Tab ) : Entier
S.
LDE
O.U.

 

 Résultat : premposmax

posmax

J
2

premposmax <-- posmax

1
 [posmax <-- D] Pour J de D+1 à F Répéter
...........................[ ] Si T [posmax] < T [J]
.....................................Alors
............................................posmax <-- J
................................FinSi
<