CODEWITHSUNDEEP
assemblyx86att
RandomName
RandomName

Reputation: 23

Sorting a string in alphabetical order using assembly

I'm using ubuntu 32 bits to code in assembly. And I'm trying to do a program to order a string in alphabetical order, but it's not working correctly.

I declared the string. I used lea to place the string in the eax register. Then used movl(%eax), %ebx, to copy the first memory cell (0) of the string that would be the "l", to then compare it with the second memory cell (1) that would be the"h".

In the next cycle, to compare the second memory cell with the third memory cell I did inc %eax so that it would do movl 1(%eax), %ebx instead movl (%eax), %ebx. This is my code:

.data
    str: .string "lhtgbvfmjnbcdsaawcfr"
.text
.globl main
main:
    movl $19, %ecx
inicio:
    leal variavel, %eax
    movl (%eax), %ebx
    cmpl %ebx, 1(%eax) 
    JA maior 
    JB menor
maior:
    xchg %ebx, 1(%eax)
    xchg (%eax), %ebx 
menor:  
    inc %eax 
    decl %ecx 
    cmpl $0, %ecx
    JA inicio 
    JE main

What i did didn't work, so clearly there is something wrong, I've searched about assembly but I haven't found many things. Is there anyone that can help me?

Upvotes: 0

Views: 2278

Answers (1)

rkhb
rkhb

Reputation: 14409

You're describing a simple Bubble Sort algorithm according to http://en.wikipedia.org/wiki/Bubble_sort:

Bubble sort animation

A ".string" is just an array of characters. The last character has the value 0 to determine the end of the string. A character is coded as an 8-bit-value. So you only need to use the 8-bit registers of the CPU (AL, AH, DL, DH etc.) to handle them. You can use the 32-bit extended registers (EAX, EBX, ECX, EDX etc.), but this complicates things unnecessarily.

Bubble Sort needs two nested loops. In this case an endless outer loop that ends when the string is sorted, and an inner loop that handles every character.

The following example is very simple. For example, the last - sorted - letter is unnecessarily compared again and again. It has a lot of potential for improvement:

#   Name:               bubblesort.s
#   Assemble & link:    gcc -m32 -obubblesort bubblesort.s
#   Run:                ./bubblesort

.data
fmt: .string "%s\n"
str: .string "lhtgbvfmjnbcdsaawcfr"

.text
.global main
main:

    pushl $str                  # Address of str onto the stack
    pushl $fmt                  # Address of fmt onto the stack
    call printf                 # Call libc: printf(fmt,str)
    addl $(4*2), %esp           # Adjust the stack by 2 PUSHes

    O1:                         # Outer loop ends when everything is sorted (swapped == false)
    movl $str, %esi
    movb $0, %dl                # swapped = false

    I1:                         # Inner loop: every character
    movb (%esi), %al
    movb 1(%esi), %ah
    cmpb $0, %ah                # End of string?
    je O2                       # Yes -> exit inner loop

    cmpb %ah, %al               # Compare the characters
    jbe I2                      # If AL < AH, don't swap the characters
    movb $1, %dl                # swapped = true
    movb %al, 1(%esi)           # Swap: Store the characters in reversed order
    movb %ah, (%esi)

    I2:
    incl %esi                   # Next character
    jmp I1

    O2:
    pushal                      # Preserve all registers
    pushl $str                  # Address of str onto the stack
    pushl $fmt                  # Address of fmt onto the stack
    call printf                 # Call libc: printf(fmt,str)
    addl $(4*2), %esp           # Adjust the stack by 2 PUSHes
    popal                       # Restore all registers

    cmpb $1, %dl                # swapped == true?
    je O1                       # Yes -> one more outer loop

    Done:
    ret                         # Return: exit the main function

And here is another "animated" illustration:

https://www.youtube.com/watch?v=lyZQPjUT5B4

Upvotes: 1

Related Questions