Announcement

Collapse
No announcement yet.

Array Sort

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

  • Michael Mattias
    replied
    So, you want to do some multiple-key sorting?

    Here are two articles from "BASICally Speaking" you should pick up:

    "Mukti-Key Sorting" by Alan Earnshaw, June 1995
    "Multi-Key Sorting Revisited" by Michael Mattias, May 1997

    Reprints are four US bucks each. You can order at the publisher's web site: http://www.infoms.com




    -------------
    Michael Mattias
    Racine WI USA
    [email protected]

    Leave a comment:


  • Lance Edmonds
    replied
    ARRAY SORT uses a proprietary "quick sort" algorythm, which means that ARRAY SORT
    sorts without regard to existing positions in an array. In other words, it sorts
    on the absolute value of the subscripts, exactly as you found.

    This works fine for many situations, but in your case, you are really looking
    to perform a sort based on two keys: "rebounds" and "names". Therefore this
    requires a slightly different aproach... there are a couple of techniques to
    consider:

    1. Sort the array first by "rebounds", then examine the results and perform
    another sort on the "names" limited to the range of elements where the "rebounds"
    values are identical. The would ensure that where the rebounds values are identical,
    the names in that range are sorted in alphanumeric order. ARRAY SORT provides methods
    of limiting the range of subscripts that are sorted.

    2. build a new key array that comprises both rebounds and names to form a single key.
    This technique means that a single sort can be used in place of the dual sort method
    in #1 above. For example, the new key could be made in the following format:
    "#####.## <---name--->". Creating a key like this is a cinch with the USING$() function.
    Additionally, this technique allows you to continue with the multiple array sorting
    techniques discussed earlier in this thread.



    -------------
    Lance
    PowerBASIC Support
    ( mailto:[email protected][email protected]</A> )

    Leave a comment:


  • Guest's Avatar
    Guest replied
    Thanks for Tim Wisseman's help. Unfortunately I am still a fairly new programmer in Power Basic and was not familiar with some of his commands etc. I have now been able to use Lance Edmonds' ARRAY SORT with the TAGARRAY. However I don't understand how some of the sorts work. Here is one example:

    DIM playername$(20)
    DIM playergame(29)
    DIM defenserd(20)
    DIM average(29)

    Here is the order before the first sort by games:

    Player Gm Drbs Avg
    McDonnell,B 4 6 1.50
    Gillory,T 4 10 2.50
    Ramirez,Ian 4 8 2.00
    Robinson,T 4 11 2.75
    Bates,Aaron 4 6 1.50
    Carter,T 4 6 1.50
    Johnson,O 4 5 1.25
    Gilchrist,D 4 9 2.25
    Cunningham,E 3 2 0.67
    Triplett,D 3 1 0.33
    Conklin,B 1 0 0.00
    Turner,Micah 2 0 0.00
    Boyd,Chris 1 0 0.00


    Here is the order after I sort by games:

    Player Gm Drbs Avg
    McDonnell,B 4 6 1.50
    Gillory,T 4 10 2.50
    Ramirez,Ian 4 8 2.00
    Robinson,T 4 11 2.75
    Bates,Aaron 4 6 1.50
    Carter,T 4 6 1.50
    Johnson,O 4 5 1.25
    Gilchrist,D 4 9 2.25
    Cunningham,E 3 2 0.67
    Triplett,D 3 1 0.33
    Turner,Micah 2 0 0.00
    Conklin,B 1 0 0.00
    Boyd,Chris 1 0 0.00

    Next I sort by Rebounds:

    Player Gm Drbs Avg

    Robinson,T 4 11 2.75
    Gillory,T 4 10 2.50
    Gilchrist,D 4 9 2.25
    Ramirez,Ian 4 8 2.00
    McDonnell,B 4 6 1.50
    Carter,T 4 6 1.50 ? Why were they switched?
    Bates,Aaron 4 6 1.50 ?
    Johnson,O 4 5 1.25
    Cunningham,E 3 2 0.67
    Triplett,D 3 1 0.33
    turner,Micah 2 0 0.00
    Conklin,B 1 0 0.00
    Boyd,Chris 1 0 0.00

    Finally I sort by average:

    Player Gm Drbs Avg
    Robinson,T 4 11 2.75
    Gillory,T 4 10 2.50
    Gilchrist,D 4 9 2.25
    Ramirez,Ian 4 8 2.00
    McDonnell,B 4 6 1.50
    Carter,T 4 6 1.50
    Bates,Aaron 4 6 1.50
    Johnson,O 4 5 1.25
    Cunningham,E 3 2 0.67
    Triplett,D 3 1 0.33
    Turner,Micah 2 0 0.00
    Conklin,B 1 0 0.00
    Boyd,Chris 1 0 0.00

    Why was Carter moved ahead of Bates after being sorted by rebounds?

    Again I used Lance Edmonds' ARRAY SORT with the TAGARRAY

    Thanks,

    Dave

    Leave a comment:


  • Guest's Avatar
    Guest replied
    Here is how to do it.

    Code:
    DIM playername(0 TO 29) AS String
    DIM playergame(0 TO 29) AS Long
    DIM defenserebounds(0 TO 29) AS Long
    DIM average(0 TO 29)AS Long
    
    DIM ptIndex(0 TO 29) AS LONG
    DIM v(0 TO 29) AS Long
    Dim vT As Long
    Dim ptT As Long
    Dim sA As String
    
    DIM i AS LONG
    Dim fg as Long
    
       '// Test data //
       Randomize Timer
       For i = 0 to 29
          playergame(i) = Int(rnd * 200)
          playername(i) = "Player " + Chr$(65 + i)
          defenserebounds(i) = Int(Rnd * 300)
          average(i) = Int(rnd * 399)
       Next i
    
       '  First I want to sort by games in descending order
       ' and if players have the same average, I want the player
       ' with the most games to be ahead of a player with fewer games
       '// Set starting sort values //
       FOR i = 0 TO 29
          ptIndex(i) = i
          v(i) = defenserebounds(i)
       NEXT i
       '// Sort    v(0) will hold the highest value
       fg = 1
       Do While fg = 1
          fg = 0
          FOR i = 28 To 0 Step -1
             IF v(i) < v(i + 1) THEN
                fg = 1
                '// Swap i with i + 1 //
                vT = v(i)
                ptT = ptIndex(i)
                v(i) = v(i + 1)
                ptIndex(i) = ptIndex(i + 1)
                v(i + 1) = vT
                ptIndex(i + 1) = ptT
             End If
             If v(i) = v(i + 1) Then
                If playergame(ptIndex(i)) < playergame(ptIndex(i + 1)) Then
                   fg = 1
                   '// Swap i with i + 1 //
                   vT = v(i)
                   ptT = ptIndex(i)
                   v(i) = v(i + 1)
                   ptIndex(i) = ptIndex(i + 1)
                   v(i + 1) = vT
                   ptIndex(i + 1) = ptT
                End If
             End If
          Next i
       Loop
    
       cls
       print "Defense Rebounds List 1"
       GoSub PrintPlayers
    
       'Next I want to sort by the total rebounds
       FOR i = 0 TO 29
          ptIndex(i) = i
          v(i) = defenserebounds(i)
       NEXT i
       '// Sort    v(0) will hold the highest value
       fg = 1
       Do While fg = 1
          fg = 0
          FOR i = 28 To 0 Step -1
             IF v(i) < v(i + 1) THEN
                fg = 1
                '// Swap i with i + 1 //
                vT = v(i)
                ptT = ptIndex(i)
                v(i) = v(i + 1)
                ptIndex(i) = ptIndex(i + 1)
                v(i + 1) = vT
                ptIndex(i + 1) = ptT
             End If
          Next i
       Loop
    
       cls
       print "Defense Rebounds List 2"
       GoSub PrintPlayers
    
       'Finally I want to sort by the average with the highest average first.
       FOR i = 0 TO 29
          ptIndex(i) = i
          v(i) = average(i)
       NEXT i
       '// Sort    v(0) will hold the highest value
       fg = 1
       Do While fg = 1
          fg = 0
          FOR i = 28 TO 0 Step - 1
             IF v(i) < v(i + 1) THEN
                fg = 1
                '// Swap i with i + 1 //
                vT = v(i)
                ptT = ptIndex(i)
                v(i) = v(i + 1)
                ptIndex(i) = ptIndex(i + 1)
                v(i + 1) = vT
                ptIndex(i + 1) = ptT
             End If
          Next i
       loop
    
       cls
       print "Averages"
       GoSub PrintPlayers
    
    
       End
    
    PrintPlayers:
       For i = 0 to 29
          sA = playername(ptIndex(i)) + "  "
          sA = sA + Str$(playergame(ptIndex(i))) + "  "
          sA = sA + Str$(defenserebounds(ptIndex(i))) + "  "
          sA = sA + Str$(average(ptIndex(i))) + "  "
          print sA
          If i = 15 Then
             do while inkey$ = ""
             loop
          end if
       Next i
    
       do while inkey$ = ""
       loop
    
    Return
    Tim Wisseman
    [email protected]

    Leave a comment:


  • Guest's Avatar
    Guest replied
    I have tried to use Lance Edmonds' ideas in his reply but I can't get it to work. Here are the specifics:

    DIM playername$(29)
    DIM playergame(29)
    DIM defenserebounds(29)
    DIM average(29)

    The arrays are filled from 0 to 12 (total of 13 players)

    I want to print out the defensive rebounds from the highest average to the lowest average.

    First I want to sort by games in descending order as if players have the same average, I want the player with the most games to be ahead of a player with fewer games

    Next I want to sort by the total rebounds as I want the player with the most rebounds ahead of a player with the same average but with fewer rebounds.

    Finally I want to sort by the average with the highest average first.

    How do I do this. A specific example would be very helpful.

    Thanks as I have been struggling with this for almoat a month!!

    Dave

    Leave a comment:


  • Guest's Avatar
    Guest replied
    Thanks to everyone for your help!

    Leave a comment:


  • Michael Mattias
    replied
    "I want to sort a$() and tag along b$() c$() and d$()
    What is the best way to do this since the TAGARRAY
    only works with one array."

    Either use the index pointer approach earlier, OR:

    Make the array to be sorted a UDT array like:
    TYPE ControlType
    KeyValue AS STRING * 12 ' what was in A$(), to be sorted
    ElementNo AS INTEGER ' element number for a, b, c and d'
    END TYPE

    Then, sort the array using FROM ..TO...

    DIM AArray(size) AS ControlType
    ...
    ARRAY SORT AArray ,FROM 1 to 12 (no Tagarray needed)

    Now your sorted array contains the element numbers for B(), C() and D() corresponding to the sorted A().



    -------------
    Michael Mattias
    Racine WI USA
    [email protected]

    Leave a comment:


  • Lance Edmonds
    replied
    Using a sorted index approach is certainly the most efficient, but lets say you still want to sort more than two arrays. It can be accomplished in a few different ways:
    1. Use a discrete dsorting algorythm. Search the internet for "sort algorythm" and you'll probably find hundreds of examples.
    2. Use the internal ARRAY SORT technique, but it requires the use of a pair of additional numeric arrays to help us along... one to hold the master "sorted order", and another as a "work array".

    For example:
    Lets say you want to sort the "key" array a$(), and then and sort b$(), c$() and d$() (which can be considered "tagarrays"). First we create a numeric array, lets say we call it x%(), and then we fill the subscripts of x%() with the subscript number, ie:

    'Psuedo code
    DIM x%(1:NumElements%)
    For i% = 1 to NumElements%
    x%(i%) = i%
    Next i%

    Now we sort the key array, and use x%() as the tagarray, ie:

    'psuedo code
    ARRAY SORT a$(1) for NumElements%, COLLATE UCASE, TAGARRAY x%()

    At this point, x%() contains the "sorted order" of the a$() array. We can think of x%() containing the "master sort order". Now in order to sort the additional "tagarrays", we duplicate the master sort order array and perform a sort operation on it. The trick is to use one of the additional tagarrays as a tagarrays to this sort operation! (confusing, huh!)

    'PSUEDO CODE
    DIM y%(1:NumELements%)
    FOR i% = 1 to NumELements%
    y%(i%) = x%(i)
    NEXT i%
    ARRAY SORT y%(1) FOR NumElements%, TAGARRAY b$()

    At this point, we have sorted a$(), and b$() has been sorted as a tagarray. x%() continues holds the master "sorted order", so to sort yet another array, we copy the x%() array into the y%() array again, and sort the Y%() array with a tagarray again.

    'PSUEDO CODE
    DIM y%(1:NumELements%)
    FOR i% = 1 to NumELements%
    y%(i%) = x%(i)
    NEXT i%
    ARRAY SORT y%(1) FOR NumElements%, TAGARRAY c$()
    'PSUEDO CODE
    DIM y%(1:NumELements%)
    FOR i% = 1 to NumELements%
    y%(i%) = x%(i)
    NEXT i%
    ARRAY SORT y%(1) FOR NumElements%, TAGARRAY d$()

    Finally, we can erase our additional arrays, ie,
    ERASE x%(), y%()

    If we only wanted to sort one tagarray, we could use the x%() array directly, but that would be inefficient as ARRAY SORT can sort one additional tagarray directly

    Clear as mud?

    -------------
    Lance
    PowerBASIC Support
    ( mailto:[email protected][email protected]</A> )

    Leave a comment:


  • Ian Cairns
    replied
    David,

    Maybe you don't have to sort Every array to get the desired result.
    How about if you just sort one array, and an array of pointers to the data?
    Then you just have to refer to the pointer to get the data. After all,
    there's more than one way to skin your cat.
    ie:
    Code:
    cls
    dim a$(1:10), b$(1:10), c$(1:10), d$(1:10)
    dim atag%(1:10)
    FOR i% = 1 TO 10
      a$(i%) = CHR$(42+i%)
      b$(i%) = CHR$(42+i%)
      c$(i%) = CHR$(42+i%)
      d$(i%) = CHR$(42+i%)
      atag%(i%) = i%
    NEXT i%
    ARRAY SORT a$(), TAGARRAY atag%(), DESCEND
    FOR i% = 1 to 10
      PRINT aTag%(i%); a$(i%); " "; b$(aTag%(i%)); " "; d$(aTag%(i%))
    NEXT i%
    Regards, Ian Cairns

    Leave a comment:


  • Guest's Avatar
    Guest started a topic Array Sort

    Array Sort

    I want to sort 4 Arrays together
    Example:
    DIM a$(29)
    DIM b$(29)
    DIM c$(29)
    DIM d$(29)
    I want to sort a$() and tag along b$() c$() and d$()
    What is the best way to do this since the TAGARRAY
    only works with one array.
    Thanks for your help!
    Dave
Working...
X