Fastest way to sort large 2-D arrays?

R

RB Smissaert

Tom,

I had worked it out now.
The VSORT.IDX function does the trick.
This is my wrapper function for this now and it works fine:


Function VSORT_IDX_Array(ByRef arr As Variant, _
ByVal btCol1 As Byte, _
ByVal strSortType1 As String, _
Optional ByVal btCol2 As Byte = 0, _
Optional ByVal strSortType2 As String = "", _
Optional ByVal btCol3 As Byte = 0, _
Optional ByVal strSortType3 As String = "") As
Variant

'------------------------------------------------------------------
'http://longre.free.fr/english/
'Uses Laurent Longre's VSORT.IDX function in the .xll add-in MoreFunc
'Done up to 3 columns here, but can be done up to 14 columns
'------------------------------------------------------------------
'will sort an 0-based or 1-based 2-D array with up to 3 sort keys
'the field key has to be supplied as a byte, where the first column
'of the array is 1, even if it is an 0-based array
'the sort type has to be given as "a", "A" , "b" or "B"
'examples:
'sorting on 1 field: arr2 = VSORT_IDX_Array(arr, 1, "A")
'sorting on 2 fields: arr2 = VSORT_IDX_Array(arr, 2, "D", 5, "A")
'------------------------------------------------------------------

Dim i As Long
Dim c As Long
Dim LB1 As Long
Dim UB1 As Long
Dim LB2 As Long
Dim UB2 As Long
Dim arrKey1
Dim arrKey2
Dim arrKey3
Dim btSortType1 As Byte
Dim btSortType2 As Byte
Dim btSortType3 As Byte
Dim arrIndex
Dim arrFinal

LB1 = LBound(arr)
UB1 = UBound(arr)
LB2 = LBound(arr, 2)
UB2 = UBound(arr, 2)

ReDim arrFinal(LB1 To UB1, LB2 To UB2)

'make the array for key 1
'------------------------
ReDim arrKey1(LB1 To UB1, LB1 To LB1)
For i = LB1 To UB1
arrKey1(i, LB1) = arr(i, btCol1 - (1 - LB1))
Next

'set the sort type for key 1
'---------------------------
If UCase(strSortType1) = "A" Then
btSortType1 = 1
Else
btSortType1 = 0
End If

If Not btCol2 = 0 Then
'make the array for key 2
'------------------------
ReDim arrKey2(LB1 To UB1, LB1 To LB1)

For i = LB1 To UB1
arrKey2(i, LB1) = arr(i, btCol2 - (1 - LB1))
Next

'set the sort type for key 2
'---------------------------
If UCase(strSortType2) = "A" Then
btSortType2 = 1
Else
btSortType2 = 0
End If
End If

If Not btCol3 = 0 Then
'make the array for key 3
'------------------------
ReDim arrKey3(LB1 To UB1, LB1 To LB1)
For i = LB1 To UB1
arrKey3(i, LB1) = arr(i, btCol3 - (1 - LB1))
Next

'set the sort type for key 3
'---------------------------
If UCase(strSortType3) = "A" Then
btSortType3 = 1
Else
btSortType3 = 0
End If
End If

If Not btCol3 = 0 Then
'3 fields to sort on
'-------------------
arrIndex = Application.Run([VSORT.IDX], _
arrKey1, btSortType1, _
arrKey2, btSortType2, _
arrKey3, btSortType3)
Else
'2 fields to sort on
'-------------------
If Not btCol2 = 0 Then
arrIndex = Application.Run([VSORT.IDX], _
arrKey1, btSortType1, _
arrKey2, btSortType2)
Else
'1 field to sort on
'------------------
arrIndex = Application.Run([VSORT.IDX], _
arrKey1, btSortType1)
End If
End If

For i = LBound(arrIndex) To UBound(arrIndex)
For c = LB2 To UB2
arrFinal(i - (1 - LB1), c) = arr(arrIndex(i, 1) - (1 - LB1), c)
Next
Next

VSORT_IDX_Array = arrFinal

End Function

Just looking at this, perhaps I might as well use the VSORT function as I
have to transfer the array
now anyhow. If I use the VSORT I can avoid doing the array transfer if a
1-based array was given, thereby
speeding this up a bit.
I think the speed gain is not 4 to 5 times as my test was not up to scratch.
Seems more like 50% faster.
Still, it is easy to sort on multiple fields.


RBS
 
R

RB Smissaert

This will be faster if it is a 1-based array:


Function VSORTArray(ByRef arr As Variant, _
ByVal btCol1 As Byte, _
ByVal strSortType1 As String, _
Optional ByVal btCol2 As Byte = 0, _
Optional ByVal strSortType2 As String = "", _
Optional ByVal btCol3 As Byte = 0, _
Optional ByVal strSortType3 As String = "") As Variant

'------------------------------------------------------------------
'http://longre.free.fr/english/
'Uses Laurent Longre's VSort function in the .xll add-in MoreFunc
'Will be about 4 to 5 times faster than a quicksort and can sort
'on multiple columns.
'Done up to 3 columns here, but can be done up to 14 columns
'------------------------------------------------------------------
'will sort an 0-based or 1-based 2-D array with up to 3 sort keys
'the field key has to be supplied as a byte, where the first column
'of the array is 1, even if it is an 0-based array
'the sort type has to be given as "a", "A" , "b" or "B"
'examples:
'sorting on 1 field: arr2 = VSORTArray(arr, 1, "A")
'sorting on 2 fields: arr2 = VSORTArray(arr, 2, "D", 5, "A")
'------------------------------------------------------------------

Dim i As Long
Dim c As Long
Dim LB1 As Long
Dim UB1 As Long
Dim LB2 As Long
Dim UB2 As Long
Dim arrKey1
Dim arrKey2
Dim arrKey3
Dim btSortType1 As Byte
Dim btSortType2 As Byte
Dim btSortType3 As Byte
Dim arrFinal
Dim arrFinal2

LB1 = LBound(arr)
UB1 = UBound(arr)
LB2 = LBound(arr, 2)
UB2 = UBound(arr, 2)

'make the array for key 1
'------------------------
ReDim arrKey1(LB1 To UB1, LB1 To LB1)
For i = LB1 To UB1
arrKey1(i, LB1) = arr(i, btCol1 - (1 - LB1))
Next

'set the sort type for key 1
'---------------------------
If UCase(strSortType1) = "A" Then
btSortType1 = 1
Else
btSortType1 = 0
End If

If Not btCol2 = 0 Then
'make the array for key 2
'------------------------
ReDim arrKey2(LB1 To UB1, LB1 To LB1)

For i = LB1 To UB1
arrKey2(i, LB1) = arr(i, btCol2 - (1 - LB1))
Next

'set the sort type for key 2
'---------------------------
If UCase(strSortType2) = "A" Then
btSortType2 = 1
Else
btSortType2 = 0
End If
End If

If Not btCol3 = 0 Then
'make the array for key 3
'------------------------
ReDim arrKey3(LB1 To UB1, LB1 To LB1)
For i = LB1 To UB1
arrKey3(i, LB1) = arr(i, btCol3 - (1 - LB1))
Next

'set the sort type for key 3
'---------------------------
If UCase(strSortType3) = "A" Then
btSortType3 = 1
Else
btSortType3 = 0
End If
End If

If Not strSortType3 = "" Then
'3 fields to sort on
'-------------------
arrFinal = Application.Run([VSORT], arr, _
arrKey1, btSortType1, _
arrKey2, btSortType2, _
arrKey3, btSortType3)
Else
'2 fields to sort on
'-------------------
If Not strSortType2 = "" Then
arrFinal = Application.Run([VSORT], arr, _
arrKey1, btSortType1, _
arrKey2, btSortType2)
Else
'1 field to sort on
'------------------
arrFinal = Application.Run([VSORT], _
arr, arrKey1, btSortType1)
End If
End If

If LB1 = 0 Then
'to revert back to an 0-based array
'----------------------------------
ReDim arrFinal2(LB1 To UB1, LB2 To UB2)
For i = LBound(arrFinal) To UBound(arrFinal)
For c = LBound(arrFinal, 2) To UBound(arrFinal, 2)
arrFinal2(i - (1 - LB1), c - (1 - LB2)) = arrFinal(i, c)
Next
Next
VSORTArray = arrFinal2
Else
VSORTArray = arrFinal
End If

End Function

One thing I noticed that the number of rows in the array to sort can't go
above 65536, the number of rows in the sheet.
It seems that these functions are geared towards sheet ranges (always
produce 1-based arrays, limit of 65536 rows)
even though they can be used for arrays. The benefit speedwise would come
into play with arrays larger than this, unless maybe you have slow hardware.
The main benefit though is that you can sort on multiple fields.


RBS
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Problem sorting 2-D array 1
Combine 2 codes from WorkSheet_Change & WorkSheet _SelectionChange to ONLY WorkSheet_Change 2
Pasting large arrays onto worksheet 0
Stuck with problem - looking for help 2
How to force column formatting (text, date, etc) when loading a fixed width text file into an array? 3
Foolproof way to add ADO reference 22
Redimming an array dynamically assigned from range (how to redim first dimension of a 2-D array? /or 3
Bug in my code 5

Top