Results 1 to 8 of 8

Thread: [RESOLVED] Sort UDT array

  1. #1

    Thread Starter
    Lively Member
    Join Date
    Oct 2007
    Posts
    126

    Resolved [RESOLVED] Sort UDT array

    Can you recommend an algorithm or idea on how to sort a UDT array with a max. of several hundred elements? The array needs to be sorted on one of the values in the type, which is a long, and contains duplicates.

  2. #2
    Cumbrian Milk's Avatar
    Join Date
    Jan 2007
    Location
    0xDEADBEEF
    Posts
    2,448

    Re: Sort UDT array

    Have a look at this fine thread.
    W o t . S i g

  3. #3

    Thread Starter
    Lively Member
    Join Date
    Oct 2007
    Posts
    126

    Re: Sort UDT array

    It is a fine thread, but I was too lazy to get to work on it...

    I'll try implementing the merge sort.

  4. #4
    PowerPoster Code Doc's Avatar
    Join Date
    Mar 2007
    Location
    Omaha, Nebraska
    Posts
    2,354

    Re: Sort UDT array

    If you only have a few hundred elements, the age-old bubble sort would work fine as shown in Milk's link. Simply sort on the crucial variable and carry the other array elements in the UDT with it as baggage. The insertion sort is also very simple and fast (and so is my jump sort).
    Doctor Ed

  5. #5
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: Sort UDT array

    I always use Comb sort to sort udt arrays because it combines speed/efficiency with ease of use for the programmer. Comb sort is plenty fast enough to sort udt arrays of thousands of elements. Once you get past ten thousand elements I would probably switch over to quicksort.

    Here's a generic template for you to play with. I've highlighted everywhere you need to make a change. (The name of the udt type definition and the element you want to compare.)
    Code:
    Public Sub SortUDT(ByRef ptypArray() As MyType)
        Const ShrinkFactor = 1.3
        Dim lngGap As Long
        Dim i As Long
        Dim iMin As Long
        Dim iMax As Long
        Dim typSwap As MyType
        Dim blnSwapped As Boolean
        
        iMin = LBound(ptypArray)
        iMax = UBound(ptypArray)
        lngGap = iMax - iMin + 1
        Do
            If lngGap > 1 Then
                lngGap = Int(lngGap / ShrinkFactor)
                If lngGap = 10 Or lngGap = 9 Then lngGap = 11
            End If
            blnSwapped = False
            For i = iMin To iMax - lngGap
                If ptypArray(i).Element > ptypArray(i + lngGap).Element Then
                    typSwap = ptypArray(i)
                    ptypArray(i) = ptypArray(i + lngGap)
                    ptypArray(i + lngGap) = typSwap
                    blnSwapped = True
                End If
            Next
        Loop Until lngGap = 1 And Not blnSwapped
    End Sub
    As you can see, it's super simple to tailor comb sort to any given udt. If you want to sort on multiple fields, the easiest and fastest executing way to go is simply create multiple copies of the algorithm named something like SortByName() and SortByCost(). Comb sort is small enough to make this manageable, unlike a more complex algorithm like merge sort where the code sprawl would quickly become overpowering.

    Another alternative if you want to be able to sort on multiple different fields is to create a comparison function that does the actual comparisons. Let me see if I can dig up an example I've used...

  6. #6
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: Sort UDT array

    Found the implementation I was thinking of. I'm happy to answer questions about what's going on if you have any.

    Note that I needed these sorts to be stable. Because the lists were always <1000 elements I went with insertion sort, mainly because I dislike the code sprawl of merge sort. And I could never live with myself using bubble sort. (Those are basically the only three stable algorithms.)
    Code:
    Option Explicit
    Option Compare Text
    
    Public Type TroopType
        TroopID As Long
        Troops As Long
        TroopsURL As String
        UnitType As String
        UnitDisplay As String
        Distance As Double
        Player As String
        PlayerIndex As Long
        PlayerURL As String
        Alliance As String
        AllianceURL As String
        Hide As Boolean
        Clicked As Boolean
        Hero As String
        HeroSort As Long
    End Type
    
    Public Sub SortTroopList(ptyp() As TroopType, plngOrder As Long)
        Dim i As Long
        Dim j As Long
        Dim iMin As Long
        Dim iMax As Long
        Dim typSwap As TroopType
        
        iMin = LBound(ptyp) + 1
        iMax = UBound(ptyp)
        For i = iMin To iMax
            typSwap = ptyp(i)
            For j = i To iMin Step -1
                If Compare(ptyp(j - 1), typSwap, plngOrder) = 1 Then ptyp(j) = ptyp(j - 1) Else Exit For
            Next j
            ptyp(j) = typSwap
        Next i
    End Sub
    
    Public Function Compare(ptyp1 As TroopType, ptyp2 As TroopType, plngOrder As Long) As Integer
        Dim var1 As Variant
        Dim var2 As Variant
        
        Select Case plngOrder
            Case 1 ' Troops
                var1 = ptyp1.Troops
                var2 = ptyp2.Troops
            Case 2 ' Distance
                var1 = ptyp1.Distance
                var2 = ptyp2.Distance
            Case 4 ' Unit
                var1 = ptyp1.UnitDisplay
                var2 = ptyp2.UnitDisplay
            Case 5 ' Player
                var1 = ptyp1.Player
                var2 = ptyp2.Player
            Case 6 ' Alliance
                var1 = ptyp1.Alliance
                var2 = ptyp2.Alliance
        End Select
        Select Case var1
            Case Is < var2: Compare = -1
            Case Is > var2: Compare = 1
            Case Else: Compare = 0
        End Select
    End Function
    (This code is part of a program I wrote for playing Travian. Specifically, managing the troops in a World Wonder.)

    EDIT: The reason I needed the sorting to be stable is to allow the user to sort on multiple columns. Imagine a multi-column listview or grid where you click a column header to sort by that column. It was desirable to be able to sort by, for example, Player then Troop Type. To achieve this I just used a stable algorithm so the user could click Troop Type then Player and be done with it.

    I didn't actually use a grid, but instead used a bunch of label control arrays (one array per column) and a scrollbar inside a picturebox so I could have complete control over the display. This let me turn each datapoint into a hotlink you could click to "open" the detail on that set of troops. I only explain this as an excuse to include this screen shot:
    Attached Images Attached Images  
    Last edited by Ellis Dee; Nov 24th, 2009 at 02:15 AM.

  7. #7

    Thread Starter
    Lively Member
    Join Date
    Oct 2007
    Posts
    126

    Re: Sort UDT array

    Beautiful! Works like a charm.

  8. #8
    New Member
    Join Date
    Jun 2018
    Posts
    1

    Re: Sort UDT array

    Ellis, This post is still very current. It provides a lot of solid and helpful information. This is typical of a role model.
    Question: I have a UDT that is not a flat UDT, it has layers. See below. Using your sort algorithm, how do I sort by a field that is not in the UDT Upper layer? Let's say PageId. Many thanks!

    Public Type typPointersTexts (Upper layer)
    typPointer As typPointers
    typPresentText As typPresentTexts
    strSequenceId As String
    End Type

    Public Type typPointers (lower layer)
    strPageId As String
    strShapeId As String
    End Type

    Public Type typPresentTexts (lower layer)
    strSourceText As String
    strTargetText As String
    End Type

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width