Algorithme de tris récursif

[Olivia77]

Bonjour, je suis en L1 maths et je suis vraiment nulle en algorithme et programmation. 

Je dois faire un programme en langage algorithmique. Voilà ce qui est demandé :

- écrire une fonction triRésursif. Cette fonction fera appel à la fonction fusion qui permet de fusionner deux listes triées.

- trier un tableau : Trier les deux moitiés du tableau et les fusionner. Pour chaque parties, trier les deux moitiés et les fusionner. Et ainsi de suite.

- lorsqu'une partie contient 1 élément elle est triée : fin de récursivité.

 

Je dois rendre le devoir vendredi 18 Mars 2022. En espérant que quelqu'un puisse m'aider. 

[julesx]

Bonjour,

Je ne peux pas vraiment t'aider car j'ai des problèmes avec la récursivité et, à mon age, on ne se refait pas.

Cela dit, il y a plusieurs sites qui traitent de ce problème, entre "algorithmes de tris" dans ton moteur de recherche. La plupart donnent des exemples en Python, mais il y a ce site, en particulier, qui raisonne en termes d'algorithmes en langage symbolique ( ou naturel ?).
https://www.lri.fr/~hivert/COURS/CFA-L3/04-Tris.pdf
Va à la partie "Algorithmes plus efficaces : Diviser pour régner".
 

 

[Olivia77]

il y a 31 minutes, julesx a dit :

Bonjour,

Je ne peux pas vraiment t'aider car j'ai des problèmes avec la récursivité et, à mon age, on ne se refait pas.

Cela dit, il y a plusieurs sites qui traitent de ce problème, entre "algorithmes de tris" dans ton moteur de recherche. La plupart donnent des exemples en Python, mais il y a ce site, en particulier, qui raisonne en termes d'algorithmes en langage symbolique ( ou naturel ?).
https://www.lri.fr/~hivert/COURS/CFA-L3/04-Tris.pdf
Va à la partie "Algorithmes plus efficaces : Diviser pour régner".
 

 

merci beaucoup pour ta réponse. Je vais aller voir ce que tu m'a envoyer.

[julesx]

Bonjour,

Tu as réussi à en tirer quelque chose ?

[Olivia77]

Le 16/03/2022 à 13:36, julesx a dit :

Bonjour,

Tu as réussi à en tirer quelque chose ?

Bonjour, 

non malheureusement. Je comprend ce qu'il explique mais le mettre en application c'est une tout autre histoire. 

Est-ce tu saurais comment séparer un tableau en deux à sa moitié ? ça m'avancera beaucoup et peut être que ça me débloquera.

[julesx]

Bonjour,

En fait, ton algorithme tu veux (ou tu dois) l'écrire en langage naturel ou en Python, par exemple ?

Sinon, pour diviser un tableau en 2,  tu détermines la longueur l du tableur , tu calcules la moitié entière l1 de l (division euclidienne) et tu définis les deux moitiés en sélectionnant les termes de 1 à l1, d'une part et de l1+1 à l d'autre part. En python, en partant d'un tableau T, ça donnerait
l=len(T)
l1=l//2
T1=T[:l1] T1 contient les termes de T du rang 0 au rang l1-1
T2=T[l1:] T2 contient les termes de T du rang l1 au rang l-1
Les -1 viennent du fait qu'en Python, les indices commencent à 0.

A tout hasard, je te joins un script Python de tri récursif largement inspiré d'un de ceux trouvés sur la toile, script testé, donc qui fonctionne.

import random

def triRécursif(t):
    n=len(t)
    if n==1:
        return t
    else:
        m=n//2
    return fusion(triRécursif(t[:m]),triRécursif(t[m:]))

def fusion(t1,t2):
    if t1==[]:
        return t2
    elif t2==[]:
        return t1
    elif t1[0]<t2[0]:
        return [t1[0]]+fusion(t1[1:],t2)
    else:
        return [t2[0]]+fusion(t1,t2[1:])

liste = []
for k in range(11):
    liste.append(random.randint(0,20))
liste_triee = triRécursif(liste)
                  
print(liste)

print(liste_triee)

Mais comme dit précédemment, moi et la récursivité, ça fait deux, ne me demande pas d'expliquer la philosophie de ce script !

[Olivia77]

il y a 57 minutes, julesx a dit :

Bonjour,

En fait, ton algorithme tu veux (ou tu dois) l'écrire en langage naturel ou en Python, par exemple ?

Sinon, pour diviser un tableau en 2,  tu détermines la longueur l du tableur , tu calcules la moitié entière l1 de l (division euclidienne) et tu définis les deux moitiés en sélectionnant les termes de 1 à l1, d'une part et de l1+1 à l d'autre part. En python, en partant d'un tableau T, ça donnerait
l=len(T)
l1=l//2
T1=T[:l1] T1 contient les termes de T du rang 0 au rang l1-1
T2=T[l1:] T2 contient les termes de T du rang l1 au rang l-1
Les -1 viennent du fait qu'en Python, les indices commencent à 0.

A tout hasard, je te joins un script Python de tri récursif largement inspiré d'un de ceux trouvés sur la toile, script testé, donc qui fonctionne.

import random

def triRécursif(t):
    n=len(t)
    if n==1:
        return t
    else:
        m=n//2
    return fusion(triRécursif(t[:m]),triRécursif(t[m:]))

def fusion(t1,t2):
    if t1==[]:
        return t2
    elif t2==[]:
        return t1
    elif t1[0]<t2[0]:
        return [t1[0]]+fusion(t1[1:],t2)
    else:
        return [t2[0]]+fusion(t1,t2[1:])

liste = []
for k in range(11):
    liste.append(random.randint(0,20))
liste_triee = triRécursif(liste)
                  
print(liste)

print(liste_triee)

Mais comme dit précédemment, moi et la récursivité, ça fait deux, ne me demande pas d'expliquer la philosophie de ce script !

je dois le faire en langage algorithmique donc je pense "naturel" et en JAVA (mais je ne le ferais pas car je galère déjà sur l'autre)

Merci ça m'aide beaucoup.

[julesx]

Juste un point de détail. Quand tu réponds dans la foulée à un post, inutile de le citer. Éventuellement, si ça concerne un point particulier, tu peux te contenter de ne citer que la partie concernée.