Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

Index sort using PowerBasic's ARRAY SORT with TAGARRAY option

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new posts

  • Index sort using PowerBasic's ARRAY SORT with TAGARRAY option

    ' index sort using powerbasic's array sort with tagarray option
    '
    ' the advantage of index sort is that the data being sorted need not
    ' be moved, but can stay unchanged in their place. this is in contrast
    ' to ordinary sorting in which the original position of items is lost
    ' and cannot be retrieved.
    '
    ' an index array is formed which holds the sequence of the data after
    ' sorting. for example, after ascending sorting the 3rd smallest value
    ' will be vararray(index(3)). after ordinary sorting it would just have
    ' been vararray(3).
    '
    ' most of the methods around for sorting data (e.g. quick sort) can
    ' be modified to perform index sorting. however, if a single array
    ' needs to be index-sorted, the built-in very fast array sort of
    ' powerbasic can be applied directly - simply by using the tagarray
    ' feature as shown in the small code below.
    '
    ' if more complex data structures need to be index-sorted according to
    ' several prioritised variables, more complex methods will be needed.
    ' one such method is shown in these links:
    '
    ' http://www.powerbasic.com/support/pb...ad.php?t=22920
    '
    ' http://www.powerbasic.com/support/pb...ad.php?t=23789
    '
    ' erik christensen ------ e.chr@email.dk
    Code:
    #compile exe
    #register none
    #dim all
    '
    sub indexsortusingpbtagarray(byref variable() as long, byref index() as long, _
                                 byval n as long, byval ad as long)
        register i as long
        dim varcopy(1:n) as local long ' extra working space
        for i = 1 to n
            varcopy(i) = variable(i)
            index(i) = i
        next
        ' ad is an indicator for sorting direction.
        if ad = 0 then      ' zero: ascending sorting (default)
            array sort varcopy(), tagarray index()
        elseif ad = 1 then  ' one: descending sorting
            array sort varcopy(), tagarray index(), descend
        end if
        erase varcopy
    end sub
    '
    function pbmain
        register i as long
        local n&,t1#,t2#,t$
        n=20
        dim variable(1:n) as local long, index(1:n) as local long
        '
        t$ = "unsorted numbers:" + $crlf
        for i=1 to n
            variable(i) = rnd(1,100)
            t$ = t$ + str$(variable(i))+"  "
        next
        t$ = t$ + $crlf + $crlf
        '
        call indexsortusingpbtagarray(variable(), index(), n, 0) ' ascending index sorting
        '
        t$ = t$ + "sorted numbers (ascending order):" + $crlf
        for i=1 to n
            t$=t$+str$(variable(index(i)))+"  "
        next
        t$ = t$ + $crlf + $crlf
        '
        call indexsortusingpbtagarray(variable(), index(), n, 1) ' descending index sorting
        '
        t$ = t$ + "sorted numbers (descending order):" + $crlf
        for i=1 to n
            t$=t$+str$(variable(index(i)))+"  "
        next
        t$ = t$ + $crlf + $crlf + $crlf
        '
        t$ = t$ +"the next is a time test ----- starts on clicking ok"
        '
        msgbox t$,,"index sorting"
        '
        ' time test for index sorting of 100.000 random long integers.
        n = 100000
        redim variable(1:n), index(1:n)
        '
        for i=1 to n
            variable(i) = rnd(1,5000000)
        next
        '
        t1 = timer ' start time of sorting
        '
        call indexsortusingpbtagarray(variable(), index(), n, 0) ' ascending index sorting
        '
        t2 = timer ' end time of sorting
        '
        msgbox "sorting time = "+format$(1000 * (t2 - t1), "######")+" ms",,"powerbasic index sort of"+str$(n)+" long integers"
        '
    end function
    ------------------


    [this message has been edited by erik christensen (edited december 05, 2003).]

  • #2
    ' Index sort using PowerBasic's ARRAY SORT with TAGARRAY option
    ' Version 2

    ' This version shows the possible application for a database which
    ' stores the data in a two-dimensional string array. The example
    ' simulates such a small database. The sorting routine has been
    ' enhanced so that it also can perform both numerical and alphabetical
    ' (string) sorting. As previously, variables can be sorted ascending
    ' or descending as well. However, the data can only be sorted according
    ' to one variable at a time. If you need prioritised sorting according
    ' to more variables you still need a more complex method like the one
    ' referred to in the links in the previous post.
    '
    ' Erik Christensen ----- e.chr@email.dk
    Code:
    #COMPILE EXE
    #REGISTER NONE
    #DIM ALL
    
    SUB IndexSortUsingPBTagarrayV2(BYREF DataArray() AS STRING, BYREF Index() AS LONG, _
                                 BYVAL R AS LONG, BYVAL C AS LONG, BYVAL AD AS LONG, BYVAL CN AS LONG)
        REGISTER i AS LONG
        ' CN is an indicator for Character (1) or Numerical (0) sorting.
        IF CN = 0 THEN      ' zero: Character or Alphabetical or String sorting
            DIM VarCopy(1:R) AS LOCAL STRING ' extra working space
            FOR i = 1 TO R
                VarCopy(i) = DataArray(C,i)
                Index(i) = i
            NEXT
            ' AD is an indicator for sorting direction.
            IF AD = 0 THEN      ' zero: ascending sorting (default)
                ARRAY SORT VarCopy(), TAGARRAY Index()
            ELSEIF AD = 1 THEN  ' one: descending sorting
                ARRAY SORT VarCopy(), TAGARRAY Index(), DESCEND
            END IF
            ERASE VarCopy
        ELSEIF CN = 1 THEN  ' one: Numerical sorting
            DIM VarCopyNum(1:R) AS LOCAL SINGLE ' extra working space
            FOR i = 1 TO R
                VarCopyNum(i) = VAL(DataArray(C,i))
                Index(i) = i
            NEXT
            ' AD is an indicator for sorting direction.
            IF AD = 0 THEN      ' zero: ascending sorting (default)
                ARRAY SORT VarCopyNum(), TAGARRAY Index()
            ELSEIF AD = 1 THEN  ' one: descending sorting
                ARRAY SORT VarCopyNum(), TAGARRAY Index(), DESCEND
            END IF
            ERASE VarCopyNum
        END IF
    END SUB
    '
    SUB ShowData(BYREF DataArray() AS STRING, BYREF Index() AS LONG, BYVAL R AS LONG, BYVAL C AS LONG, BYVAL t AS STRING)
        LOCAL B$,I&,J&
        B$=""
        FOR I&=1 TO R
            FOR J&=1 TO C
                B$=B$+DataArray(J&,Index(I&))+$TAB
            NEXT
            B$=B$+$CRLF
        NEXT
        MSGBOX B$,,t$
    END SUB
    '
    FUNCTION PBMAIN()
        LOCAL I&,J&,K&
        LOCAL R AS LONG
        LOCAL C AS LONG
        R=20 ' rows
        C=4  ' columns
        DIM DataArray(1:C,1:R) AS LOCAL STRING
        DIM Index(1:R) AS LOCAL LONG
        '
        DATA "Hans","Jensen","34","Copenhagen"
        DATA "Hans","Jensen","6","Paris"
        DATA "Erik","Jensen","47","London"
        DATA "Peter","Jensen","23","New York"
        DATA "John","Jensen","9","Los Angeles"
        DATA "John","Andersen","46","Stockholm"
        DATA "Hans","Andersen","21","Oslo"
        DATA "Jack","Andersen","36","Berlin"
        DATA "John","Andersen","7","Copenhagen"
        DATA "Hans","Carlsen","33","Paris"
        DATA "Peter","Carlsen","34","London"
        DATA "Niels","Carlsen","28","New York"
        DATA "Hans","Carlsen","33","New York"
        DATA "Hans","Carlsen","64","Los Angeles"
        DATA "Erik","Carlsen","26","Stockholm"
        DATA "John","Smith","45","Oslo"
        DATA "John","Smith","65","Berlin"
        DATA "Hans","Smith","35","Los Angeles"
        DATA "John","Smith","45","Stockholm"
        DATA "Carl","Smith","36","Oslo"
        '
        FOR I&=1 TO R
            FOR J&=1 TO C
                K&=(I&-1)*C + J&
                DataArray(J&,I&)=READ$(K&)
            NEXT
            Index(I&) = I&
        NEXT
        CALL ShowData(DataArray(), Index(), R, C,"Original Unsorted Data:")
        '                                                      C  AD CN
        '                                                         01 01
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 4, 0, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Ascending alphabetical sorting according to City:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 4, 1, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Descending alphabetical sorting according to City:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 2, 1, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Descending alphabetical sorting according to Family Name:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 2, 0, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Ascending alphabetical sorting according to Family Name:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 3, 0, 1)
        CALL ShowData(DataArray(), Index(), R, C,"Ascending numerical sorting according to Age:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 3, 1, 1)
        CALL ShowData(DataArray(), Index(), R, C,"Descending numerical sorting according to Age:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 1, 0, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Ascending alphabetical sorting according to First Name:")
        '
        CALL IndexSortUsingPBTagarrayV2(DataArray(), Index(), R, 1, 1, 0)
        CALL ShowData(DataArray(), Index(), R, C,"Descending alphabetical sorting according to First Name:")
        '
        FOR I&=1 TO R : Index(I&) = I& : NEXT
        CALL ShowData(DataArray(), Index(), R, C,"Original Unsorted Data:")
        '
    END FUNCTION
    ------------------


    [This message has been edited by Erik Christensen (edited December 06, 2003).]

    Comment


    • #3

      Erik Let me try to explain... Index sorting is not a problem if
      there is monodimensional arrays, in this example, you used
      Index(x), that is not a problem, but im using Index(x, x), so
      i need to create a buffer of the indexes and sort then reassign
      index values, that is why i made it that way.


      Elias.

      ------------------
      Learning math hurts your brain, Learning life Hurts your heart.


      Do you need a grid In your App?.... EGRID32

      Comment


      • #4
        The array is two-dimensional. Each row represents a certain
        individual. Each column represents a certain variable. Sorting
        has the effect of changing the displayed sequence of the
        individuals (rows). The integrity of each full row is maintained,
        i.e. all the variable values belonging to a given individual are
        still being displayed in one and the same row. The displayed row
        positions are just being changed according to the values of the
        variable being sorted. Even if you perform prioritised sorting
        according to more variables at the same time, a one-dimensional
        sorting index would still be sufficient.

        Only if you wish to move the variables belonging to each indivi-
        dual apart, so that they are no longer located on the same row but
        on different rows, i.e. if you want a grid without a fixed
        relationship between items in each row (and between items in
        each column for that matter), you may need a two-dimensional
        index. I guess that may be what you want? But would sorting
        then still be relevant?

        Best Regards,

        Erik
        ------------------




        [This message has been edited by Erik Christensen (edited December 09, 2003).]

        Comment

        Working...
        X