Question

How does one sort an array of values using a matching array of keys?

Answer

VBScript and RhinoScript do not expose procedures for sorting multiple arrays. The DotNET framework does, but only a single Key-Value pair. The algorithm outlined on this page can be easily extended to work for any number of value arrays. It is a standard implementation of the QuickSort algorithm.

QuickSort works through a Divide and Conquor approach and it's one of the fastest sorting algorithms available. However, this implementation uses the recursive approach which may result in Stack Overflow errors on large datasets. QuickSort works best on randomized arrays, if the array is already almost sorted the solution will take more steps.

This implementation comes as a collection of three procedures, but it can be easily packaged into one.

First, the big one. This is the actual recursive algorithm:

  Sub QuickSort(ByRef A(), ByRef B(), ByVal min, ByVal max)
    Dim i : i = min
    Dim k : k = max


    If (max - min) >= 1 Then
      Dim pivot : pivot = A(min)


      While (k > i)
        While (A(i) <= pivot And i <= max And k > i)
          i = i+1
        Wend


        While (A(k) > pivot And k >= min And k >= i)
          k = k-1         
        Wend        


        If (k > i) Then Call SwapElements(A, B, i, k)                   
      Wend


      Call SwapElements(A, B, min, k)
      Call QuickSort(A, B, min, k-1)
      Call QuickSort(A, B, k+1, max)
    End If
  End Sub

It depends on the SwapElement() procedure, which could have been written inline, but since it is called twice I decided to put it into a separate procedure:

  Sub SwapElements(ByRef A(), ByRef B(), ByVal i0, ByVal i1)
    Dim loc_A : loc_A = A(i0)
    Dim loc_B : loc_B = B(i0)


    A(i0) = A(i1)
    B(i0) = B(i1)
    A(i1) = loc_A
    B(i1) = loc_B
  End Sub

Finally, there's a wrapper procedure that makes calling this function slightly easier:

  Function SortByKey(ByRef Keys(), ByRef Values())
    Call QuickSort(Keys, Values, 0, Ubound(Keys))
  End Function

Contact the author