Tri fusion - Page 1

Je comprend pas bien pk le tri fusion est rapide.
Y divise un tableau de n éléments en n tableau à 1 éléments. Pk pas direcement mettre un chiffre dans un tableau.
Sinon je cherche des explications en général sur l'ordre de tri du tri fusion ?
Et m^me plus gfénéralemnt sur le tri fzsion
Mezrci d'avance
Smile

en fait on l'appelle aussi le tri par éclatement - fusion et c'est pour ça qu'on obtient n tableaux de 1 élément (donc forcément triés ) . Le principe du tri est ensuite reformer un seul tableau en regroupant récursivement des tableaux triés grâçe à une procédure de fusion. Imagine que tu as deux tas de cartes triés, la procédure fusion reforme un tas trié en comparant consécutivement les cartes qui sont au sommet des deux tas.
exemple:
{6, 3, 7, 5} | éclatement
{6, 3} {7, 5} |
{6} {3} {7} {5} |
{3, 6} {5, 7} | fusion
{3, 5, 6, 7} |

"Diviser pour mieux reigner" un grand principe tres souvent efficace ....
* y'a deja eut cinquante mille sujets là dessus
* http://ndailly.free.fr/projets/tris/fusion.html

tiens voilà un prog de tri par fusion que j'ai programmé en basic . C'est un prog à récursivité non terminale.
désolé je peux pas brancher ma ti au pc donc tu seras obligé de recopier

Tfus(lst)
Func

Local p,q,k,lst1,lst2,n
dim(lst)->n

If n>1 Then
  Tfus(left(lst,floor(n/2)))->lst1
  Tfus(right(lst,n-floor(n/2)))->lst2
Else
  {}->lst1
  {}->lst2
EndIf

augment(lst1,@)->lst1
augment(lst2,@)->lst2

1->p
1->q
1->k

While lst1[p]/=@ or lst2[q]/=@      // @ est un marqeur

 If lst1[p]>=lst2[q] Then
   lst2[q]->lst[k]
   q+1->q
 Else
   lst1[p]->lst[k]
   p+1->p
 EndIf

 k+1->k
EndWhile

 Return lst

EndFunc

Merci bcp pour l'algo c sympa par contre le site je le connaissais
"@ est un marqeur"
cad ? parce que qd je mets le sigle la caltoche n'est pas d'accord
C quoi un marqueur ?
/= et ça j'imagine que ça veut dire différent ?
Merci d'avance

de rien
@> ouais excuse moi c parce que sait pas faire le signe "infini" dans mes post
en fait c'est pour marquer la fin des listes lst1 et lst2 pour sortir de la boucle while.
Si lst1[p] et lst[q] valent l'infini, la boucle se termine. Si un seul des deux vaut l'infini la boucle s'occupe de tous les éléments restants dans l'autre liste car ils sont obligatoirement inférieurs à l'infini.
Ici c'est beaucoup plus simple d'utiliser un marqueur que les dimensions des listes lst1 et lst2, par exemple:

1->p
1->q
1->k

dim(lst1)->dimlst1
dim(lst2)->dimlst2

While p<dimlst1 or q<dimlst2

If lst1[p]>=lst2[q] Then
lst2[q]->lst[k]
q+1->q
Else
lst1[p]->lst[k]
p+1->p
EndIf

k+1->k
EndWhile

ne fonctionne pas car si tu arrives au dernier élément d'une des liste à fusionner il est forcément inférieur (tri dans l'ordre croissant) aux éléments qui restent dans l'autre liste donc le test de la boucle "if" provoque d'abord une erreur de logique et ensuite bloque le programme (tentative de lecture d'un élément inexistant)

/= c'est bien "différent de" ...