fastest sorting routine for 2-D array of long values

[RB Smissaert]

What would be the fastest sorting routine (in VBA or VB) to sort a 2-D array
(2 columns only) of long values?
Maybe it has to be a non-recursive quicksort, but it is not easy at all to
find these.
If somebody has a different way to do this like with a dll that would be
fine as well.
It can't be done in a sheet as there will be more than 65536 rows.
Thanks for any advice.

RBS

 

[Tim Williams]

Disconnected ADO recordset ?
That has a sort method...

Tim

 

[RB Smissaert]

Have tried that one, but it is not the fastest one.
The sorting is very fast, but transferring the array to the
recordset and back spoils it.

RBS

 

[Helmut Weber]

Hi RB,

learn more about sorting with Howard Kaikow:

http://www.standards.com/Sorting/SortPerformanceComparison-Description.html

And, IMHO, there is no fastest sorting algorithm per se.
There may be a fastest or some equally fast algorithms
for specific data. Some seemably very fast algorithms
won't work at all if the amount of data is too high.



--
Greetings from Bavaria, Germany

Helmut Weber, MVP WordVBA

Win XP, Office 2003
"red.sys" & Chr$(64) & "t-online.de"

 

[RB Smissaert]

Thanks, will have a look.
Typically, I am dealing with arrays like this:

Dim i As Long
Dim arr(0 To 60000, 0 To 1) As Long

Randomize

For i = 0 To 60000
arr(i, 0) = CLng(Rnd() * 60000)
arr(i, 1) = i
Next

RBS

 

[Helmut Weber]

Hi "RB Smissaert",

I don't feel qualified to say more than this:

What kind of sorting is fastest
depends on the right assumptions about the data.
In real life, there are rarely data,
which don't have some kind of a structure.

If I look at the screen before me,
and if I had to sort all the pixels by color,
the assumption that after a white pixel
there would come another white pixel,
would be a good guess.
Same with grey pixels, but with a probability
not quite as high as for white pixels.
Very low probability for pink pixels.

If I knew enough about sorting,
I could choose an algorithm optimized
for that situation.

The best algorithm for perfectly randomized data,
where the number of the data is known
and the size of the data as well
depends on the amount of memory you have.
Maybe on the CPU as well.

It's very interesting, but endless.

IMHO

--
Greetings from Bavaria, Germany

Helmut Weber, MVP WordVBA

Win XP, Office 2003
"red.sys" & Chr$(64) & "t-online.de"

 

[Tom Ogilvy]

This has always been pretty fast for me and allows you to select the column
to sort on and whether ascending or descending.

Sub QuickSort(SortArray, col, L, R, bAscending)
'
'Originally Posted by Jim Rech 10/20/98 Excel.Programming
'Modified to sort on first column of a two dimensional array
'Modified to handle a second dimension greater than 1 (or zero)
'Modified to do Ascending or Descending
Dim i, j, X, Y, mm

i = L
j = R
X = SortArray((L + R) / 2, col)
If bAscending Then
While (i <= j)
While (SortArray(i, col) < X And i < R)
i = i + 1
Wend
While (X < SortArray(j, col) And j > L)
j = j - 1
Wend
If (i <= j) Then
For mm = LBound(SortArray, 2) To UBound(SortArray, 2)
Y = SortArray(i, mm)
SortArray(i, mm) = SortArray(j, mm)
SortArray(j, mm) = Y
Next mm
i = i + 1
j = j - 1
End If
Wend
Else
While (i <= j)
While (SortArray(i, col) > X And i < R)
i = i + 1
Wend
While (X > SortArray(j, col) And j > L)
j = j - 1
Wend
If (i <= j) Then
For mm = LBound(SortArray, 2) To UBound(SortArray, 2)
Y = SortArray(i, mm)
SortArray(i, mm) = SortArray(j, mm)
SortArray(j, mm) = Y
Next mm
i = i + 1
j = j - 1
End If
Wend
End If
If (L < j) Then Call QuickSort(SortArray, col, L, j, bAscending)
If (i < R) Then Call QuickSort(SortArray, col, i, R, bAscending)
End Sub




Sub aaTesterSort()
Dim bAscending As Boolean
Set rng = Range("I7").CurrentRegion
vArr = rng.Value
bAscending = False
QuickSort vArr, 5, LBound(vArr, 1), UBound(vArr, 1), bAscending
Range("I26").Resize(UBound(vArr, 1), UBound(vArr, 2)).Value = vArr
End Sub

 

[RB Smissaert]

That looks like the bog standard recursive Quicksort and I have that one. I
think I got mine from Alan Beban's website. It seems though that this sort
(2 column, 2-D array of long numbers) can be done much faster.
I got this impression from doing a search for quicksort in Visual Basic on
Planet Sourcecode.
From several postings it looks the way to do this is with a non-recursive
quicksort.
Haven't got any of the examples working yet though for 2-D arrays.

RBS

 

[RB Smissaert]

After having tried loads of different routines I think that maybe there just
isn't any routine that can do it faster
than the standard recursive quicksort.
There are lots of claims to the contrary, but either they don't work or they
are slower.
So I think yes the posted routine is the one to use, even with this
particular array.

It is a pity that there is no fast way to write an array to a ADO recordset
as that can sort very fast.
Recordset GetRows is very fast, so not sure why there is no fast method for
the opposite.

RBS