Niveau Licence Maths 1e ann

Algo Tri par selection du minimum et du maximum

Posté par
mankathada 18-02-17 à 14:40

Bonjour, comment ça va ?

Etant absent pendant deux semaines, je suis bloqué aux exercices d'algo que j'ai sur mes TD, je vous montre l'énoncé :

Ecrire le sous programme qui permet de sélectionner le plus petit élément du vecteur et le plus grand ( en parallèle ) et à les échanger respectivement avec le premier et le dernier élément puis à recommencer avec le sous-vecteur ayant 2 éléments de moins, jusqu'à n'avoir plus qu'à considérer un vecteur d'au plus 2 éléments. Pour la taille maximale du tableau on dira qu'elle vaudra 50.

Au fait l'idée, ce serait de considérer la première case comme le minimum et la dernière case comme le maximum, et le but ce serait à mon avis de comparer la première case avec les autres jusqu'à la case considérée comme le max pour la recherche du min, et idem pour le max.

Au fur et à mesure le nombre de cases à comparer diminueront, et on aura à la fin que deux cases à comparer.

Mais j'ai du mal à l'exprimer en algorithme.

Merci pour votre aide et au fait ne vous souciez pas de la syntaxe que vous utilisez pour écrire les algo en pseudo-code, je saurais m'y retrouver

Posté par re : Algo Tri par selection du minimum et du maximum 18-02-17 à 15:08

bonjour,

voici une proposition à valider (je considère que les éléments sont des nombres contenus dans le tableau TAB):

TAB(50)
A, B sont des entiers    ( A = borne 1,  B = borne 2)

tant que (B-A)  > 0

min = TAB(A), max = TAB(A), Imin = A, Imax = A

Pour I = A+1  to B
  si TAB(i)< min, alors     min = TAB(i), Imin = i
  si TAB(i) > max, alors    max = TAB(i), Imax = i
fin pour

/  ici on a trouvé le min et le max. Il faut les échanger  /
z = TAB(A)
TAB(A) = TAB(Imin)
TAB(Imin)=Z

z = TAB(B)
TAB(B) = TAB(Imax)
TAB(Imax)=Z

A = A+1
B=B-1
fin tant que

afficher tous les éléments de TAB  (qui doivent etre triés !!?? ).
fin prog.

Qu'en dis tu ?

Posté par re : Algo Tri par selection du minimum et du maximum 18-02-17 à 15:13

Si j'ai bien compris tu l'as fait en deux étapes, d'abord on détecte le min et le max, et aprés la deuxième étape on permute le min et le max.

Franchement il est très bien ton algo je valide

Merci beaucoup

Posté par re : Algo Tri par selection du minimum et du maximum 18-02-17 à 15:36

ce ne sont pas vraiment deux étapes, car elles sont contenues dans la boucle tant que.
mais oui, d'abord, une boucle POUR pour trouver où sont placés le min et le max,
puis, on les échange.

Fais attention, je l'ai testé avec une dimension réduite, et les deux derniers élements (ceux du milieu du tableau) ne sont pas ordonnés correctement.... (ça dépend du tableau que tu donnes au départ).
il faut ajouter un petit truc à la fin pour rectifier ce cas là..
A tester aussi avec des valeurs variées (moi, j'ai testé uniquement avec tous les éléments différents).
Bonne journée