Algorithme Tri par sélection

**Nonimamie** · 30/10/2017, 18h08

Bonjour,

Je suis en Terminale S et j'ai un algorithme sur le tri par sélection ou par extraction à compléter, puis à traduire en langage Python. J'ai essayé plusieurs choses mais je n'arrive pas à remplir les blancs.

Le but de cet algorithme est de générer 20 nombres aléatoires entre 1 et 20 de les trier et de visualiser cette liste tout au long du processus.
Voici l'algorithme à compléter (les blancs sont représentés par zzzzzzzzz) :

Variables : I, A, J, K : entiers L₁, L₂ : listes
Entrées et initialisation :
pour I de 1 à 20 faire
zzzzzzzzz => L₁ (I)
fin
Traitement et sorties :
pour I de 1 à 19 faire
I => K
pour J de I+1 à 20 faire
si zzzzzzzzz < L₁ (K) alors
J => K
fin
L₁ (I) => zzzzzzzzz
L₁ (K) => zzzzzzzzz on échange L1 (I) avec L1 (K)
A => L₁ (K)
I => K
fin
zzzzzzzzz
fin

J'espère que vous pourrez m'aider.
Merci d'avance,
Noé.

**Jack** · 30/10/2017, 20h05

Indente le code parce que c'est illisible ainsi présenté (utilise les balises code).

Essaie également de préciser ce que fait cette ligne par exemple, c'est pas évident: "L₁ (I) =>"

**Nonimamie** · 01/11/2017, 08h19

Merci pour votre réponse mais je ne comprends réellement pas ce qu'il faut ajouter dans les blancs. C'est la première année que je fais du codage, j'ai réussi le reste de l'exercice mais je bloque à cette question. Pourriez-vous m'aider davantage ?

**Jack** · 01/11/2017, 11h14

Ah, c'est à compléter, je n'avais pas compris cette histoire de blancs.
Aller, je te fais la première partie:

Code:

pour I de 1 à 20 faire
       nombre_aleatoire => L1 (I) 
fin

J'ai fait le plus dur.

Le reste doit être INDENTE comme je te l'ai expliqué. C'est d'autant plus important que tu vas devoir coder l'algorithme en python.
Les blancs sont représentés par des zzzzzzzz.

Code:

pour I de 1 à 19 faire
   I => K 
   pour J de I+1 à 20 faire 
      si zzzzzzzzz < L1 (K) alors 
         J => K 
      fin 
      L1 (I) => zzzzzzzzz
      L1 (K) => zzzzzzzzz on échange L1 (I) avec L1 (K) 
      A => L1 (K) 
      I => K 
   fin 
   zzzzzzzzz
fin

A voir en vidéo sur Futura · Aujourd'hui

**LeMulet** · 01/11/2017, 14h51

Envoyé par Nonimamie

Merci pour votre réponse mais je ne comprends réellement pas ce qu'il faut ajouter dans les blancs. C'est la première année que je fais du codage, j'ai réussi le reste de l'exercice mais je bloque à cette question. Pourriez-vous m'aider davantage ?

Si vous n'y parvenez pas c'est que vous n'avez pas compris le principe du tri par sélection.
L'algorithme n'est ensuite rien d'autre qu'une formalisation des tâches à effectuer.
Voir donc pour commencer le principe :
https://openclassrooms.com/courses/le-tri-par-selection

**Nonimamie** · 07/11/2017, 16h32

Merci pour vos réponses mais je suis vraiment bloquée, j'ai besoin d'aide ...

**Jack** · 07/11/2017, 16h41

Essaie au moins de faire la partie échange entre L1 (I) et L1 (K):

Code:

      L1 (I) => zzzzzzzzz
      L1 (K) => zzzzzzzzz on échange L1 (I) avec L1 (K) 
      A => L1 (K)

**Nonimamie** · 07/11/2017, 16h58

On a L₁(I) échangé avec L₁(K) ??

**Jack** · 07/11/2017, 17h16

Oui, c'est écrit dans ton algo partiel il me semble.

Il faut bien faire un échange à un moment ou à un autre pour mettre un élément en place.

**Nonimamie** · 08/11/2017, 12h06

Et comment faire le reste ??

**Jack** · 08/11/2017, 12h13

Tu n'as toujours pas complété les 3 lignes permettant l'échange.

**Nonimamie** · 08/11/2017, 12h13

Serait-ce cela ???

Variables : I, A, J, K : entiers L1, L2 : listes
Entrées et initialisation :
pour I de 1 à 20 faire
L1(J) => L1 (I)
fin
Traitement et sorties :
pour I de 1 à 19 faire
I => K
pour J de I+1 à 20 faire
si L1 (J) < L1 (K) alors
J => K
fin
L1 (I) => L1 (J)
L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)
A => L1 (K)
I => K
fin
zzzzzzzzz
fin

**Jack** · 08/11/2017, 12h58

Code:

L1 (I) => L1 (J)L1 (K) => L1 (I) on échange L1 (I) avec L1 (K) 
A => L1 (K)

Prends du papier, un crayon et une gomme et essaie. Tu verras que tu ne permutes pas L1 (I) avec L1 (K)

**Nonimamie** · 08/11/2017, 13h18

Je ne comprends pas pourquoi je ne permute pas L1(I) avec L1(K) grâce à cette ligne :

L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)

**Jack** · 08/11/2017, 16h54

Envoyé par Nonimamie

Je ne comprends pas pourquoi je ne permute pas L1(I) avec L1(K) grâce à cette ligne :

L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)

Non, tu ne les permutes pas. Il faut que tu échanges la donnée contenue dans L1 (I) avec celle contenue dans L1 (K).
Toi, ce que tu fais avec cette ligne, c'est copier L1 (K) dans L1 (I). Du coup la valeur originale de L1(I) est définitivement perdue. D'où l'intérêt de la variable A.

**Nonimamie** · 08/11/2017, 17h19

Autrement dit,
on a :
Variables : I, A, J, K : entiers L1, L2 : listes
Entrées et initialisation :
pour I de 1 à 20 faire
A => L1 (I)
fin
Traitement et sorties :
pour I de 1 à 19 faire
I => K
pour J de I+1 à 20 faire
si L1 (J) < L1 (K) alors
J => K
fin
L1 (I) => L1 (J)
L1 (K) => A on échange L1 (I) avec L1 (K)
A => L1 (K)
I => K
fin
zzzzzzzzz
fin

**Nonimamie** · 08/11/2017, 17h55

S'il-vous-plait, j'ai besoin d'aide, c'est urgent !

**Jack** · 08/11/2017, 18h13

Envoyé par Nonimamie

S'il-vous-plait, j'ai besoin d'aide

J'essaie, mais il est hors de question que je fasse ton exercice.
Ton code est toujours aussi mal présenté alors que je l'avais mis en forme pour que tu en fasses de même.

Je ne vois pas comment tu vas pouvoir te sortir d'un problème de tri si tu n'arrives pas à effectuer une simple permutation de 2 valeurs, ce qui représente à mon avis ce qui peut exister de plus simple au niveau algorithmique.
De plus, je te donne la solution de la première partie que tu remplaces par:

Code:

pour I de 1 à 20 faire 
    A => L1 (I) 
fin

C'est comme ça que tu comptes remplir le tableau avec des valeurs aléatoires? Que vaut A dans ton code?

**Nonimamie** · 08/11/2017, 20h22

Ceci vous semble peut-être simple mais ça ne l'est pas pour moi puisque ce n'est que ma première année. De plus, je ne vous ai jamais demandé de me donner l'exercice tout fait. Cependant, je suis une travailleuse et j'aime lorsque j'obtiens des résultats, et voilà 2 semaines que je tourne en rond ! Je tiens tout de même à vous remercier pour votre aide.

**Jack** · 08/11/2017, 20h35

Je vois bien que tu essaies, mais je ne sais pas trop par où commencer: je te donne un bout de code fonctionnel et tu le modifies. Je repose donc ma question: que vaut A dans le code du message #18? En quoi ce bout de code va remplir le tableau avec des valeurs aléatoires?

**Nonimamie** · 08/11/2017, 22h01

Serait-ce mieux comme ça ??

Variables : I, A, J, K : entiers L1 : liste
Entrées et initialisation :
pour I de 1 à 20 faire
nombre_aleatoire => L1 (I)
fin

Traitement et sorties :
pour I de 1 à 19 faire
I => K
pour J de I+1 à 20 faire
si L1 (J) < L1 (K) alors
J => K
fin
L1 (I) => A
L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)
A => L1 (K)
I => K
fin
Ici, je sais que je dois imprimer la liste, mais je ne sais pas comment l'écrire ??
fin

**Jack** · 08/11/2017, 22h14

Le code n'est toujours pas indenté

C'est pas facile à suivre.

Bon, ça y est tu as réussi la permutation.

Ici, je sais que je dois imprimer la liste, mais je ne sais pas comment l'écrire ??

C'est que tu n'as toujours pas compris l'algorithme. As-tu au moins essayé de l'exécuter instruction par instruction avec papier, crayon, gomme? I sert à désigner le numéro de la valeur à mettre en place dans le tableau. Donc en principe, à chaque tour de la boucle principale (celle contrôlée par I), le Ième élément doit être en place. Il n'y a plus qu'à l'afficher.

**Nonimamie** · 09/11/2017, 20h01

Je crois qu'il y a des erreurs dans mon programme python ... S'il-vous-plait

Code:

for I in range(0,20):
    n=random.randint(1,20)
    L1.append(n)
    for I in range(0,19):
        K = I
        for J in range(I+1,20):
            if L1(J)<L1(K):
                K = J
            A = L1[I]
            L1[I] = L1[K]
            L1[K] = A
            K = I
print(L1)

**Jack** · 09/11/2017, 20h07

Je ne suis pas super compétent en python. Comment sais-tu qu'il y a des erreurs? Tu as essayé ce code?
Pour imprimer la liste, il me semble que le bon sens soit que tu imprimes les valeurs de celle-ci dans une boucle.

**Nonimamie** · 09/11/2017, 20h20

J'ai refait quelques modifications ... Une erreur s'affiche dans la ligne IF !

Code:

import random

L1 = []

for I in range(0,20):
    n=random.randint(1,20)
    L1.append(n)
    for I in range(0,19):
        K = I
        for J in range(I,20):
            if L1[J]<L1[K]:
                K = J
            A = L1[I]
            L1[I] = L1[K]
            L1[K] = A
            K = I
print(L1)

**Jack** · 09/11/2017, 21h51

Comme je n'arrive plus à mettre la main sur ma boule de cristal pour avoir une idée de l'erreur, j'ai dû installer python.

L'indentation est incorrecte: une fois que la liste est initialisée, il faut revenir en marge gauche.

Algorithme Tri par sélection

Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Re : Algorithme Tri par sélection

Discussions similaires

selection naturelle versus selection sexuelle.

Tri par sélection

algorithme de tri par sélection

sélection(s)

SPI selection