Announcement

Collapse
No announcement yet.

Array Sort

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

  • 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

  • #2
    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
    :) IRC :)

    Comment


    • #3
      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> )
      Lance
      mailto:[email protected]

      Comment


      • #4
        "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]
        Michael Mattias
        Tal Systems Inc. (retired)
        Racine WI USA
        [email protected]
        http://www.talsystems.com

        Comment


        • #5
          Thanks to everyone for your help!

          Comment


          • #6
            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

            Comment


            • #7
              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]

              Comment


              • #8
                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

                Comment


                • #9
                  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> )
                  Lance
                  mailto:[email protected]

                  Comment


                  • #10
                    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]
                    Michael Mattias
                    Tal Systems Inc. (retired)
                    Racine WI USA
                    [email protected]
                    http://www.talsystems.com

                    Comment

                    Working...
                    X