What's wrong with my assembly Bubble Sort?

Question

I am implementing Bubble Sort in assembly with the basic pseudocode / outline:

for i in array
    if array[i] >= array[i+1]
        exchange array[i], array[i+1]

My ASM code:

BubbleSort PROC
    mov     EBX, LENGTHOF myArr
    .REPEAT
        mov     ESI, 0
        mov     ECX, LENGTHOF myArr
        .REPEAT
            mov     EAX, [myArr + ESI]
            .IF EAX >= [myArr + ESI + TYPE myArr]       ; If (myArr[i] < myArr[i + 1])
                xchg    EAX, [myArr + ESI + TYPE myArr]
                mov     [myArr + ESI], EAX
            .ENDIF

            add     ESI, TYPE myArr
            dec     ECX
        .UNTIL ECX == 0
    dec     EBX
    .UNTIL EBX == 0
    ret
BubbleSort ENDP

When I showed my implementation to my professor, he said that it was "kind of" like bubble sort or a "type of" bubble sort. When telling us about the assignment he said we should start from the back of the array, and move back-to-front. Yet I am starting from the front and moving front-to-back.

I feel that I'm on the right track and the code works but I want to do it correctly.

Does anyone see where I am messing up?

Answer 1

Assuming your code works, it's definitely Bubble Sort. Bubbling toward either end of the array is fine, and so is leaving out optimizations like using the outer loop counter (EBX) as an upper bound for the inner loop.

Being simplistic or naive doesn't stop it from being Bubble Sort. (If anything, being simplistic and naive is the entire point of Bubble Sort.)

---

See also Bubble Sort: An Archaeological Algorithmic Analysis for more about the history of Bubble Sort, with some discussion of the related JumpDown Sort, and whether you use a boolean as an early-out.

The version of BubbleSort it presents runs the outer loop from j=n-1 down to 1 (inclusive), so the inner loop can use it as an upper bound. But the inner loop is the same as yours, from k=0 to j, conditionally swapping A[j] with A[j+1], thus bubbling elements towards the end of the array.

The version on Wikipedia also bubbles upwards, running i from 1 to n-1 (inclusive). Wiki actually has 2 versions: that first naive one like yours, and a second that decrements n inside the loop. (Both Wiki's versions use a boolean variable to record if it did any swaps, complicating the algorithm and defeating the only purpose / advantage of Bubble Sort which is to be dead simple and have tiny code. (e.g. about 20 bytes of x86 machine code, although that's heavily optimized for size over speed. A more normal implementation would be similar size to InsertionSort.)

---

Your code uses MASM macros that will end up wasting instructions redoing checks (I assume .UNTIL ECX == 0 doesn't take advantage of the fact that dec ecx already just set flags according to ECX being non-zero). But it does have good do{}while() loop structure that's idiomatic for asm.

---

BTW, your pseudocode is missing the outer loop. That's only one pass of BubbleSort. But yes, iterating that n times will sort an n element array.