Re: sort 1-D array of doubles for Olaf Schmidt

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

Mike,

Thanks for the reply, but I have no problem with the idea of the lookup array or index array or whatever you call it, but I just wanted to alter Olaf's code so that it would handle a 1-D array of doubles rather than a 1-D array of strings.
Let me know if I misunderstood something.

RBS


"Mike D Sutton" <EDais@xxxxxxxx> wrote in message news:eZTXMKHjGHA.4040@xxxxxxxxxxxxxxxxxxxxxxx
A few weeks Olaf Schmidt posted a VB6 routine to sort a 1-D array of strings very fast indeed.
This was in the thread: fastest way to change case of string.
Now I wonder if I could use this code to sort a variant 2-D array where the sorting columns holds
long numbers only.

My idea is as follows:
Make a 1-D array of doubles from the sort column holding long numbers, concatenated with the
index of these long numbers in that 2-D array, so for example:
<snip>
It seems sorting an array of doubles this way should be simpler, but I haven't worked
it out yet. Thanks for any assistance.

You would use a lookup array in this situation, which is simply an array of longs which hold the indexes of the data. At first you populate the array with the original indices into the data (1 - x), then in your sort you use the value in this index array to lookup into the original data array to get its corresponding value. In this way you never touch the original data array and only manipulate the lookup array of longs, which is a _lot_ faster.
If you want to store the original data array sorted then you would simply re-build the data array once after having built the lookup array.
Here's a quick example:

'***
Private Type typMyData
mdIndex As Long
mdDouble As Double
mdString As String
End Type

Private MySimpleArr(0 To 2) As typMyData

Private Sub Form_Load()
Dim IndexList() As Long
Dim LoopData As Long

' Create some sample data
MySimpleArr(0) = NewMyData(0, 1.5, "Bbb")
MySimpleArr(1) = NewMyData(1, 2, "Aaa")
MySimpleArr(2) = NewMyData(3, 1, "Ccc")

' Get sorted index list
IndexList = GetDoubleSort()

' Print sorted data to debug window
For LoopData = LBound(MySimpleArr()) To UBound(MySimpleArr())
With MySimpleArr(IndexList(LoopData))
Debug.Print CStr(LoopData) & " = Index: " & _
CStr(.mdIndex) & ", Double: " & _
CStr(.mdDouble) & ", String: " & .mdString
End With
Next LoopData
End Sub

Private Function NewMyData(ByVal inIndex As Long, _
ByVal inDouble As Double, ByVal inString As String) As typMyData
With NewMyData ' Simple UDT constructor
.mdIndex = inIndex
.mdDouble = inDouble
.mdString = inString
End With
End Function

Private Function GetDoubleSort(Optional ByVal inDescending As Boolean = False) As Long()
Dim RetIndex() As Long
Dim LoopIndex As Long
Dim ArrLow As Long, ArrHigh As Long
Dim TempSwap As Long
Dim Sorted As Boolean
Dim SwapPair As Boolean

ArrLow = LBound(MySimpleArr())
ArrHigh = UBound(MySimpleArr())

' Allocate and build initial index list
ReDim RetIndex(ArrLow To ArrHigh) As Long
For LoopIndex = ArrLow To ArrHigh
RetIndex(LoopIndex) = LoopIndex
Next LoopIndex

Do
Sorted = True

For LoopIndex = ArrLow To ArrHigh - 1
If (inDescending) Then ' Work out whether these two need swapping
SwapPair = MySimpleArr(RetIndex(LoopIndex)).mdDouble < _
MySimpleArr(RetIndex(LoopIndex + 1)).mdDouble
Else
SwapPair = MySimpleArr(RetIndex(LoopIndex)).mdDouble > _
MySimpleArr(RetIndex(LoopIndex + 1)).mdDouble
End If

If (SwapPair) Then ' Swap these two
TempSwap = RetIndex(LoopIndex)
RetIndex(LoopIndex) = RetIndex(LoopIndex + 1)
RetIndex(LoopIndex + 1) = TempSwap
Sorted = False ' Flag as potentially still unsorted
End If
Next LoopIndex
Loop Until Sorted

' Return index list
GetDoubleSort = RetIndex
End Function
'***

It creates a basic array of some UDTs containing various data, then uses the GetDoubleSort() call to create an index list for the data array sorted by its mdDouble field - Note that the data array is never manipulated which makes it fast. Here I'm just using a simple bubble sort, however you can plug your own routine in there to perform the actual sorting of the data.
Hope this helps,

Mike


- Microsoft Visual Basic MVP -
E-Mail: EDais@xxxxxxxx
WWW: Http://EDais.mvps.org/


.

Relevant Pages

  • Re: sort 1-D array of doubles for Olaf Schmidt
    ... Now I wonder if I could use this code to sort a variant 2-D array where the sorting columns holds ... original data array and only manipulate the lookup array of longs, ... Dim IndexList() As Long ...
    (microsoft.public.vb.general.discussion)
  • Re: Kicking bindings to refresh a NSTableView
    ... > I have a minimal app with an NSTableView whose NSTableColumns have ... > However, if I unarchive the data array from disk, the table isn't ... provided you trigger the binding mechanism by ...
    (comp.sys.mac.programmer.help)
  • Re: Proper way to use array
    ... > array data, but provide the necessary access functions in the class. ... I suppose there's no speed cost to having an "oversized" array floating ... of course with the index i can easily redim after filling if i still feel ... > only contains an index that refers to the data array) and a freelist array ...
    (microsoft.public.vb.general.discussion)
  • Re: problem with AVI getframe modify pixels and display
    ... > Thanks to you Mike I can now change the avi frame pixels and display ... This method is _faster_ than creating a DIBSection since you're just pointing to the data rather than having to move it about. ... you're after more speed then a single dimensional array is quicker to access than a multi-dimensional array, and if you can get back ... a 32-bit image then using a data array of DWords is again faster than a byte array however at that point you're starting to count ...
    (microsoft.public.vb.winapi.graphics)
  • Re: Detecting a running process.
    ... Private Declare Function EnumProcessModules Lib "psapi.dll" _ ... (ByVal dwProcessID As Long, _ ... Dim nProcesses As Long ... 'fill an array of longs with the ...
    (microsoft.public.vb.winapi)