Discussion :

[aspire]

Je cherche à coder le plus simplement possible en python la fonction suivante du tri fusion:
avec A tableau a trier et p<q<r

TRI-FUSION(A, p, r)
si p < r
alors q ← (p + r)/2

TRI-FUSION(A, p, q)
TRI-FUSION(A, q + 1, r)
FUSION(A, p, q, r)

en gardant les appels récursifs séparés. (pas de Fusion(tri-fusion(...),tri_fusion(..))
Fusion réalise juste la fusion de 2 tableaux déjà triés en o(n) cad A de p à q et A de q+1 à r.

[josmiley]

heu ....
t'aurais pas plutôt un exemple input/output ; ce serait plus clair pour moi ...

[mont29]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
def trifusion(A, p, r):
    if p < r:
        q = (p + r)/2
        trifusion(A, p, q)
        trifusion(A, q + 1, r)
        fusion(A, p, q, r)

Non*?

Évidemment, c’est récursif*!

[Sve@r]

Je cherche à coder le plus simplement possible en python la fonction suivante du tri fusion:
avec A tableau a trier et p<q<r

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
TRI-FUSION(A, p, r)
    si p < r
    alors q ← (p + r)/2
        TRI-FUSION(A, p, q)
        TRI-FUSION(A, q + 1, r)
        FUSION(A, p, q, r)

en gardant les appels récursifs séparés. (pas de Fusion(tri-fusion(...),tri_fusion(..))
Fusion réalise juste la fusion de 2 tableaux déjà triés en o(n) cad A de p à q et A de q+1 à r.

Salut

Déjà pense à encadrer ton code entre balises "CODE" et non balises "QUOTE". Comme ça, il reste quand on cite ton post.

Sinon ben toute l'astuce de l'algorithme "tri-fusion" consiste dans la fusion. Or là ben tu as un peu "oublié" cette étape...

https://secure.wikimedia.org/wikiped...iki/Tri_fusion

[aspire]

En fait je cherche plus a récupérer les paramètres de la récursion. Je n'arrive pas a faire le tri sur place dans le tableau A. J'ai une solution récursive qui reprend les 2 listes et les fusionne mais en reconstruisant une nouvelle liste a chaque fois. Ici je cherche a utilisé le même tableau.

Désolé pour les balises je suis allé un peu vite.
@mont29:

[dividee]

Le tri fusion ne fonctionne pas en place, c'est d'ailleurs son principal désavantage par rapport au quicksort (son avantage est qu'il est O(n*log(n)) dans le pire des cas, contrairement au quicksort).

Cela dit, il me semble que l'utilisation de mémoire supplémentaire peut être limité à n/2: il suffirait de recopier A[p:q], la fusion opérerait sur cette copie et sur le tableau A entre les indices q et r (pas besoin de recopier ceux-là), et le résultat irait directement dans A.

[aspire]

C'est tout a fait ca dividee.
La fusion n'est pas réalisée sur place.
mais le quicksort est en o(n²) dans le pire des cas... alors que le tri fusion reste en o(nlgn).

Qui connait l'algo utilisé dans la fonction standard sort() de python ?

[tyrtamos]

Bonjour,

Qui connait l'algo utilisé dans la fonction standard sort() de python ?

S'il n'a pas changé depuis 2002, ça doit être "timsort" de Tim Peters: http://en.wikipedia.org/wiki/Timsort.