Sortowanie przez scalanie/kod: Różnice pomiędzy wersjami

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
m bot poprawia starą składnię wiki
disambig
 
Linia 1:
{{disambig}}
{{Nagłówek
|tytuł=Sortowanie przez scalanie
|sekcja=Kod źródłowy
|adnotacje=Kody źródłowe programów stosujących sortowanie przez scalanie
{{Wikipedia|strona=Sortowanie przez wstawianie|dopełniacz=Sortowanie przez scalanie}}
}}
 
* Sortowanie przez scalanie – artykuł w wikipedii:<br /><br />{{softredirect|w:Sortowanie przez scalanie}}<br />
== Asembler x86 ==
* Sortowanie przez scalanie – kod źródłowy dla programistów:<br /><br />{{softredirect|b:Kody źródłowe/Sortowanie przez scalanie}}<br />
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.
 
<syntaxhighlight lang="asm">
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 ;
</syntaxhighlight>
 
=== Pascal ===
Struktura <code>tablica</code> jest tablicą, której elementy mogą być zmieniane, argumenty <code>start</code>, <code>koniec</code> są całkowitoliczbowe.
 
<syntaxhighlight lang="delphi">
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[j] < tablica[i] then
begin
tab_pom[k] := tab[j];
j := j + 1;
end
else
begin
tab_pom[k] := tab[i]
i := i + 1;
end;
k := k + 1;
end;
 
if (i <= środek)
while (i <= środek)
begin
tab_pom[k] := tab[i];
i := i + 1;
k := k + 1;
end
else
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;
</syntaxhighlight>
 
=== 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
 
<syntaxhighlight 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);
</syntaxhighlight>
== Licencja ==
{{Cc-by-3.0-tekst|dyskusja=0}}
 
[[Kategoria:Kody źródłowe]]