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

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

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