vbScript - Sorting With and Without Code
Please see my post vbScript - The Basics for more details on vbScript.
Sorting is something that must be done from time to time. I'm going to examine three ways. The first is the well known (at least by name) QuickSort method. Rather than repeating existing explanations of the actual algorithm I'll just refer you to the Wikipedia QuickSort article and present the code with comments below.
The second method uses a binary tree. The concept is simple even if the implementation is a little difficult to grasp initially. We start with the idea of a node. A node is just a block of data which will contain three important pieces of information. The first is a value (in our case, an item of whatever we sorting). The other two pieces are indicators (pointers) to any subtrees to the left and/or right. Imagine a pyramid with one box at the top and two boxes below that, one to the left and one to the right. Now imagine that each of the lower boxes is its own tree with possibly two boxes below that, and so on.
The idea is that the first item we want to sort will go at the top of the tree. The next item will be either less than the first item, in which case we add it to the left of the tree, greater than the first item, in which case we add it to the right, or equal, in which case, oh dear. So we add another piece of information to the node. It will be a count of how many of each item we have. So if the second item is the same as the first we just add one to the count.
But what if there is already an item to the left or right? In that case we just treat the left or right node as the top of a tree and do the same test again. At some point we will get to the end of the tree and we can add a new node with the given value.
Here's where we get to the part that can give newbies trouble. Recursion. The top node may or may not be the lowest value. What we do know is that if there is a lower value, it must be to the left of the top node, so we go left and find the same conditions - if there is a lower value than that node it must be to the left, and so on and so on. So the output algorithm becomes
Output everything to the left of the current node
Output the current node
Output everything to the right of the current nodeIt's elegant once you wrap your mind around it. One last thing I should mention - in vbScript you can define objects using Class and End Class and add properties and methods (either public or private). If you want to go by the book you can define get, set and let functions for the properties, or if you are lazy (like me) or disciplined (like me) you can just make the properties public. It's certainly clearer to read.
To test the bitree.vbs code I suggest you create a file, test.txt, that contains the lines
the
quick
brown
fox
jumped
over
the
lazy
lazy
white
dogThen you can run bitree.vbs by
bitree test.txt
bitree test.txt /verboseThe second method will result in a lot more output but will explain in more detail what is happening. To help you can draw the tree on a piece of paper and match the actions shown in the /verbose output.
The third method requires almost no coding whatsoever. The .net core library provides a number of collection objects that you can create as needed in vbScript. One of these is the ArrayList. Using this object you can add items (of any type, including objects) without having to predetermine an array size, or redimension on the fly. The object provides a Sort method. Here is an example.
Set arr = CreateObject("System.Collections.ArrayList")
arr.Add "the"
arr.Add "quick"
arr.Add "brown"
arr.Add "fox"
arr.Add "jumped"
arr.Add "over"
arr.Add "the"
arr.Add "lazy"
arr.Add "dog"
WScript.Echo ""
WScript.Echo "List the items in storage order"
WScript.Echo ""
For Each item In arr
WScript.Echo item
Next
WScript.Echo ""
WScript.Echo "Sort the array and output"
WScript.Echo ""
arr.Sort()
For Each item In arr
WScript.Echo item
NextThere is a similar object, SortedArray. This collection is similar to a Dictionary except that unlike a Dictionary, the keys are maintained in sorted order. That means that you can add items in any order and when you iterate through the keys they will always be in sorted order.
Check out System.Collections for a more complete list of objects. Note that not all methods and properties are available in vbScript.