bizzaarr : manipuler une liste apres un tri

naskaa · juin 2010

salut,

<br /># O(n2)<br />def triBulle(aList, len_AList):<br />&nbsp; &nbsp; i=0;<br />&nbsp; &nbsp; Tmp=0; <br />&nbsp; &nbsp; while(i &lt; len_AList):<br />&nbsp; &nbsp; &nbsp; &nbsp; j = len_AList - 1;<br />&nbsp; &nbsp; &nbsp; &nbsp; while(j &gt; i):<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ( aList[j-1] &lt; aList[j]):<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Tmp = aList[j-1];<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; aList[j-1] = aList[j];<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; aList[j] = Tmp;<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j=j-1;<br />&nbsp; &nbsp; &nbsp; &nbsp; i=i+1;<br /><br />def Merge(l1, l2):<br />&nbsp; &nbsp; l = &#91;]<br />&nbsp; &nbsp; i = j =0<br />&nbsp; &nbsp; n1=len(l1)<br />&nbsp; &nbsp; n2=len(l2)<br />&nbsp; &nbsp; while True:<br />&nbsp; &nbsp; &nbsp; &nbsp; if i&lt;n1 and j&lt;n2:<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if l1[i]&lt;l2[j]:<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.append(l1[i])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i+=1<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.append(l2[j])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j+=1<br />&nbsp; &nbsp; &nbsp; &nbsp; elif i&gt;=n1:<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.extend(l2[j:])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break<br />&nbsp; &nbsp; &nbsp; &nbsp; else:<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.extend(l1[i:])<br />&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break<br />&nbsp; &nbsp; return l<br /><br />#O(nlogn)<br />def Tri_Fusion(l):<br />&nbsp; &nbsp; def Tri_Fusion_interne(l):<br />&nbsp; &nbsp; &nbsp; &nbsp; if len(l)&lt;2: return l<br />&nbsp; &nbsp; &nbsp; &nbsp; return Merge( Tri_Fusion_interne(l[:len(l)//2]), Tri_Fusion_interne(l[len(l)//2:]))<br />&nbsp; &nbsp; l[:]= Tri_Fusion_interne(l)<br /><br />#Creation liste<br />myList = [12,22,3,44,32,5,66,23];<br />lenMyList = len(myList);<br /><br />#TRI liste<br />#triBulle(myList, lenMyList);&nbsp; &nbsp; &nbsp; &nbsp; # tri bulle ici <br />#Tri_Fusion(myList);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # ou tri&nbsp; fusion ici<br /><br />#Affichage<br />y=0;<br />while(y &lt; len(myList)):<br />&nbsp; &nbsp; print myList[y];<br />&nbsp; &nbsp; print &quot;**&quot;<br />&nbsp; &nbsp; y=y+1;<br />

Le code ci-haut présente un triBulle et un TriFusion. Je me demande pourquoi dans le cas du tri bulle ma liste myList sans faire un return -> J'arrive a la manipuler !
Alors que pour le tri Fusion si je ne fais pas [glow=red,2,300]l[:]= Tri_Fusion_interne(l)[/glow] ca ne marche pas
et pourquoi [glow=red,2,300]l[:]= Tri_Fusion_interne(l)[/glow] au lieu de [glow=red,2,300]l= Tri_Fusion_interne(l)[/glow], a quoi sert le [:] ??

p.s. J'ai codé le tri bulle mais le tri fusion je l'ai pris sur un site
merci