A set of Excel/VBA procedures that can be used to parse a Matrix into a List.Using Excel Range Names to Parse a Matrix
Background for this Enhanced Insertion Sort Routine
The procedure was first written in FORTRAN when I worked for Grumman Aerospace.
I was introduced to the insertion sort by my mentor Francis J. Nolan. He told me that he had to compose the algorithm for a job interview.
As I was coding the algorithm I realized that the procedure would have a much broader application if it were written to generate a permutation array which could then be applied as a sort operator.
I made use of this algorithm, which I named AORDER, during my entire carrier at Grumman.
Now that I am a Senior Excel VBA Developer, I started to refractor a number of my FORTRAN codes.
As I began work I realized that just converting FORTRAN to VBA would not be the complete answer.
I saw that the all the refactored routines needed to deal with Arrays for both input and output.
In the context of Excel, the ultimate input and output would be to spreadsheet Ranges, but there would be many circumstances when the output array from one process would be passed directly to another procedure without having to cycle back to a spreadsheet .
An Enhanced VBA Insertion Sort Procedure
The basic insertion sort algorithm is very direct.
Given a partial list of values which are sorted the algorithm seeks to add a new value to the sorted list.
This task takes two steps:
- Search over the sorted list to determine where the new value belongs.
- Split the sorted list to make room for the new value.
These two steps are repeated until the entire list of data values is sorted.
The essential features of this procedure are:
- It generates a stable sort which keeps elements that have the same value in the same order as they were in the original list. The Excel Spreadsheet Sort is a stable sort.
- It generates a permutation array which can be applied as a sorting operator. The original data is unchanged. This resulting sorting operator can be used to generate compound sort operators.
A number of operational tweaks have been made to enhance the performance of the sorting process:
- The procedure is presented as two distinct subroutines, one for Hi_To_Lo sorting and another for Lo_To_Hi The benefit of this modification lets the algorithm to keep track of the latest inserted value and its location in the permutation array.
This information facilitates the search for the next insertion location. Instead of having to search over the entire list of sorted values, it can search from either the minimum to the latest or from the latest to the maximum.
- The storage for the permutation array is initially set to double the size of the values array. By starting the permutation array in the middle, the permutation array can be split by moving the shortest part, moving the permutation down below the insertion point or moving the permutation up above the insertion point.
One set of routines are required for sorting strings and another for sorting numerical values.
I refer to this suite of Numerical Techniques as an Engineer’s Tool Kit for practical and empirical Numerical Analysis.
How the Toolkit came to be.
- I want my mathematics to be intuitive.
- I want to see it.
- I want to understand it.
- I want to own it.
- When applying curve fitting to physical data, knowing the theoretical behaviors does not make the error terms in the curve fit any smaller than if you did not know the theoretical behavior.
- This then led me to focus the local behavior of a curve.
- Focusing on three points at a time while sliding over the extent of the curve.
- stacking the deck to facilitate the desired outcome is right and proper attitude for practical numerical techniques.
- Statement Functions in FORTRAN are cool.
The three seeds that formed the foundation of the Toolkit:
- A paper on Aitken’s Graphical Analog for Constructing Lagrange Polynomials
- A drafting textbook describing how a carpenter can measure arc length
- While reading textbooks on numerical analysis – there are always long glowing chapters on integration touting how averaging is the key to good results. While the very next chapter on differentiation is short and the author always advises the reader not to get involved. This led me to consider the possibility of incorporating an averaging technique into a process for numerical differentiation.