Sorting arrays in parallel
January 8, 2010 • JP • 6 Comments • Rate This Article
You have two arrays:
place horses name
3 bob
2 leo
4 kendon
1 hippo
5 dad
How do you sort the "place" array so the numbers are in order, while maintaining "horse" reference integrity? In other words, how do I sort these arrays in parallel?
Answer:
You need two sort routines:
- A selection sort to grab the lowest number in an unsorted list and move it into the first position.
- A swap routine that switches the position of two array elements in a given array.
The function to do the selection sort is courtesy of Rod Stephen's VB Helper site. (FYI: Visit his site for a ton of sample VB/VBA code.)
The two elements of the array to be switched in the swap routine are:
- list(itemToBeMoved) – the position of the item you want to move
- list(newPosition) – the position the item should be moved to
The swap routine will need to be called after the selection sort, since that's when we'll know which two elements in the first array are being switched. We'll use a Variant to make the swap, so we can work with both strings and numbers.
So for example, in the first iteration, the selection sort will move the number 1 (third position) to the first position in the array.
itemToBeMoved = 3
newPosition = 0
(Remember that arrays are zero-based, so 0 is the first position.)
So the swap sort routine would be called with the second array and the numbers 0 and 3. The array items at positions 0 and 3 in the second array would be swapped. Since this corresponds with the swapping being done in the first array, the two arrays will be sorted in parallel.
For the sake of argument, we'll assume that the arrays are of equal size. For demonstration purposes, we'll print their values before and after sorting.
On Error GoTo ErrorHandler
Dim arr1 As Variant
Dim arr2 As Variant
Dim i As Long
arr1 = Array(3, 2, 4, 1, 5)
arr2 = Array("bob", "leo", "kendon", "hippo", "dad")
' assume arrays are same size
' show arrays before sorting
For i = LBound(arr1) To UBound(arr1)
Debug.Print arr1(i)
Next i
For i = LBound(arr2) To UBound(arr2)
Debug.Print arr2(i)
Next i
' sort the arrays together
Call ParallelSort(arr1, arr2)
' show arrays after sorting
For i = LBound(arr1) To UBound(arr1)
Debug.Print arr1(i)
Next i
For i = LBound(arr2) To UBound(arr2)
Debug.Print arr2(i)
Next i
ProgramExit:
Exit Function
ErrorHandler:
MsgBox Err.Number & " - " & Err.Description
Resume ProgramExit
End Sub
ParallelSort is a wrapper function that merely passes the arrays into Selectionsort. The first array (mainArray) is the primary array you want to sort. shadowArray is the secondary array that you want sorted in parallel with the primary array.
Selectionsort combs the array for the next lowest value and moves it to the top of the list. (For a fuller explanation, visit Rod's site.) After the smallest value is moved to the top of the list, the swap sort function is called, and the corresponding values in the second array are switched.
ByRef shadowArray As Variant)
Call Selectionsort(mainArray, shadowArray, _
LBound(mainArray), UBound(mainArray))
End Function
Function Selectionsort(firstArray As Variant, secondArray As Variant, _
min As Long, max As Long)
' from http://www.vb-helper.com/tut1.htm
Dim i As Long
Dim j As Long
Dim best_value As Long
Dim best_j As Long
For i = min To max - 1
best_value = firstArray(i)
best_j = i
For j = i + 1 To max
If firstArray(j) < best_value Then
best_value = firstArray(j)
best_j = j
End If
Next j
firstArray(best_j) = firstArray(i)
firstArray(i) = best_value
Call SwapSort(secondArray, best_j, i)
Next i
End Function
Function SwapSort(ByRef arr As Variant, IndexToBeMoved As Long, _
IndexNewPosition As Long)
' swap values stored in array
Dim tempVal As Variant
tempVal = arr(IndexNewPosition)
arr(IndexNewPosition) = arr(IndexToBeMoved)
arr(IndexToBeMoved) = tempVal
End Function
VBA ·
Rate This Article:
(No Ratings Yet)
Loading ...What now?
Subscribe To The Blog
Email This Article
Follow Me On Twitter
My Facebook Page
Or just keep reading:
I'm just an average guy who writes VBA code for a living. This is my personal blog. Excel and Outlook are my thing, with a sprinkle of Access and Word here and there. Follow this space if you want to learn more about VBA. Keep Reading »
Previous Post: Major blog/site changes
Next Post: Are classic Office 2003 menus already making a comeback?
This is very similar to routines that sort 2D arrays.
To make the functioning of the code more obvious (i.e., you're swapping the same pairs in each array), you might take out the swap sort that's embedded in the Selection Sort routine, and call the Swap Sort routine for both arrays:
min As Long, max As Long)
' from http://www.vb-helper.com/tut1.htm
Dim i As Long
Dim j As Long
Dim best_j As Long
For i = min To max - 1
best_value = firstArray(i)
best_j = i
For j = i + 1 To max
If firstArray(j) < best_value Then
best_j = j
End If
Next j
SwapSort firstArray, best_j, i
SwapSort secondArray, best_j, i
Next i
End Function
Good point, I posted the procedure almost verbatim to avoid messing it up (I can only understand my own use of i and j variables).
This is one of the reasons I find it so hard to code with VBA today, after having worked with .Net. In C#, I would write something like this:
{
public string Name
{ get; set;}
public int Position
{ get; set; }
public string Owner
{get; set; }
public static void SortList()
{
var horse1 = new HorseRace() {Name = "Alpha", Position = 1, Owner = "Joe"};
var horse2 = new HorseRace() {Name = "Bravo", Position = 3, Owner = "Joe"};
var horse3 = new HorseRace() {Name = "Charlie", Position = 2, Owner = "Bill"};
var list = new List<HorseRace>() {horse1, horse2, horse3};
var sorted = from horse in list orderby horse.Position select horse;
}
}
I think it's much better for 2 reasons. First, VBA forces you to solve the wrong problem: you should not sort 2 separate arrays, conceptually you should be sorting one unique array of whatever you want to sort, on whatever criterion you chose. Then, in this day and age, you should not have to re-write a sort yourself, unless you are doing something really special – especially because you will likely not pick the best implementation of the algorithm…
It's easier in .NET because you use classes. VBA doesn't require you to do so. If we used a class instead, it could be done in VBA the same way you do it in C#. Unfortunately there's no built-in equivalent to Array.Sort in VBA (like you would find in Java, for instance).
I guess it's all a question of perspective – I would have said, "using classes in VBA isn't quite pleasant", rather than "VBA doesn't require classes"
– and yes, the fact that sorting is built-in in .Net, like Java, is icing on the cake!