Sorting array

[Bamizas]

Hello all!

I am reading a string with numbers. I store those numbers in a array.

I would like to sort the numbers in the array by size.

Somebody can give me a hint?

[dedndave]

you mean - you convert them to binary and store them ?
or - they are stored as ASCII characters ?

dword sort ?
if you convert them to binary dwords, the masm32 library has a couple sort routines, i think
look in \masm32\help

[Bamizas]

They're already in DWORD once in the array. I just want to sort them in ascending order.

thx again.

[MichaelW]

An example using the CRT qsort function:

Code Select Expand


;==============================================================================
    include \masm32\include\masm32rt.inc
;==============================================================================
    .data
        buffer dd 100 dup(0)
    .code
;==============================================================================

compare proc C p1:DWORD, p2:DWORD
    mov eax, p1
    mov edx, p2
    mov eax, [eax]
    mov edx, [edx]
    sub eax, edx
    ret
compare endp

;==============================================================================
start:
;==============================================================================

    mov esi, OFFSET buffer

    xor ebx, ebx
    .WHILE ebx < 100
        invoke nrandom, 1000
        mov [esi+ebx*4], eax
        inc ebx
    .ENDW

    xor ebx, ebx
    .WHILE ebx < 100
        printf("%d\t", DWORD PTR [esi+ebx*4])
        inc ebx
    .ENDW
    printf( "\n\n" )

    invoke crt_qsort, esi, 100, 4, compare

    xor ebx, ebx
    .WHILE ebx < 100
        printf("%d\t", DWORD PTR [esi+ebx*4])
        inc ebx
    .ENDW
    printf( "\n\n" )

    inkey
    exit
;==============================================================================

end start


[dedndave]

the masm32 library also has quick sorts, shell sorts, etc

Code Select Expand

        INVOKE  nrQsortA,<address of array>,<number of elements> ;sort ascending
        INVOKE  nrQsortD,<address of array>,<number of elements> ;sort descending

Code Select Expand

        INVOKE  nrQsortA,offset Array,NumberOfElements

[RuiLoureiro]

How many numbers have you in the array ?
100 ? 1000 ? 10000 ? 100000 ? more ?

[Bamizas]

I dont have a lot.

Here is the first Idea I had for a code...

I am using the Irvine32 library.

Code Select Expand


.data
arrayA DWORD 4,3,5,8,7,1,3,5,9,8     

.code
MAIN PROC
mov ecx, LENGTHOF arrayA
mov esi,1
l1:
mov eax, arrayA[esi]
mov ebx, arrayA[esi+1]
cmp eax, ebx
jg change
jle stay

change:
mov arrayA[esi+1], eax
mov arrayA[esi], ebx

stay:
inc esi
loop l1

mov edx, OFFSET arrayA
call WriteInt
     

MAIN ENDP
END MAIN


But obviously it dosent work... very noob in assembly

[dedndave]

untested - see if it works   :P

Code Select Expand

        INCLUDE    \masm32\include\masm32rt.inc

        .DATA

arrayA  dw 4,3,5,8,7,1,3,5,9,8

        .CODE

_main   PROC

        mov     ebx,lengthof arrayA
        mov     esi,offset arrayA
        INVOKE  nrQsortA,esi,ebx

show00: print   str$([esi]),32
        add     esi,4
        dec     ebx
        jnz     show00

        print   chr$(13,10)
        inkey
        exit

_main   ENDP

        END     _main

[RuiLoureiro]

Bamizas,
       
            1. You need to compare each one with ALL other
               not one and NEXT.
               
            2. You must start at index esi=0, not esi=1.
           
            3. If ecx= LENGTHOF arrayA, the last index is ecx-1

           
            example:  arrayA DWORD  4, 7, 1, 8, 3
                                                   0  1  2  3  4   <-  index ( length=5 !)

            note that   arrayA[0]=4, ..., arrayA[4]=3

            compare 4:
                      with 7, next with 1, next with 8, next with 3

            When we compare 4 with 1, we change, so after this we have

            compare 1:                     next with 8, next with 3

            We get this: arrayA DWORD 1,3,4,8,7 when we use index esi=0.
            ;
            Now, go to index esi=1 ... repeat

            When esi = 4 we stop

.data
arrayA DWORD 4,3,1,8,7     

.code
MAIN PROC
   mov   ecx, LENGTHOF arrayA
      sub   ecx, 1
     
      cmp   ecx, 0
      jle   done
     
   mov   esi, 0         ; first index is 0
     
l1:
   mov   eax, arrayA[esi]
      mov   ebx, esi
     
l2:
      add   ebx, 1
     
   mov   edx, arrayA[ebx]
   cmp   eax, edx
   jle   next

      ; change
      ; ------
      xchg  eax, edx
   mov   arrayA[ebx], edx
   mov   arrayA[esi], eax
      ;
      ; next ebx
      ; --------
next:     
      cmp   ebx, ecx
      jb    l2

      ;
      ; next esi
      ; --------
      add   esi, 1
      cmp   esi, ecx
      jb    l1

done:     
   mov   edx, OFFSET arrayA
   call   WriteInt
     
MAIN ENDP
END MAIN

EDIT: replace [esi] and [ebx] by [esi*4] and [ebx*4]

[dedndave]

You need to compare each one with ALL other not one and NEXT

Rui - that's how a bubble-sort works

[RuiLoureiro]

Dave,

Rui - that's how a bubble-sort works

        I didnt understand.
        And i dont know how a bubble-sort works
        But i cannot sort comparing only the first with the second,
        the second with the third, etc.

        Follow this example:

                      arrayA DWORD  4, 7, 1, 8, 3
                                             0  1  2  3  4   <-  index ( length=5 !)

        So we have:
                    array[0]=4  array[1]=7  array[2]=1  array[3]=8  array[4]=3
                   
        Start comparing array[0] with array[1].

        array[0] is < array[1] so go on and compare array[1] with array[2]
        ...
        compare array[3] with array[4] and stop.
       
        so i never put array[0]=1.
       
        But, if you want, you can explain here how a bubble-sort works
        using arrayA example.

[mineiro]

bubble sorts works comparing the first element with all others until find the lowest, so, increment pointer to next element and go on until are in last position -1 .
another variant is compare first element with next, if lower, exchange and go comparing.
Some sorts methods divide the array in the half, and compare the first element with the first element of the half, increase both pointers until reach the end. After, divide again the half in 2 and go on.
Other method is, create an empty array, and move the value of that element to the corresponding index of that element, so after, a simple pass searching for not null characters is done. This is good because only need 2 pass. The bad is because need memory.
In youtube have some videos showing how these sorts are done.

[RuiLoureiro]

Dave,
        Sorry i misunderstood what you said  :U
        this because Bamizas compare each element with
        the next one.
       
        to compare each one with ALL other: that's how a bubble-sort works
        is what you said. Sorry

mineiro,

bubble sorts works comparing the first element with all others until find the lowest

Ok, thanks  :wink

[uosunsetter]

Why bubble?

Is there any spesific reason to not to use selection sort? Isn't it faster and simplier? Isn't bubble sort very slow? I would probably go for selection sort if I am to write a sorting algo in assembly by myself...

[dedndave]

bubble sort can be ok - for small to medium size arrays
it is very sensitive to the initial order of the array, though
if the array is completely reversed to start with (worst case for bubble sort) - it will be slow
if the array is half-way in order to start with - it can be fast
for example....

Code Select Expand

MyArray dd 10,6,7,8,9
bubble sort will order that array in 1 pass   :P

bubble sort is nice because it makes for small code and uses minimal memory
also - it would probably be easy to write a bubble sort that handles variable data sizes and could do both ascend/descend

i think one of the reasons bubble sort is a popular subject is that instructors like to have students write a reccursive version   :bg