VBScript Coding Exercise – Insertion Sorting Algorithm

Among the simple sorting algorithms, the insertion sorting algorithm is my favourite. Insertion sort is simple to implement and gives an average quadratic O(n²) running time, like other simple sorting algorithms i.e. bubble sort, selection sort etc. For larger inputs, the simple sorting (including insertion sort) is slower than the O(n log n) sorting algorithms like quick sort.

When data is nearly sorted, the insertion sort gives a O(n) running time complexity, which is like the improved bubble sort. The worst case happens when the data is in the reverse order, in which case the complexity is O(n²)

The insertion sort splits the data into two parts, the sorted partial result and the unsorted part. At each iteration, one number from the unsorted list is inserted into the correct position of the sorted list.

The insertion sort is generally considered practically faster than other simple sorting algorithms, in fact, it is faster than quick sort when the data number is small. That is why a good quick sort will usually employ the insertion sort when the number of data partitions (either left or right recursively) is smaller than a threshold.

The following demonstrate the insertion sort in VBScript.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Option Explicit
Const N = 10
 
Dim Nums()
ReDim Nums(N)
 
Randomize
Dim i
For i = 0 To N
    ' Randomize the Numbers as Integers
    Nums(i) = Int(Rnd() * (N * 2))
Next
 
' Print out the Number Array
Sub PrintNum(Msg, arr)
    Dim i, s
    s = Msg
    For i = 0 To UBound(arr)
        s = s & " " & arr(i)
    Next
    WScript.Echo s
End Sub
 
Sub InsertionSort(ByRef arr)
    Dim j, i, N, x
    ' Upper Bound of Array
    N = UBound(arr)
    For i = 1 To N
        j = i
        x = arr(i)
        Do While j > 0
            If arr(j - 1) > x Then
                ' Shift Big Numbers to The Right
                arr(j) = arr(j - 1) 
                j = j - 1   
            Else
                Exit Do
            End If
        Loop 
        arr(j) = x
    Next
End Sub
 
PrintNum "Before: ", Nums
Call InsertionSort(Nums)
PrintNum "After: ", Nums

Option Explicit
Const N = 10

Dim Nums()
ReDim Nums(N)

Randomize
Dim i
For i = 0 To N
	' Randomize the Numbers as Integers
	Nums(i) = Int(Rnd() * (N * 2))
Next

' Print out the Number Array
Sub PrintNum(Msg, arr)
	Dim i, s
	s = Msg
	For i = 0 To UBound(arr)
		s = s & " " & arr(i)
	Next
	WScript.Echo s
End Sub

Sub InsertionSort(ByRef arr)
	Dim j, i, N, x
	' Upper Bound of Array
	N = UBound(arr)
	For i = 1 To N
		j = i
		x = arr(i)
		Do While j > 0
			If arr(j - 1) > x Then
				' Shift Big Numbers to The Right
				arr(j) = arr(j - 1)	
				j = j - 1	
			Else
				Exit Do
			End If
		Loop 
		arr(j) = x
	Next
End Sub

PrintNum "Before: ", Nums
Call InsertionSort(Nums)
PrintNum "After: ", Nums

It sorts the numbers:

Before:  14 10 11 5 6 15 0 15 16 14 0
After:  0 0 5 6 10 11 14 14 15 15 16

We use a ByRef (although by default can be omitted) to enable passing array as reference, so we can change it in the function. However, make sure we use the Call to invoke the function or simply without adding brackets, like this: InsertionSort Nums. In VBScript, if we are calling the Sub the brackets wrapping the parameters will force ByVal (pass by value) even the parameters are defined as ByRef.

In VBScript, there is no Exit While so you cannot break the While loop unless you use the syntax Do While … Loop and Exit Do. Also, the VBScript (at least the Microsoft WSH) does not employ any boolean circuit optimisation, so if you write While j > 0 and arr(j – 1) > x this will cause the error of trying to access arr(-1) which is out of the valid subranges.

References

en.wikipedia.org/wiki/Insertion_sort

–EOF (The Ultimate Computing & Technology Blog) —