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.
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).
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...
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:
Last edited by Ellis Dee; Nov 24th, 2009 at 02:15 AM.
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