Tri par sélection

Version imprimable

Tri par sélection

Bonjour tout le monde,
Je débute dans l'algorithmique...j'ai compris le tri par sélection mais je n'ai pas compris pourquoi ces deux algorithmes fontionnent parfaitement bien sur Algobox :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  VARIABLES
 i EST_DU_TYPE NOMBRE
 n EST_DU_TYPE NOMBRE
 tmp EST_DU_TYPE NOMBRE
 tab EST_DU_TYPE LISTE
 mi EST_DU_TYPE NOMBRE
 j EST_DU_TYPE NOMBRE
 DEBUT_ALGORITHME
 LIRE n
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   LIRE tab[i]
 FIN_POUR
 POUR i ALLANT_DE 0 A n-2
   DEBUT_POUR
   mi PREND_LA_VALEUR i
   POUR j ALLANT_DE i+1 A n-1
     DEBUT_POUR
     SI (tab[j]<tab[mi]) ALORS
       DEBUT_SI
       tmp PREND_LA_VALEUR tab[mi]
       tab[mi] PREND_LA_VALEUR tab[j]
       tab[j] PREND_LA_VALEUR tmp
     FIN_SI
   FIN_POUR
 FIN_POUR
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   AFFICHER tab[i]
 FIN_POUR
 FIN_ALGORITHME

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
  VARIABLES
 i EST_DU_TYPE NOMBRE
 n EST_DU_TYPE NOMBRE
 tmp EST_DU_TYPE NOMBRE
 tab EST_DU_TYPE LISTE
 mi EST_DU_TYPE NOMBRE
 j EST_DU_TYPE NOMBRE
 DEBUT_ALGORITHME
 LIRE n
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   LIRE tab[i]
 FIN_POUR
 POUR i ALLANT_DE 0 A n-2
   DEBUT_POUR
   POUR j ALLANT_DE i+1 A n-1
     DEBUT_POUR
     SI (tab[j]<tab[i]) ALORS
       DEBUT_SI
       tmp PREND_LA_VALEUR tab[i]
       tab[i] PREND_LA_VALEUR tab[j]
       tab[j] PREND_LA_VALEUR tmp
     FIN_SI
   FIN_POUR
 FIN_POUR
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   AFFICHER tab[i]
 FIN_POUR
 FIN_ALGORITHME

Ma question c'est pourquoi utiliser une variable mi pour stocker la valeur de i pour ensuite comparer tab[j] et tab[mi]...alors que le premier algo marche tout aussi bien...autrement dit qu'est-ce qui m'a échappé?
Merci d'avance.

10/06/2017, 09h27
tbc92

Si on prend ton algorithme, et qu'on ajoute une nouvelle variable k, et qu'on fait vers le milieu k = i* j, le nouvel algorithme continuera de fonctionner. La ligne ajoutée ne sert à rien. Dans ton cas, c'est pareil, A partir d'un algorithme qui fonctionne, on peut faire des modifications mineures, et l'algorithme continue de fonctionner.
Mais l'algorithme perd en élégance et en lisibilité.

L'objectif est bien évidemment d'avoir non seulement un algorithme qui donne le résultat voulu, mais aussi un algorithme élégant, sans instructions superflues.
10/06/2017, 11h29
mobiclick

Bonjour le forum
Bonjour tbc92
Merci pour la réponse
Justement, je le pense aussi ...du coup je ne comprends pas pourquoi c'est le premier algorithme qui est repris dans tous les tutoriels et les cours que j'ai consultés sur le net....c'est pas normal. ..le deuxième algorithme (très simpliste ) c'est celui que j'ai fait pour donner la solution d'un exercice. ...y a quelque chose qui m'échappe forcément ! J'ai du faire une erreur.

Salut,

L'algorithme montré n'est pas celui du "tri par sélection", mais celui du "tri à bulles". Le tri par sélection c'est

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
VARIABLES
 i EST_DU_TYPE NOMBRE
 n EST_DU_TYPE NOMBRE
 tmp EST_DU_TYPE NOMBRE
 tab EST_DU_TYPE LISTE
 mi EST_DU_TYPE NOMBRE
 j EST_DU_TYPE NOMBRE
 DEBUT_ALGORITHME
 LIRE n
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   LIRE tab[i]
 FIN_POUR
 POUR i ALLANT_DE 0 A n-2
   DEBUT_POUR
   mi PREND_LA_VALEUR i
   POUR j ALLANT_DE i+1 A n-1
     DEBUT_POUR
     SI (tab[j]<tab[mi]) ALORS
       DEBUT_SI
       mi PREND_LA_VALEUR j
     FIN_SI
   FIN_POUR
   SI (i!=mi) ALORS
       DEBUT_SI
       tmp PREND_LA_VALEUR tab[mi]
       tab[mi] PREND_LA_VALEUR tab[i]
       tab[i] PREND_LA_VALEUR tmp
   FIN_SI
 FIN_POUR
 POUR i ALLANT_DE 0 A n-1
   DEBUT_POUR
   AFFICHER tab[i]
 FIN_POUR
 FIN_ALGORITHME

Et dans cet algorithme, l'utilisation de mi est indispensable.

11/06/2017, 00h40
mobiclick

Bonjour le forum,
Merci pour vos explications
Bonne continuation à tous