Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

bubble sort

r0nnr0nn Member Posts: 10
Hi everyone, I'm trying to implement a function in x86 assembly that sorts a given array of characters in descending order according to its ASCII code. The inputs are an array of characters and the size of the array.

In my case, the given array contains "cOmPuTeR" so the result should be "umecTRPO"

This is the pseudocode that I'm trying to follow:
[code]
/* bubble sort pseudocode
for(i=(arraySize - 1); i>=0; i--)
for(j=1; j<=1; j++)
if(arrayOfLetters[j-1] < arrayOfLetters[j])
{
temp = arrayOfLetters[j-1]
arrayOfLetters[j-1] = arrayOfLetters[j]
arrayOfLetters[j] = temp
}
*/
[/code]

Here is my code, when I try to run it I just get the original array back and the sort is not working at all.

[code]
int descending_sort( char arrayOfLetters[], int arraySize )
{
char temp;
__asm{
push eax
push ebx
push ecx
push edx
push esi
push edi

mov ebx, arrayOfLetters //initialize array
mov esi, arraySize //i
dec esi //i-1
mov edi, 1 //j
mov ecx, 0

OUTER_LOOP:
cmp esi, ecx
jl END_OUTER
jge INNER_LOOP
dec esi
jmp OUTER_LOOP

INNER_LOOP:
cmp edi, esi
jg OUTER_LOOP
jle COMPARE
inc edi
jmp INNER_LOOP

COMPARE:
mov al, byte ptr[ebx + edi * 1 - 1]
mov dl, byte ptr[ebx + edi * 1]
cmp al, dl
jl SWAP

SWAP:
mov temp, al
mov al, dl
mov dl, temp

END_OUTER:

pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax
}
}
[/code]

I appreciate any suggestions, thanks for your time.

Comments

  • anthrax11anthrax11 Member Posts: 511
    1) The swap routine swaps the values in registers, but the array in memory is never updated with the swapped values.
    2) The pseudo-code is weird in that the inner loop always has exactly one iteration, which is again weird, because that's not how bubble sort should work.
    3) The compare and swap sections are not functions in the sense that they do not automatically return to the caller before the next label, they simply fall through and continue executing from the next label. This should be taken into account.
    4) Swapping needs no temporary variable, because you already have both values stored in registers.
    5) No need to save registers, the compiler should be smart enough to handle that.
    6) There's no point doing something in assembly unless you optimize it as good as you can. One possible optimization would be to see if the sort is already completed by checking if any swapping occured during one iteration of the outer loop.

    Try this:
    [code]
    int descending_sort( char arrayOfLetters[], int arraySize )
    {
    __asm{
    mov ebx, arrayOfLetters //initialize array
    mov esi, arraySize //i

    OUTER_LOOP:
    dec esi
    jz END_OUTER
    mov edi, arraySize //j

    INNER_LOOP:
    dec edi
    jz OUTER_LOOP

    COMPARE:
    mov al, [ebx + edi - 1]
    mov dl, [ebx + edi]
    cmp al, dl
    jnl INNER_LOOP

    SWAP:
    mov [ebx + edi], al
    mov [ebx + edi - 1], dl
    jmp INNER_LOOP

    END_OUTER:
    }
    }
    [/code]
    You were quite close, though, so keep at it!
    One really useful thing to learn is how to debug your program, it makes finding errors a lot faster and easier as you can see exactly how the program behaves when it runs. You should look into it :-)
  • r0nnr0nn Member Posts: 10
    Thank you so much! Especially for pointing out #3. All along I was assuming that labels would return to the caller, I wasn't aware that they just fall through! It all makes sense to me now, again thank you so much, you made my life so much easier.
Sign In or Register to comment.