I am creating a Rhinoscript to sort surfaces based on proximity along a curve. I implemented a Bubble sort, but it is too slow. I have ~16,000 surfaces, pre-sorted into 42 “rows” of ~400. The Bubble sort takes about 2 minutes per 400 surfaces, so it would take about 84 minutes to run the script. I’d like to bring that down, thus my desire to implement a Merge or Quick sort. If anybody would be willing to help me implement a better sort algorithm, I greatly appreciate it. My script looks like this so far:

Sub SortSrfAlongCrv()
Dim arrSrf : arrSrf = Rhino.GetObjects("Select panels to sort", 8)
If IsNull(arrSrf) Then Exit Sub
Dim strCrv : strCrv = Rhino.GetObject("Select control curve", 4)
If IsNull(strCrv) Then Exit Sub
Call Rhino.Print(Time)
Call Rhino.EnableRedraw(False)
'BUBBLE SORT
Dim n : n = UBound(arrSrf) + 1
Dim newn
Dim swapped: swapped = False
Dim srf1, srf2, arrCen1, arrCen2, param1, param2
Dim temp
Dim j
Do
newn = 0
For j = 1 To UBound(arrSrf)
arrCen1 = Rhino.SurfaceAreaCentroid(arrSrf(j - 1))
arrCen2 = Rhino.SurfaceAreaCentroid(arrSrf(j))
param1 = Rhino.CurveClosestPoint(strCrv, arrCen1(0))
param2 = Rhino.CurveClosestPoint(strCrv, arrCen2(0))
'If this pair is out of order
If (param1 > param2) Then
'Swap them and remember something changed
temp = arrSrf(j)
arrSrf(j) = arrSrf(j - 1)
arrSrf(j - 1) = temp
newn = j
End If
Next
n = newn
Loop While n <> 0
'Give each surface a name based on it's material and index value
Dim i, arrCen
For i = 0 To UBound(arrSrf)
Call Rhino.ObjectName(arrSrf(i), id)
arrCen = Rhino.SurfaceAreaCentroid(arrSrf(i))
Call Rhino.AddTextDot(CStr(i), arrCen(0))
Next
Call Rhino.EnableRedraw(True)
Call Rhino.Print(Time)
End Sub

I don’t have time to write and test now (gotta get on an airplane tomorrow) but one little Python trick is that you can sort tuples by their first element and it will bring along the rest of the elements… sorta like sorting an ordered dictionary.

So the first element of each tuple could be the distance and the second element could be the surface ID. But, of course, you would have to use python.

A long time ago, I wrote a “gnome sort” for vbscript… should be faster than bubble, but it’s not the fastest either…

Function GnomeKVSort(ByVal arrK, ByVal arrV)
'Script written by Mitch Heynick
'Version November 24, 2009
'Sorts Keys (objects - arrK) by Values (numbers - arrV)
'by default lowest value will be first in output array
Dim arrVTemp,arrKTemp,i,j
i=1 : j=2
Do While i <= Ubound(arrV)
If arrV(i-1) <= arrV(i) Then 'For highest value first, change to >=
i=j : j= j+1
Else 'swap values
arrVTemp=arrV(i) : arrKTemp=arrK(i)
arrV(i)=arrV(i-1) : arrK(i)=arrK(i-1)
arrV(i-1)=arrVTemp : arrK(i-1)=arrKTemp
i=i-1 'go back one index
If i=0 Then
i=j : j=j+1
End If
End If
Loop
GnomeKVSort=arrK 'output is array of keys
End Function

I wrote this version, I think the comments although brief might be enough.
Basically I added a function I have for sorting numbers by indices.
0: make an array to get all parameters (and while calculating them anyway an array to store the centers)
1: sort the parameters array and return a new array with the indices in order.
2: go through the sorted indices and annotate the surfaces.

A short test made it appear much faster.

Call SortSrfAlongCrv()
Sub SortSrfAlongCrv()
Dim arrSrf : arrSrf = Rhino.GetObjects("Select panels to sort", 8)
If IsNull(arrSrf) Then Exit Sub
Dim strCrv : strCrv = Rhino.GetObject("Select control curve", 4)
If IsNull(strCrv) Then Exit Sub
Call Rhino.Print(Time)
Call Rhino.EnableRedraw(False)
Dim j
'create arrays for parameters and centers
Dim arrParms
ReDim arrParms(Ubound(arrSrf))
Dim arrCenters
ReDim arrCenters(Ubound(arrSrf))
Dim p
For p=0 To Ubound(arrSrf)
arrCenters(p) = Rhino.SurfaceAreaCentroid(arrSrf(p))(0)
arrParms(p) = Rhino.CurveClosestPoint(strCrv, arrCenters(p))
Next
Dim arrSortedIndices
arrSortedIndices = SortNumbersIndices(arrParms, True)
'Give each surface a name based on it's material and index value
Dim i, index , arrCen
For i = 0 To UBound(arrSortedIndices)
index = arrSortedIndices(i)
Call Rhino.ObjectName(arrSrf(index), i) 'change "id" to "i"
Call Rhino.AddTextDot(CStr(i), arrCenters(index))
Next
Call Rhino.EnableRedraw(True)
Call Rhino.Print(Time)
End Sub
Function SortNumbersIndices(ByVal arrNumbers, blnAscending)
'function sorts numbers and returns an array with the indices of the sorted numbers
Dim arrRef : arrRef = Rhino.SortNumbers(arrNumbers, blnAscending)
Dim UB : UB = Ubound(arrNumbers)
Dim arrSorted : ReDim arrSorted(UB)
Dim i,j
For i=0 To UB
For j=0 To UB
If Not IsNull(arrNumbers(j)) And Not IsNull(arrRef(i)) Then
If arrRef(i) = arrNumbers(j) Then
arrSorted(i) = j
arrNumbers(j) = Null
arrRef(i) = Null
End If
End If
Next
Next
SortNumbersIndices = arrSorted
End Function

So I started with Willem’s code, since it was the most explicit. (FYI, to format your code, three forward ticks (`) then vbscript or python, then your code, then three more ticks at the end of your code.)

One row (~400 surfaces) runs very quickly. So far, so good! Thank you, Willem.

I’m integrating this into my larger script and report back.

So I think I’ve got it working, but as I’m running it I’m finding that it slows down. I’ve sorted the surfaces into rows, then I’m sorting each row sequentially. The first row took ~1 second to run, the 30th row took ~1m45s to run.

Any thoughts? I don’t know enough about memory management, but intuitively that’s what I think I need to address.