Kody źródłowe/Sortowanie przez scalanie
Asembler x86
[edytuj]Poniższy kod jest prostą iteracyjną implementacją algorytmu sortowania przez scalanie. Sortowane są w kolejności rosnącej elementy tablicy znaków zgodnie z ich kodem ASCII.
section .data
; ciąg znaków do posortowania
msg1 db '9876543210ZYXQVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba543210'
; tablica pustych znaków
msg2 db ' '
src dd 0 ; wskaźnik do aktualnej źródłowej tablicy
dst dd 0 ; wskaźnik do aktualnej tablicy wynikowej
cnt dd 68 ; rozmiar tablicy wpisany na stałe, znajdujący się także
; wpisany na stałe w linii 115 tego kodu źródłowego
bufor dd 0 ; ofset kolejnego znaku tablicy dst
skok dd 2 ; skok do początku następnej pary podciągów
ofset dd 0 ;
indeks dd 0 ;
esiend dd 0 ; graniczne indeksy scalanych podciągów
ediend dd 0 ;
srcend dd 0 ;
endl db 0x0a ; znak końca linii
section .text
global _start
_start:
mov [src],dword msg1 ; początkowy wskaźnik do tablicy źródłowej
mov [dst],dword msg2 ; i docelowej
petla2:
mov [bufor],dword 0 ; reset wartości indeksowych na początku
mov [ofset],dword 0 ; każdego obiegu pętli głównej
mov [indeks],dword 0
mov edx,[src] ; ustawienie granicznych indeksów podciągu drugiego
add edx,[cnt] ; na koniec tablicy źródłowej
dec edx ;
mov [srcend],edx ;
petla1:
mov ecx,[skok] ; ecx zawiera liczbę znaków w obu podciągach do
; wstawienia do ciągu wynikowego
shr ecx,1 ; tymczasowa modyfikacja ecx na potrzeby poniższych
; instrukcji
mov esi,[src] ; esi ustawione na początek podciągu pierwszego
add esi,[ofset]
mov edi,esi ;
add edi,ecx ; edi ustawione na początek podciągu drugiego
mov al,[esi] ; rejestry eax oraz ebx zawierają kolejne elementy
mov bl,[edi] ; porównywane w celu scalenia podciągów
dec ecx ; tymczasowa modyfikacja ecx na potrzeby poniższych
; instrukcji
mov edx,esi ; ustawienie granicznych indeksów podciągu pierwszego
add edx,ecx ; na koniec podciągu pierwszego
mov [esiend],edx ;
mov edx,edi ; ustawienie granicznych indeksów podciągu drugiego
add edx,ecx ; na koniec podciągu drugiego zwiększając wartość o CF
mov [ediend],edx ;
inc ecx ; przywrócenie pierwotnej wartości ECX, który
shl ecx,1 ; będzie wykorzystywany w petli 'loop porownaj'
mov edx,[dst] ; wyznaczenie pierwszego indeksu ciągu wynikowego
add edx,[ofset] ;
mov [bufor],edx ; kolejny indeks przechowywany jest w zmiennej bufor
add [ofset],ecx ; zwiększenie ofsetu o wartość skoku na potrzeby kolejnego
; obiegu pętli
porownaj:
mov edx,[bufor]
cmp esi,[srcend] ; jeżeli pierwszy podciąg doszedł do końca tablicy źródłowej
jg koniec ; rozpoczyna sie nowy obieg petli
cmp edi,[srcend] ; jeżeli drugi podciąg doszedł do końca tablicy źródłowej
jg pierwszy ; do tablicy wynikowej wpisywane są pozostałe
; elementy z pierwszego podciągu
cmp esi,[esiend] ; jeżeli doszliśmy do końca pierwszego podciągu
jg drugi ; do tablicy wynikowej wpisywane są pozostałe
; elementy z drugiego podciągu
cmp edi,[ediend] ; jeżeli doszliśmy do końca drugiego podciągu
jg pierwszy ; do tablicy wynikowej wpisywane są pozostałe
; elementy z pierwszego podciągu
cmp al,bl ; porównuje kolejne elementy ze scalanych podciągów
jl pierwszy ; kopiuje mniejszy z nich do tablicy wynikowej
drugi:
mov [edx],bl ; jeżeli BL<=AL, wstawiamy BL do ciągu wynikowego
inc edi ; przechodzimy do następnego znaku podciągu drugiego
mov bl,[edi] ; i ładujemy do rejestru BL
jmp koniec
pierwszy:
mov [edx],al ; jeżeli AL<BL, wstawiamy AL do ciągu wynikowego
inc esi ; przechodzimy do następnego znaku podciągu pierwszego
mov al,[esi] ; i ładujemy go do rejestru AL
koniec:
inc edx
mov [bufor],edx
inc dword [indeks];
loop porownaj ; skok do kolejnego porównania
cmp [indeks], dword 68 ; dopóki nie przeszliśmy końcowego elementu ciągu
jl petla1 ; wynikowego, to porównujemy elementy kolejnych par podciągów
; wyświetla pośrednie tablice wynikowe
mov eax, 4 ; eax=4, write() syscall
mov ebx, 1 ; ebx=1, stdout
mov ecx, [dst] ; adres tekstu do ecx
mov edx, [cnt] ; długość tekstu do edx
int 0x80 ; wywołanie funkcji systemowej
; wyświetla znak końca linii
mov eax, 4 ; eax=4, write() syscall
mov ebx, 1 ; ebx=1, stdout
mov ecx, endl ; adres tekstu do ecx
mov edx, 1 ; długość tekstu do edx
int 0x80 ; wywołanie funkcji systemowej
mov eax,[src] ; w celu oszczędności pamięci
mov ebx,[dst] ; tablica wynikowa staje się teraz źródłową,
mov [src],ebx ; a aktualna źródłowa będzie nadpisana zawartością
mov [dst],eax ; nowej tablicy wynikowej
mov ecx,[skok] ; mnożymy skok przez 2, jeżeli nowy skok
shl ecx,1 ; jest mniejszy od dwukrotności rozmiaru
mov [skok],ecx ; tablicy, wykonujemy skok do początku pętli głównej
shr ecx,1 ;
cmp ecx,[cnt] ; rozpoczynając scalanie od pierwszego znaku
jl petla2 ;
; kończy program
mov eax, 1 ; exit() syscall
mov ebx, 5 ; kod wyjścia
int 0x80 ;
Pascal
[edytuj]Struktura tablica jest tablicą, której elementy mogą być zmieniane, argumenty start, koniec są całkowitoliczbowe.
procedure merge(tablica, start, środek, koniec);
var tab_pom : array [0..koniec-start] of integer;
i,j,k : integer;
begin
i := start;
k := 0;
j := środek + 1;
while (i <= środek) and (j <= koniec)
begin
if tablica[i] <= tablica[j] then
begin
tab_pom[k] := tab[i]
i := i + 1;
end
else
begin
tab_pom[k] := tab[j];
j := j + 1;
end;
k := k + 1;
end;
while (i <= środek)
begin
tab_pom[k] := tab[i];
i := i + 1;
k := k + 1;
end;
while (j <= koniec)
begin
tab_pom[k] := tab[j];
j := j + 1;
k := k + 1;
end;
for i:= 0 to koniec-start do
tab[start + i] := tab_pom[i];
end;
procedure merge_sort(tablica, start, koniec);
var środek : integer;
begin
if start <> koniec then
begin
środek := (start + koniec) div 2;
merge_sort(tablica, start, środek);
merge_sort(tablica, środek + 1, koniec);
merge (tablica, start, środek, koniec);
end;
end;
JavaScript
[edytuj]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
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);
Python
[edytuj]def scal(n):
if len(n)==1:return n
s=int(len(n)/2)
a=scal(n[:s])
b=scal(n[s:])
a=a[::-1]
b=b[::-1]
i=a.pop()
e=b.pop()
c=[]
for x in range(len(n)):
if(i<e):
c.append(i)
if not len(a)==0:
i=a.pop()
else:
c.append(e)
for q in b:
c.append(q)
break
else:
c.append(e)
if not len(b)==0:
e=b.pop()
else:
c.append(i)
for q in a:
c.append(q)
break
return c
Licencja
[edytuj]
