Asembler x86 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 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 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 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 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 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