Site Tools


Key-Value Pair QuickSort Algorithm

Developer: RhinoScript
Summary: How to sort multiple arrays using a Key list.

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


developer/quicksortkeyvaluepair.txt ยท Last modified: 2016/01/25 by sandy