Author: excel1star

Senior Excel VBA Automation Developer. Ex Aerospace Engineer with Grumman Aerospace

Sorting in VBA using VBA-ADO

Several months ago I re-published my Code for an Enhanced Insertion Sort Algorithm.

At that point, my colleague SNB wrote to tell me about other methods that could be applied to achieve the same results.

SNB is the owner of a very valuable Web Site: VBA for Smarties

http://www.snb-vba.eu/

In particular, check out his great tutorial on VBA Arrays

http://www.snb-vba.eu/VBA_Arrays_en.html

He evaluated my code and provided a much simpler solution using

VBA-ADO Library which has a sorting method.

I am republishing the improved VBA project to provide a hands-on demonstration that presents the hard way and the easy way to sort using VBA.

SNB’s code is very efficient and direct, one routine for sorting numerical values and another one for sorting string. Each routine has 30 lines of code!

My code, on the other hand, has two routines for sorting numerical values and two routines for sorting strings along with a number of supporting routines. All in all, my codes require nearly 900 lines of code.

I have included a tab in the Workbook to demonstrate that our results match the stable sorting that is provided by the Worksheet sorting.

I want to point out that our sorting procedures are stable. Meaning that as the sorting is progressing through the original data, that the position of each new data item that is added to the sorted collection maintains its relative position to where it was in the original data.

I also want to underscore the importance that I give generating a permutation array to act as a sorting operator.
Based on what I have learned from SNB, I will be using his code as I continue the development of my Tool Kit of Numerical Techniques.

Link to the Workbook:

https://drive.google.com/open?id=0BxNZW5nboqyIaHlJdW9jQTF5d28

Other important references:

Stable Sorting:

https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Click to access stability.pdf

Insertion Sorting:

https://en.wikipedia.org/wiki/Insertion_sort

http://www.geeksforgeeks.org/insertion-sort/

https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm

Permutations for Sorting:

https://rosettacode.org/wiki/Sorting_algorithms/Permutation_sort

Click to access 06-Maus.pdf

Click to access Lecture35.4up.pdf

Other Links to VBA for Smarties:

http://www.snb-vba.eu/VBA_Dictionary_en.html

http://www.snb-vba.eu/VBA_Collection_en.html

A User Controlled Demonstration of the Aitken-Lagrange Construction for Points on a Cubic.

Aitken Lagrange Cubic Construction

A few weeks ago Peter Bartholomew (uk.linkedin.com/in/peterbartholomew ) visited my blog. He made a very valuable suggestion – put up a demonstration for the construction of points on a cubic using the Aitken- Lagrange construction.
He sent me a sample workbook that demonstrated the point wise construction of a Bezier Cubic.
I have now re-engineered his workbook and have generated a user controlled demonstration for the Aitken-Lagrange construction of points on a cubic.
This workbook also demonstrates the technique of incorporating User Define Functions in Named Ranges. I believe that Bob Umlas (www.linkedin.com/pub/bob-umlas/46/278/479 ) was the first to discover this technique.
The User Defined Functions employed by this demonstration are:
Name Definition
X_Values =OFFSET(Aitken_Lagrange!$D1,0,0)

y_12_FLINE =(Y_P1*(X_P2-X_Values)+Y_P2*(X_Values-X_P1))/(X_P2-X_P1)
Y_23_FLINE =(Y_P2*(X_P3-X_Values)+Y_P3*(X_Values-X_P2))/(X_P3-X_P2)
Y_34_FLINE =(Y_P3*(X_P4-X_Values)+Y_P4*(X_Values-X_P3))/(X_P4-X_P3)

Y_123_FLINE =(y_12_FLINE*(X_P3-X_Values)+Y_23_FLINE*(X_Values-X_P1))/(X_P3-X_P1)
Y_234_FLINE =(Y_23_FLINE*(X_P4-X_Values)+Y_34_FLINE*(X_Values-X_P2))/(X_P4-X_P2)

Y_1234_FLINE =(Y_123_FLINE*(X_P4-X_Values)+Y_234_FLINE*(X_Values-X_P1))/(X_P4-X_P1)

Note well: The definition for the X_Values coming from Column D on Aitken_Lagrange Sheet enables the calculation of both the XStar lookup at the top of the sheet as well as the table of values at the bottom of the sheet.
The construction first evaluates Y_12_FLINE, Y_23_FLINE and Y_34_FLINE at XStar.
These results are the used to evaluate Y_123_FLINE and Y_234_FLINE at XStar.
And finally Y_1234_FLINE at XStar.

These steps can also be presented using the Functional Form for FLINE:
Function FLINE(ByRef XL As Double, _
ByRef YL As Double, _
ByRef XR As Double, _
ByRef YR As Double, _
ByRef XSTAR As Double) As Double
‘======================================
If Abs(XR – XL) > 0 Then
FLINE = (YL * (XR – XSTAR) + YR * (XSTAR – XL)) / (XR – XL)
Else
FLINE = 0.5 * (YL + YR)
End If
End Function

y_12_FLINE =FLINE(X_P1,Y_P1,X_P2,Y_P2,XStar)
Y_23_FLINE =FLINE(X_P2,Y_P2,X_P3,Y_P3,XStar)
Y_34_FLINE =FLINE(X_P3,Y_P3,X_P4,Y_P4,XStar)

Y_123_FLINE =FLINE(X_P1,Y_12_FLINE,X_P3,Y_23_FLINE,XStar)
Y_234_FLINE =FLINE(X_P2,Y_23_FLINE,X_P4,Y_34_FLINE,XStar)

Y_1234_FLINE =FLINE(X_P1,Y_123_FLINE,X_P4,Y_234_FLINE,XStar)

A User Controlled Demonstration of the Aitken-Lagrange Construction for Points on a Parabola.

Aitken Lagrange Parabola Construction

A few weeks ago Peter Bartholomew (uk.linkedin.com/in/peterbartholomew )visited my blog. He made a very valuable suggestion – put up a demonstration for the construction of points on a parabola using the Aitken- Lagrange construction.
He sent me a sample workbook that demonstrated the point wise construction of a Bezier Cubic.
I have now re-engineered his workbook and have generated a user controlled demonstration for the Aitken-Lagrange construction of points on a parabola.
This workbook also demonstrates the technique of incorporating User Define Functions in Named Ranges. I believe that Bob Umlas (www.linkedin.com/pub/bob-umlas/46/278/479 )was the first to discover this technique.
The User Defined Functions employed by this demonstration are:
Name Definition
X_Values =OFFSET(Aitken_Lagrange!$D1,0,0)

y_12_FLINE =(Y_P1*(X_P2-X_Values)+Y_P2*(X_Values-X_P1))/(X_P2-X_P1)
Y_23_FLINE =(Y_P2*(X_P3-X_Values)+Y_P3*(X_Values-X_P2))/(X_P3-X_P2)

Y_123_FLINE =(y_12_FLINE*(X_P3-X_Values)+Y_23_FLINE*(X_Values-X_P1))/(X_P3-X_P1)

Note well: The definition for the X_Values coming from Column D on Aitken_Lagrange Sheet enables the calculation of both the XStar lookup at the top of the sheet as well as the table of values at the bottom of the sheet.

Enhanced Insertion Sorting

Array Based Insertion Permutation Sorts.Numerical

Array Based Insertion Permutation Sorts.Strings

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:

  1. Search over the sorted list to determine where the new value belongs.
  2. 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:

  1. 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.
  2. 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:

  1. 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.

  1. 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.

My Tool Kit for Practical Numerical Tools for Tabular Functions

How the Toolkit came to be.

First realization 

  • I want my mathematics to be intuitive.
  • I want to see it.
  • I want to understand it.
  • I want to own it.

Second realization

  •  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.

Third realization

  •  stacking the deck to facilitate the desired outcome is right and proper attitude for practical numerical techniques.

Fourth realization

  • Statement Functions in FORTRAN are cool.

The three seeds that formed the foundation of the Toolkit:

  1. A paper on Aitken’s Graphical Analog for Constructing Lagrange Polynomials
  2. A drafting textbook describing how a carpenter can measure arc length
  3. 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.