Sortowanie przez scalanie/kod: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
→Asembler x86: kilka słów komentarza |
→Asembler x86: rozmiar tablicy nie musi być już potęgą liczby 2 |
||
Linia 8:
== 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.
<source lang="asm">
section .data
; ciąg znaków do posortowania
msg1 db '9876543210ZYXQVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba543210'
msg2 db ' '▼
; tablica pustych znaków
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 ;
skok dd 2 ; skok do początku następnej pary podciągów
indeks dd 0 ;
esiend dd 0 ; graniczne indeksy scalanych podciągów
ediend dd 0 ;
srcend dd 0 ;
endl
section .text
Linia 30 ⟶ 35:
_start:
mov [src],dword msg1 ; początkowy wskaźnik do tablicy źródłowej
mov [
petla2:
mov [bufor],dword 0 ; reset wartości indeksowych na początku
mov [
mov [indeks],dword 0
mov edx,[src] ; ustawienie granicznych indeksów podciągu drugiego
add edx,[cnt] ; na koniec tablicy źródłowej
mov [srcend],edx ;
petla1:
mov ecx,[skok] ; ecx zawiera liczbę znaków w obu podciągach do
Linia 47 ⟶ 55:
; instrukcji
mov esi,[src]
add esi,[
mov edi,esi ;
Linia 60 ⟶ 68:
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
shl ecx,1 ; będzie wykorzystywany w petli 'loop porownaj'
mov edx,[dst] ; wyznaczenie pierwszego indeksu ciągu wynikowego
add edx,[
mov [bufor],edx ; kolejny indeks przechowywany jest w zmiennej bufor
add [
; 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,[
jg pierwszy ; do tablicy wynikowej wpisywane są pozostałe ▼
cmp esi,[esiend] ; jeżeli doszliśmy do końca pierwszego podciągu▼
jg drugi ; do tablicy wynikowej wpisywane są pozostałe
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 esi,[esiend] ; jeżeli doszliśmy do końca pierwszego podciągu
▲ ; 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 drugiego podciągu
cmp al,bl ;▼
▲ jl pierwszy ; porównuje kolejne elementy ze scalanych podciągów
drugi:
mov [edx],bl ; jeżeli
inc edi ; przechodzimy do następnego znaku podciągu drugiego
mov bl,[edi] ; i ładujemy do rejestru
jmp koniec
pierwszy:
▲ mov [edx],al ; jeżeli eax<ebx, wstawiamy eax do ciągu wynikowego
▲ inc esi ; przechodzimy do następnego znaku podciągu pierwszego
▲ mov al,[esi] ; i ładujemy go do rejestru eax
koniec:
inc edx
mov [bufor],edx
inc dword [indeks];
loop porownaj ; skok do kolejnego porównania
cmp [indeks], dword
jl petla1
▲ ; podciągów
; wyświetla pośrednie tablice wynikowe
mov eax, 4 ; eax=4, write() syscall▼
mov ecx, endl ; adres tekstu do ecx▼
mov edx, 1 ; długość tekstu do edx▼
int 0x80 ; wywołanie funkcji systemowej▼
shl ecx,1 ; mnożymy skok przez 2▼
; wyświetla znak końca linii
mov eax,[src] ; tablica wynikowa staje się teraz źródłową,▼
mov ebx,[dst] ; a aktualna źródłowa będzie nadpisana zawartością▼
mov
mov eax,[src] ; w celu oszczędności pamięci
jle petla2 ▼
mov [dst],eax ; nowej tablicy wynikowej
shl ecx,1 ; jest mniejszy od dwukrotności rozmiaru
mov [skok],ecx ; tablicy, wykonujemy skok do początku pętli głównej
cmp ecx,[cnt] ; rozpoczynając scalanie od pierwszego znaku
; kończy program
</source>
| |||