Help with Bubble Sorting in MASM

[dedndave]

in reply #8, i outlined it for him - you want me to write the code for him ? - lol

[RuiLoureiro]

in reply #8, i outlined it for him - you want me to write the code for him ? - lol

No Dave, you can do only if you want, of course.

Here is a linked list example (it is in the old forum)
There are 3 fields: LkdData (80 bytes), StrData( 40 bytes), IntData (dword)
The data in linked list is only in LkdData,
StrData and IntData are not in linked list.
The example shows the structure (read it).
I think we can redefine the structure (try)
and we dont need to alloc memory for it
(NOTE: but the memory has a special structure!).

[RuiLoureiro]

Hi MASMClass,
              i am reading (and learning ) what you did.

1.  If «maximum length of student name» is 10.

    we should do THIS:

MAXNUMST = 4                  ; maximum number of students that can be entered into database
NAMELEN = 10                  ; maximum length of student name
NAMELEN0    = NAMELEN + 1  ; maximum length of student name + NULL

lastname    BYTE NAMELEN0 DUP(0)
firstname   BYTE NAMELEN0 DUP(0)

lnamearr    BYTE MAXNUMST*NAMELEN0 DUP(0)   ; last name array
fnamearr    BYTE MAXNUMST*NAMELEN0 DUP(0)       ; first name array
stuidnum    DWORD MAXNUMST DUP(0)         ; student id array
avgscore    DWORD MAXNUMST DUP(0)         ; average score array

        If we want «maximum length of student name» is 9.
        DO
            NAMELEN = 9

       EDIT: i want NAMELEN and NAMELEN0 because i like to   
                work with NAMELEN, not with NAMELEN0.

2. We have 4 different arrays for each record.

   It means that when we do SortByLastName, we need
   change all other three in the same way.
   The same for SortByScore.

   So, we need one procedure to exchange 2 strings
   and another to exchange 2 dwords.
   
        Is it what you want to do ?
        Good luck !

[RuiLoureiro]

Hi
        I modified bubble_sort (MASM) to bubble_sortM
        and
        i wrote SortString which is bubble_sort for strings

       See the file below

        Here are the results:
        Good luck !  ;)


         EDIT: replace «jl» by «jle» to sort integers.       

Unsorted INTEGERS
1
9
2
8
3
7
4
6
5
0

Sorted INTEGERS- Bubble SORT
0
1
2
3
4
5
6
7
8
9
Unsorted STRINGS

Hutch
dedndave
MichaelW
Jochen
Gunther
Raymond
Farabi
Zen
minor28
RuiLoureiro
Press any key to continue ...

Sorted STRINGS- Bubble SORT

dedndave              <<<<<<<<<<<<<<<--- Hey, you are the first !
Farabi
Gunther
Hutch
Jochen
MichaelW
minor28
Raymond
RuiLoureiro
Zen
Press any key to continue ...

[dedndave]

looks good, Rui   :t
some time back, i needed an index sort - can't remember what it was for - lol
if i could remember, i could find the source for it

[Gunther]

Hi Rui,

good and illustrating example.  :t

Gunther

[minor28]

I do not know if bubble sorting is the same as heap sorting but heap sorting is how I sort and search in lists.

[RuiLoureiro]

I do not know if bubble sorting is the same as heap sorting but heap sorting is how I sort and search in lists.

It doesnt seem to be the same.

[RuiLoureiro]

Hi

    This is the new linked list file LkdList5.asm
    Now it works with 4 fields in linked list and ...

    See the file LkdList5.zip (asm,exe) and test it.
    I tried to explain a lot of things in the file .asm.

    Good luck !   
    RuiLoureiro
   

        We may create a linked list database with 4 fields in linked_list:

            First  field X: LkdDataX   -> is a string field

            Second field Y: LkdDataY   -> is a string field

            Third  field I: LkdDataI   -> is an integer field

            Fourth field K: LkdDataK   -> is an integer field

            These fields are defined in the NODE structure we can see below.
           
            These names (LkdDataX,LkdDataY,LkdDataI,LkdDataK) are used in
            the written procedures, so we cannot redefine it.

            We may add some other like StrData for strings or IntData for
            integers. But these are not in linked_list. They stay only
            in the records.

      -----------------------------
      CREATING A DATABASE
      -----------------------------
     
            1. Define NumOfRecords ( LenOfRecords is defined in NODE)

            2. call
           
            invoke   CreateLkdList, NumOfRecords, LenOfRecords, addr pBuffer, addr pList

            3. before exiting, call

                invoke   DestroyLkdList, pBuffer

    --------------               
         OR
    -------------       

            1. We use _LkdDataXBase defined in .DATA

            2. call
           
                invoke  FormatLkdList, NumOfRecords, pList

      --------------------------------------------
      INSERTING DATA INTO A DATABASE
      --------------------------------------------

        First, insert into field X using InsertLkdListX because only
        this procedure alloc one free record (the others dont alloc)
     
            invoke   InsertLkdListX, pList, addr Frut1          ; insert string

        Second, insert any other by any order
           
            invoke   InsertLkdListY, pList, addr Str1           ; insert string           
            invoke   InsertLkdListI, pList, Val1                ; insert integer
            invoke   InsertLkdListK, pList, 20                  ; insert integer

        Third, add any other
       
            invoke   AddStrLkdList, pList, NODE.StrData, addr Str1      ; string
            invoke   AddIntLkdList, pList, NODE.IntData, Val1           ; integer

      --------------------------------------------
      DELETING DATA FROM A DATABASE
      --------------------------------------------
     
            Use DeleteLkdListX  or DeleteLkdListY or DeleteLkdListI or DeleteLkdListK

            They try to find the string or integer and remove the record from the
            database. They don't wait for an answer, so it is not the best way, but...

[RuiLoureiro]

Hi

***--The Linked List Database --***
       
        I wrote a set of basic procedures to build a
        complete linked list database (LkdList6.inc).

        I wrote an example program that shows how
        to use the procedures (LkdList6.asm).

        For detailed information, read LkdList6.txt
       
        If you don't mind, try to test it and
        say something about it.

        Good luck !
        RuiLoureiro

        NOTE: Soon, i will post a complete example.
              You may write your own example, easily.

        Files:
                LkdList6.inc <---- set of basic procedures
                LkdList6.glb  ----  global (protos ...)
                LkdList6.mac  ----  macros
                LkdList6.dat  ----  test data
                LkdList6.txt <---- text about basic information

                LkdList6.asm <---- basic example

[Gunther]

Rui,

well done.

Gunther

[Will]

hutch:

I know that I've been exiled to the 16 bit DOS Programming thread of this forum but this problem interests me right now because one of the things I use my Advanced Data Access method (ADAM) is as a sorter. Unfortunately I am in the middle of converting it to MASM32 so it probably can't help with this problem until I get it finished. I should be finished in a week or so. How I sorted records using ADAM was to build a record with a key in the order that I wanted it sorted, created an ADAM file using ADAMCREA.exe with that key, added the records I built in random order to the ADAM file using ADAMACMD, and then read them back in sequential order because  ADAM has them all sorted by key. An example would be if you want your records sorted by last name, first name, and social security number (in case you could have duplicate first and last name), you could build them with a key of last name say 30 characters, first name 30 characters, and social security number 9 characters which gives you a key 69 characters long. Create an ADAM file using the program ADAMCREA,exe to build a file with the 69 characters in the first position (the key) plus the record length, however long, so the ADAM record length would be your record length plus 69. Add them to the file that you created in random order using ADAMACMD and, VIOLA! read them back all sorted in sequential order using ADAMACMD.

I won't be too much longer with the conversion from 16 bit DOS to MASM32 but I have a question. Under DOS you use the ES:SI registers to point at the source for a move to the address in the DS:DI registers. You move a field of data from one segment to another. Under MASM 32, since the ESI and EDI registers are now 32 bits long, does it even matter what the ES register and the DS point to?  :icon_confused: I don't think so because in MASM32 everything in a program is linked together in one up to 4 gigabyte "segment!" 

Will

[dedndave]

it's DS:SI / DS:ESI and ES:DI / ES:EDI
in win32, all addresses are 32 bits in size, so you must use ESI and EDI
and - right, with a Flat memory model, CS = DS = ES = SS, no need to mess with the segment registers

EDIT: in truth, the segment registers are not pointers to physical segments anymore
they are, instead, pointers to tables with physical memory maps
so, the values in the segment registers may not be the same
but, they point to the same virtual memory

[Gunther]

Will,

I assume you're talking about the string instructions. Here's the description of STOS from the Intel Manual, Vol. 2B, p. 4-444:

In non-64-bit and default 64-bit mode; stores a byte, word, or doubleword from the AL, AX, or EAX register (respectively) into the destination operand. The destination operand is a memory location, the address of which is read from either the ES:EDI or ES:DI register (depending on the address-size attribute of the instruction and the mode of operation). The ES segment cannot be overridden with a segment override prefix.

At the assembly-code level, two forms of the instruction are allowed: the "explicit-operands" form and the "nooperands" form. The explicit-operands form (specified with the STOS mnemonic) allows the destination operand to be specified explicitly. Here, the destination operand should be a symbol that indicates the size and location of the destination value. The source operand is then automatically selected to match the size of the destination operand
(the AL register for byte operands, AX for word operands, EAX for doubleword operands). The explicit-operands form is provided to allow documentation; however, note that the documentation provided by this form can be misleading. That is, the destination operand symbol must specify the correct type (size) of the operand (byte, word, or doubleword), but it does not have to specify the correct location. The location is always specified by the ES:(E)DI register. These must be loaded correctly before the store string instruction is executed.

The no-operands form provides "short forms" of the byte, word, doubleword, and quadword versions of the STOS instructions. Here also ES:(E)DI is assumed to be the destination operand and AL, AX, or EAX is assumed to be the source operand. The size of the destination and source operands is selected by the mnemonic: STOSB (byte read from register AL), STOSW (word from AX), STOSD (doubleword from EAX). After the byte, word, or doubleword is transferred from the register to the memory location, the (E)DI register is incremented or decremented according to the setting of the DF flag in the EFLAGS register. If the DF flag is 0, the register is incremented; if the DF flag is 1, the register is decremented (the register is incremented or decremented by 1 for byte operations, by 2 for word operations, by 4 for doubleword operations).

HTH
Gunther

[Will]

it's DS:SI / DS:ESI and ES:DI / ES:EDI
in win32, all addresses are 32 bits in size, so you must use ESI and EDI
and - right, with a Flat memory model, CS = DS = ES = SS, no need to mess with the segment registers

EDIT: in truth, the segment registers are not pointers to physical segments anymore
they are, instead, pointers to tables with physical memory maps
so, the values in the segment registers may not be the same
but, they point to the same virtual memory

You're right, I got the register notation backward in my post. But I do have to "mess" with the ES and DS registers because that's the way ADAM works in DOS and it'll be the same in MAS32. What we are talking about here is that I have to set the ES:EDI registers to point to the ADAM .data and the DS:ESI to the user .data when writing a record for the user and the opposite when reading a record for the user. I had to do the same thing when I originally wrote ADAM in 1982, except it was DS:SI and ES:DI. Actually, it makes the convert easier because it already works under DOS, just change the SI and DI registers to ESI and EDI   :t