fonction récursive et tri

Version imprimable

22/12/2011, 17h45
aspire

fonction récursive et tri

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

Citation:

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.
22/12/2011, 18h00
josmiley

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

Code:

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*? :mouarf:

Évidemment, c’est récursif*!

22/12/2011, 20h29
Sve@r
Citation:
Envoyé par 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

Code:

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
23/12/2011, 10h40
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: :mrgreen:
24/12/2011, 11h42
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.
24/12/2011, 15h08
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 ?
24/12/2011, 16h06
tyrtamos

Bonjour,

Citation:

Envoyé par aspire

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.