Sortieralgorithmus Bubble-Sort in 8051-Assembler

[Wilhelm F. (Gast)]

So, die Herrschaften. Ich habe im Betreff mal den Namensteil "Sortier", 
damit man es in der Forensuche findet.

Der Bubble-Sort funktioniert ausgezeichnet, wenn auch ich in 
Internetseiten fand, daß er eher nur zu Lehrzwecken eingesetzt wird. 
Aber das ist nur die halbe Wahrheit, in meinen Applikationen tut der es 
sehr gut:

.if BUBBLE_SORT_USED

; Bubble Sort Sortierprogramm

; Vom aufrufenden Programm werden uebergeben:

; R2 enthaelt Adresse der Bytekette
; R3 enthaelt Laenge der Bytekette

; Hier verwendet werden:

; R0 ist Zeiger auf LSB der Bytekette
; R1 ist Zeiger auf LSB+1 der Bytekette
: R4 innere Schleife
; ACC ist Arbeitsregister

; Ist die Byteanzahl kleiner als 2, wird das Programm vorher beendet.

; Die aufsteigende Sortierreihenfolge kann auf einfache Weise geaendert
; werden, wenn man den bedingten Sprung beim Groeßenvergleich um kehrt,
; also das Carry-Flag negiert bzw. den komplementaeren Befehl verwendet.

BUBBLE_SORT:
        MOV     A, R3             ; teste auf Anfangslaenge
        DEC     R3                ; n-1 Durchlaeufe
        SETB    C
        SUBB    A, #1
        JC      BUBBLE_SORT_ENDE  ; Ende, wenn Anzahl zu klein
BUBBLE_SORT_RE_INIT:
        MOV     A, R2             ; Adressen der beiden Operanden
        MOV     R0, A             ; in ein Zeigerregister umladen
        INC     A
        MOV     R1, A
        MOV     A, R3             ; Anzahl der restlichen Durchlaeufe
        MOV     R4, A
BUBBLE_SORT_LOOP:
        CLR     C
        MOV     A, @R0
        SUBB    A, @R1
        JC      BUBBLE_SORT_LOOP_2; wenn R1 > R0: nicht tauschen!
        XCH     A, @R0            ; sonst tauschen!
        XCH     A, @R1
        XCH     A, @R0
BUBBLE_SORT_LOOP_2:
        INC     R0
        INC     R1
        DJNZ    R4, BUBBLE_SORT_LOOP
        DJNZ    R3, BUBBLE_SORT_RE_INIT
BUBBLE_SORT_ENDE:
        RET

.endif ; if BUBBLE_SORT_USED

Der Quicksort scheint besser, habe den noch nicht ganz durchschaut.

Der hier gezeigte Code arbeitet aber schon diagonal, es wird pro 
Durchlauf ein Element weniger verarbeitet, weil nach einem Durchlauf 
immer ein Element schon sortiert ist.

Ganz ausgefeilt ist er nicht, man könnte in der Schleife noch fest 
stellen, ob eine Reihe Elemente bereits sortiert sind, und dann 
abbrechen.

Nun ja, in Assembler ist das sowieso hypergalaktisch schnell.

Es kann und darf noch optimiert werden.

Ob man die Funktion reentrant macht oder nicht, da gibt es eben einige 
Möglichkeiten.

[Läubi .. (laeubi)]

Wilhelm Ferkes schrieb:
> Der Bubble-Sort funktioniert ausgezeichnet, wenn auch ich in
> Internetseiten fand, daß er eher nur zu Lehrzwecken eingesetzt wird

Was nicht heißt das es nicht funktioniert... Die Laufzeit ist nur (im 
Vergleich zu anderen Verfahren) für Große Datenmengen halt ungünstig.

[Wilhelm F. (Gast)]

Läubi .. schrieb:

> Wilhelm Ferkes schrieb:
>> Der Bubble-Sort funktioniert ausgezeichnet, wenn auch ich in
>> Internetseiten fand, daß er eher nur zu Lehrzwecken eingesetzt wird
>
> Was nicht heißt das es nicht funktioniert... Die Laufzeit ist nur (im
> Vergleich zu anderen Verfahren) für Große Datenmengen halt ungünstig.

Ich arbeite noch an den Dingen, z.B. Quicksort oder Shellsort. Für 
vieles an meinem 8051 reicht aber der Bubble-Sort. Keine Frage. 5 
Elemente sortiert der auch in weniger als 100µS. Sagen wir mal für 5 
Sortierelemente. Darüber steigt es dann mindestens quadratisch in 
Laufzeit, deswegen muß man sich dann was besseres als den Bubble-Sort 
nehmen.

Es stellt sich mir gerade ein ganz neuer Aspekt: Daten in einem 8-bit-µC 
sortieren, die vielleicht 32 bit haben. Da würde ich die Funktion 
COMPARE mit skalierbarer Bytelänge aufrufen, die auch nur aus wenigen 
Zeilen besteht, die ein Carry-Flag zurück gibt.

Das geht alles, auch auf einem 8-bitter. Keine Frage.