Ordinare un vettore è un’ operazione che solitamente (con algoritmi tra i quali c’è il Bubble Sort) ha un costo N².
Con Merge Sort questo no è un problema.
|
|
1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> 8<br /> 9<br />10<br />11<br />12<br />13<br />14<br />15<br />16<br />17<br />18<br />19<br />20<br />21<br />22<br />23<br />24<br />25<br />26<br />27<br />28<br />29<br />30<br />31<br />32<br />33<br />34<br />35<br />36<br />37 |
|
|
|
<span style="color: #007788; font-weight: bold;">void</span> mergesort(<span style="color: #007788; font-weight: bold;">int</span><span style="color: #555555;">*</span> V, <span style="color: #007788; font-weight: bold;">int</span> g){<br /> <span style="color: #006699; font-weight: bold;">if</span>(g <span style="color: #555555;">==</span> <span style="color: #ff6600;">1</span>) <br /> <span style="color: #006699; font-weight: bold;">return</span>;<br /> <span style="color: #007788; font-weight: bold;">int</span> k <span style="color: #555555;">=</span> (g <span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>);<br /> <span style="color: #007788; font-weight: bold;">int</span> s2 <span style="color: #555555;">=</span> g<span style="color: #555555;">-</span>k;<br /> <span style="color: #007788; font-weight: bold;">int</span> V1 [k];<br /> assert(V1<span style="color: #555555;">!=</span><span style="color: #336666;">NULL</span>);<br /> <span style="color: #007788; font-weight: bold;">int</span> V2 [s2];<br /> assert(V2<span style="color: #555555;">!=</span><span style="color: #336666;">NULL</span>);<br /> <span style="color: #006699; font-weight: bold;">for</span> ( i <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>; i <span style="color: #555555;"><</span> k ; i<span style="color: #555555;">++</span>)<br /> V1[ i ] <span style="color: #555555;">=</span> V[ i ];<br /> <span style="color: #006699; font-weight: bold;">for</span> ( i <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>; i <span style="color: #555555;"><</span> s2 ; i<span style="color: #555555;">++</span>){<br /> V2[i] <span style="color: #555555;">=</span> V[k<span style="color: #555555;">+</span>i];<br /> }<br /> merge(V1,k);<br /> merge(V2,s2);<br /> <span style="color: #007788; font-weight: bold;">int</span> i1,i2;<br /> i1<span style="color: #555555;">=</span>i2 <span style="color: #555555;">=</span><span style="color: #ff6600;">0</span>;<br /> <span style="color: #006699; font-weight: bold;">while</span> (i1 <span style="color: #555555;"><</span>k <span style="color: #555555;">&&</span> i2<span style="color: #555555;"><</span>s2){<br /> <span style="color: #006699; font-weight: bold;">if</span> (V1[i1] <span style="color: #555555;"><=</span> V2[i2]) {<br /> V[i1<span style="color: #555555;">+</span>i2] <span style="color: #555555;">=</span> V1[i1]; <br /> i1<span style="color: #555555;">++</span>;<br /> }<br /> <span style="color: #006699; font-weight: bold;">else</span>{<br /> V[i1<span style="color: #555555;">+</span>i2]<span style="color: #555555;">=</span>V2[i2];<br /> i2<span style="color: #555555;">++</span>;<br /> }}<br /> <span style="color: #006699; font-weight: bold;">while</span> (i1 <span style="color: #555555;"><</span> k) {<br /> V[i1<span style="color: #555555;">+</span>i2] <span style="color: #555555;">=</span> V1[i1];<br /> i1<span style="color: #555555;">++</span>;<br /> }<br /> <span style="color: #006699; font-weight: bold;">while</span> (i2 <span style="color: #555555;"><</span>s2) {<br /> V[i1<span style="color: #555555;">+</span>i2] <span style="color: #555555;">=</span> V2[i2];<br /> i2<span style="color: #555555;">++</span>;<br /> }<br /> <span style="color: #006699; font-weight: bold;">return</span>;<br /> }<br /> |
|
