Algorithmique

[Baba.Com]

Algorithmique > algorithme de tri

 

Soit l'algorithme de tri suivant :
PROCEDURE sinking_sort (TABLEAU a[1:n])
passage <- 0
REPETER
permute <- FAUX
POUR i VARIANT DE 1 A n - 1 - passage FAIRE
SI a[i] > a[i+1]ALORS
échanger a[i] ET a[i+1]
permute <- VRAI
FIN SI
FIN POUR
passage <- passage + 1
TANT QUE permute = VRAI

 

1) Donnez l'évolution de l'algorithme pour trier le tableau [27, 10, 12, 8, 11] sur
l'éditeur de texte Notepad++.
2) Implémentez l'algorithme en Python.
3) Mettre en œuvre l'algorithme de tri dans le projet 'Formatage' afin de trier les clients
par ordre alphabétique.

 

Merci si vous arrivez à résoudre ce problème !

[julesx]

Bonjour,

Je ne sais pas exactement ce qu'on entend par "donner l'évolution". Moi, je procèderais comme suit.

De toute façon, le principe est de comparer successivement tous les termes consécutifs et de les permuter si le premier est supérieur au second. On recommence tant qu'on aura effectué au moins une permutation.

Ainsi, pour le tableau  [27, 10, 12, 8, 11], au premier passage, comme il y a 5 termes, on fait varier i de 1 à 4.
i=1 a[1]=27 a[2]=10 donc on permute les deux [27, 10, 12, 8, 11] devient [10, 27, 12, 8, 11]
i=2 a[2]=27 a[3]=12 donc on permute les deux [10, 27, 12, 8, 11] devient [10, 12, 27, 8, 11]
i=3 a[3]=27 a[4]=8 donc on permute les deux [10, 12, 27, 8, 11] devient [10, 12, 8, 27, 11]
i=4 a[4]=27 a[5]=11 donc on permute les deux [10, 12, 8, 27, 11] devient [10, 12, 8, 11, 27]
Il y a donc au moins une permutation, donc on continue. Par contre, comme le plus grand terme est à la fin, il est inutile d'aller jusqu'au dernier, on fait donc varier i de 1 à 4, d'où le "de 1 à n-1-passage". Ceci sera le cas à chaque passage.

Le tableau est maintenant égal à  [10, 12, 8, 11, 27].
i=1 a[1]=10 a[2]=12 on ne change rien
i=2 a[2]=12 a[3]=8 donc on permute les deux  [10, 12, 8, 11, 27] devient [10, 8, 12, 11, 27]
i=3 a[3]=12 a[4]=11 donc on permute les deux  [10, 8, 12, 11, 27] devient [10, 8, 11, 12, 27]
De même, il y a au moins une permutation, donc on continue.

 Je te laisse continuer ou utiliser une autre présentation ?

[Baba.Com]

Il y a 14 heures, julesx a dit :

Bonjour,

Je ne sais pas exactement ce qu'on entend par "donner l'évolution". Moi, je procèderais comme suit.

De toute façon, le principe est de comparer successivement tous les termes consécutifs et de les permuter si le premier est supérieur au second. On recommence tant qu'on aura effectué au moins une permutation.

Ainsi, pour le tableau  [27, 10, 12, 8, 11], au premier passage, comme il y a 5 termes, on fait varier i de 1 à 4.
i=1 a[1]=27 a[2]=10 donc on permute les deux [27, 10, 12, 8, 11] devient [10, 27, 12, 8, 11]
i=2 a[2]=27 a[3]=12 donc on permute les deux [10, 27, 12, 8, 11] devient [10, 12, 27, 8, 11]
i=3 a[3]=27 a[4]=8 donc on permute les deux [10, 12, 27, 8, 11] devient [10, 12, 8, 27, 11]
i=4 a[4]=27 a[5]=11 donc on permute les deux [10, 12, 8, 27, 11] devient [10, 12, 8, 11, 27]
Il y a donc au moins une permutation, donc on continue. Par contre, comme le plus grand terme est à la fin, il est inutile d'aller jusqu'au dernier, on fait donc varier i de 1 à 4, d'où le "de 1 à n-1-passage". Ceci sera le cas à chaque passage.

Le tableau est maintenant égal à  [10, 12, 8, 11, 27].
i=1 a[1]=10 a[2]=12 on ne change rien
i=2 a[2]=12 a[3]=8 donc on permute les deux  [10, 12, 8, 11, 27] devient [10, 8, 12, 11, 27]
i=3 a[3]=12 a[4]=11 donc on permute les deux  [10, 8, 12, 11, 27] devient [10, 8, 11, 12, 27]
De même, il y a au moins une permutation, donc on continue.

 Je te laisse continuer ou utiliser une autre présentation ?

Bonjour, 

Je voulais vous remercier pour votre aide

[julesx]

Bonjour,

Merci pour le retour. Ça ira pour la suite ?

[Baba.Com]

Le 17/02/2022 à 13:13, julesx a dit :

Bonjour,

Merci pour le retour. Ça ira pour la suite ?

Bonjour, 

Malheureusement non, j'ai longtemps réfléchi sur les questions 2 et 3 et je n'ai toujours pas trouvé comment faire... 

Pourriez-vous m'aidez ? 

Merci d'avance !

[julesx]

Bonjour,

Pour la question 2, il faut écrire un script en Python. Pour moi, une des difficultés est que l'instruction REPETER suivie de TANT QUE n'existe pas dans ce langage. Il faut donc la remplacer par While. D'autre part, il faut aussi adapter la notion TABLEAU a[1:n] dont je ne vois pas nom plus l'équivalent en Python pour lequel je ne connais que les listes et les tuples.

Ce préambule pour justifier le script que je te propose ci-dessous.

def sinking_sort (a):
    passage=0
    permute=True
    n=len(a)
    while permute==True:
        permute=False
        for i in range(n-1-passage):
            if a[i]>a[i+1]:
                b=a[i]
                a[i]=a[i+1]
                a[i+1]=b
                print(i+1,a)
                permute=True
        passage=passage+1
        print("fin passage n°",passage,"\n")
    return a

print(sinking_sort([27, 10, 12, 8, 11]))

Essaie de le comprendre et demande des explications si nécessaire. A noter que j'ai rajouté des print intermédiaires pour afficher le déroulement des opérations. Ceux-ci peuvent évidemment être supprimés dans la rédaction finale.

Pour la question 3), je ne connais pas le projet "Formatage", mais si ça concerne juste un tri de noms, il suffit de remplacer le tableau de chiffres dans l'appel de la fonction par le tableau de noms.

[Denis CAMUS]

Bonjour les deux,

Pour le tableau, l'équivalent serait la liste plutôt que le tuple. Une fois créé, un tuple n'est pas modifiable, contrairement à la liste.

https://pixees.fr/informatiquelycee/n_site/nsi_prem_pythonSequence.html

[julesx]

Bonjour Denis,

Ce sont bien des listes que j'ai utilisées. Ma phrase à propos des tableaux et des tuples était une simple remarque mais pouvait effectivement être mal interprétée.

[Baba.Com]

Le 18/02/2022 à 13:46, julesx a dit :

Bonjour,

Pour la question 2, il faut écrire un script en Python. Pour moi, une des difficultés est que l'instruction REPETER suivie de TANT QUE n'existe pas dans ce langage. Il faut donc la remplacer par While. D'autre part, il faut aussi adapter la notion TABLEAU a[1:n] dont je ne vois pas nom plus l'équivalent en Python pour lequel je ne connais que les listes et les tuples.

Ce préambule pour justifier le script que je te propose ci-dessous.

def sinking_sort (a):
    passage=0
    permute=True
    n=len(a)
    while permute==True:
        permute=False
        for i in range(n-1-passage):
            if a[i]>a[i+1]:
                b=a[i]
                a[i]=a[i+1]
                a[i+1]=b
                print(i+1,a)
                permute=True
        passage=passage+1
        print("fin passage n°",passage,"\n")
    return a

print(sinking_sort([27, 10, 12, 8, 11]))

Essaie de le comprendre et demande des explications si nécessaire. A noter que j'ai rajouté des print intermédiaires pour afficher le déroulement des opérations. Ceux-ci peuvent évidemment être supprimés dans la rédaction finale.

Pour la question 3), je ne connais pas le projet "Formatage", mais si ça concerne juste un tri de noms, il suffit de remplacer le tableau de chiffres dans l'appel de la fonction par le tableau de noms.

Bonjour,

Je vous remercie de votre réponse, le problème étant que je n'ai toujours pas compris comment rédiger la question 3.

Surtout que je ne vois pas ce que cela peut être le projet formatage...

Si on ne prend pas en compte le projet "formatage" est-ce possible de le faire ? 

Merci d'avance 

[Baba.Com]

Le 19/02/2022 à 17:40, Denis CAMUS a dit :

Bonjour les deux,

Pour le tableau, l'équivalent serait la liste plutôt que le tuple. Une fois créé, un tuple n'est pas modifiable, contrairement à la liste.

https://pixees.fr/informatiquelycee/n_site/nsi_prem_pythonSequence.html

Bonjour, 

Peut-on alors utiliser la fonction sorted ? 

[julesx]

Bonjour,

Tu ne peux pas demander à l'auteur de l'énoncé ce qu'il entend par le projet 'Formatage' ou ce qu'il veut que tu fasses i?

Comme déjà dit, si c'est uniquement un tri de noms qu'il faut faire, tu inventes une liste de noms, par exemple ["Pompidou","Coty","De Gaulle","Mitterrand"] et tu la mets à la place de [27, 10, 12, 8, 11], dans l'appel de la fonction sinking_sort.

Tu peux aussi utiliser la fonction sorted, qui fait la même chose, mais ce n'est pas dans l'optique de l'énoncé.
print(sorted(["Pompidou","Coty","De Gaulle","Mitterrand"]))