# Sorting a 2D array on 1 dimension

Inspired by a previous question, I was looking into converting a table to a sorted list (ascending) - Resulting in this - I used a very simple bubble-sort, but I don't know how efficient that would be with larger data sets, either in records or if I wanted to sort on more than one condition. Basically, this was an exercise in using arrays when built-in excel tools would be better.

Option Explicit

Public Sub GetBids()
Dim i As Long
Dim j As Long
Dim customer As String
Dim counter As Long
Dim size As Long
Dim sortedBids As Variant
counter = 1

Dim lastRow As Long
lastRow = Cells(Rows.Count, 1).End(xlUp).Row
Dim lastColumn As Long
lastColumn = Cells(1, Columns.Count).End(xlToLeft).Column
size = WorksheetFunction.Count(Range(Cells(2, 2), Cells(lastRow, lastColumn)))

Dim arrayOfBids As Variant
ReDim arrayOfBids(1 To size, 1 To 2)
For i = 2 To lastRow
customer = Cells(i, 1)
For j = 2 To lastColumn
If Not IsEmpty(Cells(i, j)) Then
arrayOfBids(counter, 1) = Cells(i, j)
arrayOfBids(counter, 2) = customer
counter = counter + 1
End If
Next
Next

sortedBids = BubbleSort(arrayOfBids)
Range(Cells(1, 6), Cells(size, 7)) = sortedBids

End Sub

Private Function BubbleSort(ByVal arrayOfBids As Variant) As Variant
Dim temporaryArray As Variant
Dim i As Integer
ReDim temporaryArray(1 To 1, 1 To 2)

Do
For i = 1 To UBound(arrayOfBids) - 1
If arrayOfBids(i, 1) > arrayOfBids(i + 1, 1) Then
temporaryArray(1, 1) = arrayOfBids(i, 1)
temporaryArray(1, 2) = arrayOfBids(i, 2)
arrayOfBids(i, 1) = arrayOfBids(i + 1, 1)
arrayOfBids(i, 2) = arrayOfBids(i + 1, 2)
arrayOfBids(i + 1, 1) = temporaryArray(1, 1)
arrayOfBids(i + 1, 2) = temporaryArray(1, 2)
End If
Next i

BubbleSort = arrayOfBids
End Function


Overall, pretty good code. There are a couple things I would personally change though.

1 - I'd start by qualifying the references to Cells and Range even if it's assumed that everything is done with the same sheet - I'd grab a reference to ActiveSheet right at the start and use that throughout. Using a Worksheet reference inside a With block is much faster than using the global objects. Outside of the performance, it's generally a good habit to get into as it avoids using an implicit reference.

2 - The call to calculate the size of the array is a bit of overkill - there really isn't a need for a function call with:

size = WorksheetFunction.Count(Range(Cells(2, 2), Cells(lastRow, lastColumn)))


You already have all the information you need to calculate it with a simple multiplication:

size = (lastRow - 1) * (lastColumn - 1)


Excel is almost certainly doing more work to count it, because a Range object doesn't have to be rectangular.

3 - You write your array by setting the .Value of the target Range to the array, but your reads are still done inside of a loop. Not only that, but you read the same value (Cells(i, j)) from the worksheet twice here:

If Not IsEmpty(Cells(i, j)) Then
arrayOfBids(counter, 1) = Cells(i, j)


Remember, Cells(r, c) is a function call (2 actually - see #1) so you should be caching the result if the return value isn't going to change between the calls. I'd read the source Range into an array also and then iterate over that.

4 - While I'm on that section of code, the block enclosed by...

If Not IsEmpty(Cells(i, j)) Then
'...
End If


...should be indented another level.

5 - IsEmpty probably isn't the best choice (see this review) - you really just need to test that the cell isn't equal to vbNullString. Or if a zero bid is invalid, test that the cell isn't equal to 0.

6 - temporaryArray is basically being used as a tuple to store the swap values in your BubbleSort implementation. However, when you store them in an array you carry a bunch of SafeArray overhead along with it, especially since it's curiously a two dimensional array with the first dimension fixed at 1 element. A one dimensional array would be better (the runtime performs a multiply internally every time you address a cell in a 2D array). Even better would be to create a simple type to store them in:

Private Type Tuple
ItemOne As Variant
ItemTwo As Variant
End Type


7 - One small advantage that a bubble sort has is that it sorts the array in place. But..., your implementation takes the array ByVal and then just returns a copy of the sorted array when it's done. This is a huge performance hit that negates the advantage of an in-place sort. Think of it in terms of memory copies. The call sortedBids = BubbleSort(arrayOfBids) creates a copy of sortedBids in memory and then passes it to BubbleSort. The BubbleSort function then sorts the copy in place. But the copy is just a locally scoped variable, so finally you call BubbleSort = arrayOfBids which copies it again and puts it on the stack as the return value. Take advantage of possible the sole benefit of your algorithm and convert BubbleSort to a Sub that takes the array ByRef.

8 - Your counter i should be declared as a Long in BubbleSort. I'd actually consider this a bug, because the variables you use to size the array you pass it are Long. Speaking of which, you also need overflow protection in GetBids(). WorksheetFunction.Count returns a Double which it has to because the total number of possible cells in a Range is 17,179,869,184 (the maximum possible return value in your code is 17,178,804,225). This will easily overflow a Long. Granted, you won't be able to write the results if it overflows (and I shudder to think of the execution time for a bubble sort with 1,048,575 elements), but a graceful exit would be nicer than an unhandled exception.

9 - The return value of UBound(arrayOfBids) will never change inside your Do loop in BubbleSort. This value should also be cached outside of the loop - there isn't a need for repeated function calls to determine what is essentially a static value.

10 - You should swap the order of your data collection loops. Based on the sample data, the values on each row should always be increasing from left to right. This indicates that the final placement of an element in the sorted output is more strongly correlated by which column it's in instead of which row it's in. But when you're building the arrayOfBids that is eventually going to be sorted, you're building it in row order then column order. While this doesn't make as much of a difference with a bubble sort as it would with other sort algorithms, you are basically ensuring that your input to the sort will be closer to the worst case than it will to the best case. If you switch the loop order to this...

For j = 2 To lastColumn
For i = 2 To lastRow
Next
Next


...you are using this characteristic of your typical data set to make sure your sort input is closer to best case.

• Or if a zero bid is invalid, test that the cell isn't equal to 0. - that, and I think I'd go as far as taking a negative, or any bid that isn't a positive integer as an illegal value. Then you need some custom error-raising mechanism, and a nice way for your client code to handle these errors, e.g. use the exact original (string) value but write it in bold red with a flashy yellow background on the worksheet, or not - but then you have grounds for wrapping it all up in a class module and play with an object, or give it a dflt.instance and let the client code use it as a global-scope tool. – Mathieu Guindon Aug 31 '16 at 0:32
• I always mess up point 1. Thanks. As for the count, I'm accounting for any cells that don't have a bid rather than just making it the size of the possible bids, because I couldn't resize it afterwards. 7 - OH NO I SHOULD KNOW BETTER! – Raystafarian Aug 31 '16 at 11:02
• @Raystafarian - Re: the count (to borrow your phrase) "OH NO I SHOULD KNOW BETTER". You're right that I completely missed the purpose there - and empty elements at the end would all be turtles in an ascending bubble sort. – Comintern Aug 31 '16 at 15:57