Sortowanie przez scalanie/kod: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
→Asembler x86: rozmiar tablicy nie musi być już potęgą liczby 2 |
dodano javascript |
||
Linia 224:
end;
</source>
=== Java script ===
Porównanie mergsorterów znalezionych na:
http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0013.php
oraz
http://www.algorytm.org/algorytmy-sortowania/sortowanie-przez-scalanie-mergesort/merge-d.html
Wszystko gotowe do odpalenia w konsoli firebuga
<source lang="javascript">
function merge(pocz, sr, kon)
{
var i,j,q;
t = new Array();
for (i=pocz; i<=kon; i++) t[i]=tab[i]; // Skopiowanie danych do tablicy pomocniczej
i=pocz; j=sr+1; q=pocz; // Ustawienie wskaźników tablic
while (i<=sr && j<=kon) { // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
tab_iter++;
if (t[i]<t[j])
tab[q++]=t[i++];
else
tab[q++]=t[j++];
}
while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
}
function mergesort(pocz, kon)
{
var sr;
if (pocz<kon) {
sr=Math.floor((pocz+kon)/2);
mergesort(pocz, sr); // Dzielenie lewej części
mergesort(sr+1, kon); // Dzielenie prawej części
merge(pocz, sr, kon); // Łączenie części lewej i prawej
}
}
function onemerge(i_p, i_k)
{
var i_s,i1,i2,i;
p = new Array();
i_s = Math.floor((i_p + i_k + 1) / 2);
if(i_s - i_p > 1) onemerge(i_p, i_s - 1);
if(i_k - i_s > 0) onemerge(i_s, i_k);
i1 = i_p; i2 = i_s;
for(i = i_p; i <= i_k; i++)
{ d_iter++;
p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
}
for(i = i_p; i <= i_k; i++) d[i] = p[i];
}
tab_iter = d_iter = 0;
source= new Array();
for(counter = 0; counter < 100; counter++) source[counter] = Math.floor(Math.random() * 100);
tab = d = source;
mergesort(0, source.length-1);
onemerge(0,source.length-1);
console.log(tab);
console.log('tab iter'+tab_iter);
console.log('##################');
console.log(d);
console.log('d iter'+d_iter);
</source>
| |||