Bubblesort probléma

Bubblesort probléma
2018-04-10T14:50:38+02:00
2018-04-10T19:34:13+02:00
2022-10-15T21:35:28+02:00
HelloWorld
Sziasztok!

Assembly x86-ban tanulok programozni. Olyan feladatot kaptam, hogy bekérek a felhasználótól karaktereket szóközzel elválasztva (A programomban nem vizsgálom, hogy mi történik, ha nem csak egy karaktert adok meg, hanem mondjuk egy stringet->nem számít, mert a felhasználó csak karaktereket fog megadni.) Utána azokat a karaktereket ki kell iratni Z-A sorrendben. De csak a kisbetűket, más karaktereket ignorálni kell, valamint, ha egy betűből több van, akkor a felesleget is ignoráljuk.

Én úgy képzeltem el a megoldást, hogy létrehozok egy buffert, amibe elmentem a kisbetűket szóközök nélkül. A buffer végére még beszúrok egy null karaktert. Utána hívom a bubblesort függvényt/procedúrát, ez szépen sorrendbe rakná a karaktereket, majd azután dobálnám ki a felesleget.

A bubblesort függvényt ezen az oldalon talált pszeudokód szerint készítettem: x86 Assembly Lesson 1 Chapter 12
Maga a pszeudokód így néz ki:

; ----------------------------
; | bubble_sort ; | sort an array whose pointer pointed by arr_idx ; | modifies: ; | none ; | algorithm outline: (when size = 10) ; | for i = 0 to 8 ; | for j = i+1 to 9
; | if arr_idx>arr_idx[j] then swap(arr_idx, arr_idx[j]);
; | ; | i is mapped to SI ; | j is mapped to DI ; | bx hold the base array index ; | ah, al is to aid processing ; | cx is to hold the size ; ---------------------------- proc bubble_sort arr_idx: word, size: word pusha ; save all registers mov bx, [arr_idx] mov cx, [size] dec cx ; because maximum index bound is always one less than ; the size (i.e. when size is 10, the index is 0..9, not 1..10) sub si, si sub di, di @@loop_i: mov di, si inc di ; j = i + 1 @@loop_j: mov ah, [bx+si] ; AH = arr_idx mov al, [bx+di] ; AL = arr_idx[j] cmp ah, al ; if (arr_idx<= arr_idx[j]) then no swap
jle @@noswap mov [bx+si], al ; else swap mov [bx+di], ah @@no_swap: inc di ;(increase j)
cmp di, cx ; (compare with bound) jbe @@loop_j ; if below or equal, then go to @@loop_j ; end of loop j inc si ; increment i cmp si, cx ; compare with bound jb @@loop_i ; if below, then loop to @@loop_i popa ; restore all registers ret endp

Sajnos, valamiért nálam nem működik. Igaz, én ESI és EDIvel dolgoztam végig, és cx helyett az utolsó karaktert vizsgáltam. Segítetek rájönni, hogy miért nem működik? És még abban is kérhetnék tanácsot, hogyan törölhetném ki azokat a karaktereket a bufferből, amelyek többször megtalálhatóak?

Itt a forráskódom:

%include "asm_io.inc" segment .data buffer times 500 db 0 ;létrehozom a buffert a karakterek számára segment .text global _asm_main _asm_main: enter 0,0 pusha mov ebx, buffer mov edi, buffer mov esi,ebx ;Ez a rész itt bekéri a karaktereket, a kisbetűkön kívül mindent ignorál ;a bekért karaktereket elmenti a bufferbe, de csak a kisbetűket és szóközök nélkül char_loop: call read_char cmp al,10 jz last_char cmp al,13 jz last_char cmp al,'a' jl char_loop cmp al,'z'+1 jnl char_loop stosb jmp char_loop ;itt a buffer végére beszurok egy null karaktert last_char: mov al,0 stosb call print_nl ; itt jön a bubblesort call bubblesort ;itt kiírja a buffer tartalmát write: mov al,[ebx] cmp al,0 jz end call print_char inc ebx jmp write end: popa mov EAX, 0 leave ret bubblesort: loop_i: mov edi,esi inc edi ;j = i + 1 loop_j: mov al,[esi] cmp al,[edi] jge no_swap xchg al,[edi] no_swap: inc edi mov al,[edi] cmp al,0 jbe loop_j inc esi mov al,[esi] cmp al,0 jb loop_i ret


Mutasd a teljes hozzászólást!
Köszi mindenkinek! Sikerült megoldanom a sorttal. Annyi volt a hiba, hogy amikor a feltételeknél vizsgáltam a bubblesort funkcióban, hogy az EDI vagy az ESI egyenlő-e nullával, akkor ott át kellett írni az ugrásokat jg-re.
Köszi mindekinek az ötleteket! :)
Mutasd a teljes hozzászólást!

  • A felesleg kidobálása  már megvan. :) Ha a sortot sikerül megoldani, akkor a kiiratásnál csak megvizsgálom:

    ... mov al,[ebx] cmp al,0 jz end cmp al,[ebx+1] jz inc_ebx...
    És az inc_ebx-ben pedig növelem az ebx-t, majd visszaugrok a kiiratásra.
    Mutasd a teljes hozzászólást!
  • Ha nem feltétlenül előírt a sort használata, felesleges komplikálni. Kiallokálsz egy 256 byte hosszúságú memóriaterületet, kinullázod, majd a beérkező charakterek ascii értékét offsetnek használva bármilyen nemnulla értékre állítod a megfelelő memóriacimet.
    Az olvasás befejeztével egy ciklussal kiolvasod 61h-tól ('a') 7Ah-ig ('z') a memóriacímeket. Ahol nem nulla ott az offsetet most ascii értékként kiératod.
    Mutasd a teljes hozzászólást!
  • más karaktereket ignorálni kell, valamint, ha egy betűből több van, akkor a felesleget is ignoráljuk.

    Ez alapján pont olyasmi kell neki, amit leírtál. Persze lehetne előszűrni, meg bitmezőbe csoportosítani (a kisbetűk jelenléte akár egy darab 32-bites regiszterben is követhető lenne), csak minek.
    Mutasd a teljes hozzászólást!
  • Köszi mindenkinek! Sikerült megoldanom a sorttal. Annyi volt a hiba, hogy amikor a feltételeknél vizsgáltam a bubblesort funkcióban, hogy az EDI vagy az ESI egyenlő-e nullával, akkor ott át kellett írni az ugrásokat jg-re.
    Köszi mindekinek az ötleteket! :)
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd