Newbie and need help w/ completing a bubble sort program

[turtle13]

I am just starting out learning assembly and NASM and one of my first assignments is to complete this simple bubble sort program.

http://ideone.com/NUovpA

I figured out that it is sorting in descending order, I just need to complete it so that it runs through inner and outer loops as needed.

I believe that I need to have the "outerloop" start at 0 (the first index of the array of integers) and then increment ecx by 1 each time it is run, however, I'm stumped as to how to implement that.

I am then required to create a variable named "passes" that holds the number of times that "outerloop" executes. I believe this should go under the "section .data" ? And how should I implement that in the "outerloop" loop?

An additional array named "output" should be placed in "section .bss" where the values of the array named "array" must be copied.

Please help to guide an exasperated newbie on the right path 

[Frank Kotler]

Hi turtle13,

Welcome to the forum. You will find that we're not going to do your homework for you, but we will help. Is that "ideone" code your own work, or is that the "assignment"?

You would increment ecx with:

Code: [Select]

inc ecx
your code already does that.

The variable "passes" could go in "section .data" or it could go in "section .bss". Unlike ecx, Nasm doesn't know how big "passes" is, so we'll have to tell it. A byte ought to be big enough...

Code: [Select]

inc byte [passes]

Since your code obviously sorts "array" in place, I don't see why you need "output", but it shouldn't be a problem...

Code: [Select]

section .bss
output resd 9

I'm going to have to refresh my memory on just how "bubble sort" is supposed to go. I'm pretty sure I've done it, but it was a long time ago (DOS, I imagine). I think we need a variable - a "flag" to tell us if a "swap" has been done on each pass. We set it to zero before each pass, and if it's still zero, we're done. I think I had a routine to print the array after each pass so we could watch the values "bubble" up and down. This makes a good debugging tool too.

I'll try to get back to you on this. Remind me if I don't. You work on it too, and show us how you're doing. As I said, we're not going to do it for you.

Best,
Frank

[Frank Kotler]

This is just "your code" with a "print_array" routine. It seems to be "working" as is. I think it can be improved.

BTW, just "code" in square brackets at the beeginning of your code, and "/code" in square brackets at the end.

Code: [Select]

; from "turtle13" on the forum
; nasm -f elf32 myprog.asm
; ld -o myprog myprog.o -m elf_i386

bits 32
section .text ;section declaration
global _start
_start:

    call print_array

    mov edx, 9
    jmp outerloop

outerloop:
    mov ecx, 0          ; instead of 0, value should be the number of times outerloop has traversed
    jmp innerloop

innerloop:
    mov eax, [array + ecx * 4]
    mov ebx, [array + 4 + ecx * 4]
    cmp eax, ebx
    jge next
    mov [array + ecx * 4], ebx
    mov [array + 4 + ecx * 4], eax
next:
;    call print_array

    inc ecx
    cmp ecx, edx
    jl innerloop
    je endinner
endinner:
    dec edx
    jnz outerloop
done:
    call print_array

    mov ebx,0       ;first syscall argument: exit code
    mov eax,1       ;system call number (sys_exit)
    int 0x80        ;"trap" to kernel

print_array:
    push eax
    push ecx
    xor ecx, ecx
    .top:
    mov eax, [array + ecx * 4]
    call showeaxd
    mov al, ' '
    call putc
    inc ecx
    cmp ecx, 9
    jle .top
    mov al, 10
    call putc
    pop ecx
    pop eax
    ret

;---------------------------------
; showeaxd - print a decimal representation of eax to stdout
; for "debug purposes only"... mostly
; expects: number in eax
; returns; nothing useful
showeaxd:
    push eax
    push ebx
    push ecx
    push edx
    push esi
   
    sub esp, 10h
    lea ecx, [esp + 12]
    mov ebx, 10
    xor esi, esi
    mov byte [ecx], 0
.top:   
    dec ecx
    xor edx, edx
    div ebx
    add dl, '0'
    mov [ecx], dl
    inc esi
    or eax, eax
    jnz .top
   
    mov edx, esi
    mov ebx, 1
    mov eax, 4
    int 80h
   
    add esp, 10h

    pop esi
    pop edx
    pop ecx
    pop ebx
    pop eax

    ret
;---------------------------------
;---------------------------------
putc:
    push edx
    push ecx
    push ebx
    push eax
   
    mov eax, 4 ; sys_write
    mov ebx, 1 ; stdout
    mov ecx, esp ; buffer is on stack
    mov edx, 1 ; just one character
    int 80h
    pop eax
    pop ebx
    pop ecx
    pop edx
    ret
;------------------------

section .data       ;section declaration
; This variable must remain named exactly 'array'
array dd 3, 9, 1, 6, 2, 4, 0, 5, 7, 8


Best,
Frank

[turtle13]

Frank thanks for your help here,
many hours spent reading today trying to learn how this all works and I still feel lost. Here is the latest code I have:

Code: [Select]

bits 32
section .text ;section declaration
global _start
_start:
    mov edx, 9
    jmp outerloop

outerloop:
    inc passes
    mov ecx, 0          ; instead of 0, value should be the number of times outerloop has traversed
    jmp innerloop

innerloop:
    mov eax, [array + ecx * 4]
    mov ebx, [array + 4 + ecx * 4]
    cmp eax, ebx
    jge next
    mov [array + ecx * 4], ebx
    mov [array + 4 + ecx * 4], eax
    jmp next
next:
    inc ecx
    cmp ecx, edx
    jl innerloop
    je endinner
endinner:
    dec edx
    jnz outerloop
done:
    mov ebx,0       ;first syscall argument: exit code
    mov eax,1       ;system call number (sys_exit)
    int 0x80        ;"trap" to kernel

section .data       ;section declaration
; This variable must remain named exactly 'array'
array dd 3, 9, 1, 6, 2, 4, 0, 5, 7, 8
passes dd 0

section .bss
output resd 9

I am trying to declare a variable "passes" which increments each time that outerloop is run (the way I have declared "passes"now in secton.data, I get errors when trying to compile "error: invalid combination of opcode and operands".. how do I declare a variable that increments each time a loop is run?)

Also.. how do I do a printf type operation so I can see what the values are in the array? I am starting to learn gdb but can't figure out how to show the results of an array variable.

[Frank Kotler]

Code: [Select]

;    inc passes
; this is the address (offset) of the variable
; you want the "[contents]"
inc dword [passes]

See the "showeaxd" routine I posted (I also have a "showeaxh" that displays it in hex). We don't need the number to be in eax, but edx:eax is the implicit operand to "div" (edx * 4gig + eax) so it needs to wind up in eax (and edx!) eventually. I should have commented that more extensively.

The manufacturer's documentation is preferred, but you can find the instruction set reference from the old Nasm manual here:
http://home.myfairpoint.net/fbkotler/nasmdocr.html

If it wuz easy, everybody'd be doing it!

Best,
Frank

[turtle13]

I'm getting there..

I ended up completing my assignment with the following code (it's a bit quirky because the professor had requirements such as the return code needed to be the number of passes through the bubble sort)

Code: [Select]

bits 32
section .text ;section declaration
global _start
_start:
    mov edx, 19

outerloop:
    inc byte [passes]
    mov ecx, 0   
    mov [swapflag], ecx       

innerloop:
    mov eax, [array + ecx * 4]
    mov ebx, [array + 4 + ecx * 4]
    cmp eax, ebx
    jle next
    inc byte [swapflag]
    mov [array + ecx * 4], ebx
    mov [array + 4 + ecx * 4], eax
next:
    inc ecx
    cmp ecx, edx
    jl innerloop
    je endinner
endinner:
    mov ebx, [swapflag]
    cmp ebx, 0
    je done
    dec edx
    jnz outerloop
done:
    cld
    mov ecx, 80
    mov edi, output
    mov esi, array
    rep movsb
    mov ebx, [passes]       ;first syscall argument: exit code
    mov eax, 1       ;system call number (sys_exit)
    int 0x80        ;"trap" to kernel

section .data       ;section declaration
; This variable must remain named exactly 'array'
array dd 7, 11, 4, 5, 19, 20, 8, 10, 9, 15, 6, 16, 12, 3, 2, 17, 14, 13, 1, 18
passes db 0
swapflag db 0

section .bss
output resd 20


I still having some issues with setting the flag and making it more efficient. As you can see I tried to increment the flag only when it swapped numbers through a pass and it is supposed to end the program when it goes through a pass without swapping anything (meaning that the sort is completed) yet doesn't seem to do that. After 11 hours of working on this today it's now 2am and I'm pretty much over it at this point

[Frank Kotler]

Watch your sizes. Both "passes" and "swapflag" are bytes, but you sometimes move a 32 bit register in and out of them. This can overwrite the next variable. I don't know if it's a problem or not.

Best,
Frank