Forum: Mikrocontroller und Digitale Elektronik 8051 ASM Bubblesort


von t.tichi (Gast)


Lesenswert?

Guten Morgen,

ich hab ein kleines Problem bei dem ich irgendwie nicht weiter komme. Es 
geht um die Umsetzung des Bubblesort algorithmusses in Assembler für den 
8051.
Ich habe im externen RAM die Zahlen, welche sortiert werden sollen 
abgelegt. Und wenn ich mich richtig erinnere, dann ist die äußere 
Schleife n-1
1
Habe beim googeln diverse Ausführung in Pseudocode gefunden, aber irgendwie komme ich nicht damit zurecht. Zur Erinnerung:
2
3
/* bubble sort pseudocode
4
  for(i=(arraySize - 1); i>=0; i--)
5
    for(j=1; j<=1; j++)
6
      if(arrayOfLetters[j-1] < arrayOfLetters[j])
7
      {
8
        temp = arrayOfLetters[j-1]
9
        arrayOfLetters[j-1] = arrayOfLetters[j]
10
        arrayOfLetters[j] = temp
11
      }
12
*/
Und ich habe dann mal folgendes draus gemacht:
1
sortieren:
2
    mov r0, #04h
3
4
    loop1:                                                       
5
          mov dptr, #9006h       
6
          mov a, r0                                        
7
          mov r1, a 
8
        
9
          loop2:
10
                movx a, @dptr                        
11
                mov r2, a 
12
                inc dptr 
13
                movx a, @dptr 
14
                subb a, r2    
15
                jnc continue2        
16
                
17
                swapnumbers:
18
                        movx a, @dptr               
19
                        xch a, r2                  
20
                        movx @dptr, a           
21
                        dec dpl                               
22
                        mov a, r2                        
23
                        movx @dptr, a                
24
                        inc dptr                    
25
        
26
    continue2: djnz r1, loop2    
27
28
continue1: djnz r0, loop1              
29
jmp ausgabe


Wenn ich das ganze im Singlestep einfach mal im Debugger laufen lasse, 
dann meine ich zu sehen, dass der Fehler beim Schleifenkonstrukt liegen 
muss. Vielleicht ist ja jemand so nett und hilft mir auf die Sprünge

von Peter D. (peda)


Lesenswert?

1
field_size      equ     4
2
field_start     equ     9006h
3
4
bubblesort:
5
        mov     r7, #field_size - 1
6
_bs1:
7
        mov     a, r7
8
        mov     r6, a
9
        mov     dptr, #field_start
10
_bs2:
11
        movx    a, @dptr
12
        mov     r5, a
13
        inc     dptr
14
        movx    a, @dptr
15
        clr     c
16
        subb    a, r5
17
        jnc     _bs4
18
19
        xch     a, dpl          ; dec dptr
20
        jnz     _bs3            ;
21
        dec     dph             ;
22
_bs3:                           ;
23
        dec     a               ;
24
        xch     a, dpl          ;
25
26
        movx    @dptr, a        ; store in reverse order
27
        inc     dptr
28
        mov     a, r5
29
        movx    @dptr, a
30
_bs4:
31
        djnz    r6, _bs2
32
        djnz    r7, _bs1
33
        ret


Peter

von t.tichi (Gast)


Lesenswert?

Hallo Peter und danke für deine Mühe.

Ich muss aber gestehen, dass mir deine Lösung nicht ganz klar ist. 
Getestet habe ich sie natürlich auch, um es evtl. Schritt für Schritt 
nachvollziehen zu können und ein Fehler müsste dort auch noch drin sein, 
wenn ich richtig geschaut habe.

Undzwar folgende Passage:
1
xch     a, dpl          ; dec dptr
2
        jnz     _bs3            ;
3
        dec     dph             ;
4
_bs3:                           ;
5
        dec     a               ;
6
        xch     a, dpl          ;
7
8
        movx    @dptr, a        ; store in reverse order
9
        inc     dptr
10
        mov     a, r5
11
        movx    @dptr, a

Führt zu gänzlich falschen Zahlenwerten im Ziel"array". Mir ist auch 
nicht ganz klar, warum du diesen Weg gewählt hast. Der DPTR besteht ja, 
so wie du es auch anwendest, aus niederwertigen 8-bit und höherwertig 
8-bit = 16bit total. Was ich allerdings nicht verstehe ist der Punkt, 
warum du ein xch auf den Zeiger selbst anwendest. Stehe ich da total auf 
dem Schlauch?

von t.tichi (Gast)


Lesenswert?

Leider keine Edit Funktion, daher muss ich einfach noch mal antworten. 
Ich habe mal eben den Teil etwas umgeschrieben und 2-3 getestet. 
Funktioniert, so wie ich das sehen kann. Ergebnis stimmt auch.
1
  sortieren:
2
    mov a, r3
3
    subb a,#1
4
    mov r7,a
5
  
6
  _bs1:
7
    mov a,r7
8
    mov r6,a
9
    mov dptr, #9006h
10
  
11
  _bs2:
12
    movx a, @dptr
13
    mov r5, a
14
    inc dptr
15
    movx a, @dptr
16
    clr c
17
    subb a, r5
18
    jnc _bs4
19
20
  _bs3:
21
    movx a, @dptr
22
    xch a, r5
23
    movx @dptr, a
24
    dec dpl
25
    mov a, r5
26
    movx @dptr, a
27
    inc dptr
28
    
29
  _bs4:
30
    djnz r6, _bs2
31
    djnz r7, _bs1
32
    jmp ausgabe

Ist noch ein bisschen wüst, aber es scheint erstmal zu tuen und ich kann 
endlich schlafen gehen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.