3

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?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Small_Kitten
  • 116
  • 9
  • 2
    Any particular reason why he thinks you should go back-to-front? If you look at the plain pseudocode implementation at wikipedia, its inner loop goes front-to-back, and its outer loop keeps going until no more swaps have occured. – Michael Apr 24 '20 at 05:44
  • @Michael I'm not really sure, if I remember correctly he said it will be faster than going front-to-back. – Small_Kitten Apr 24 '20 at 05:59

1 Answers1

2

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.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • Thank you for the information! We were told to use .REPEAT and .IF instead of cmp for this exercise. – Small_Kitten Apr 24 '20 at 06:30
  • 1
    @Small_Kitten: ok, that's fine. My point was that you don't need `cmp` at all. `dec ecx / jnz top of loop` is the normal thing to do at the bottom of a `do{}while(--ecx)` loop. Hiding inefficiencies like that is a downside to using MASM high-level constructs. Once you're more experienced with asm and understand how FLAGS work, it's just as easy to write loops without it. – Peter Cordes Apr 24 '20 at 06:34
  • Ah I now understand what you meant, thanks for that too! I think I've seen that implementation in some examples. Assembly is very different than other languages but I am enjoying it so far. – Small_Kitten Apr 24 '20 at 07:03
  • @Small_Kitten: cool. If you want to read more, I wrote an answer on [Why are loops always compiled into "do...while" style (tail jump)?](https://stackoverflow.com/q/47783926). See also https://stackoverflow.com/tags/x86/info for more links to docs, manuals, and so on, and [How to remove "noise" from GCC/clang assembly output?](https://stackoverflow.com/q/38552116) for getting a compiler to make example asm for you. (General principles apply for MSVC just as well as for GCC). – Peter Cordes Apr 24 '20 at 07:27
  • 1
    @Small_Kitten: And BTW, often the people asking homework questions about asm on Stack Overflow are the ones that either hate it or are totally lost (otherwise they'd have just solved their own problems by single-stepping with a debugger). So it's a nice change when someone has a real question. Anyway, C is not *that* different from asm. Once you know asm, you can think in terms of what the CPU can do efficiently while you're writing C, and in terms of how you want your code to compile. You could even write C that's structured like asm with do{}while loops, but usually compilers are good. – Peter Cordes Apr 24 '20 at 07:30