Insertion sort (Visual Basic .NET)

From LiteratePrograms

This article implements the insertion sort or "bin sort" sorting algorithm in Visual Basic .NET. Insertion sort operates by repeatedly taking the next remaining element and inserting it into its correct position in the sorted sublist constructed so far. It is among the fastest of the very simple sorts and works well on nearly-sorted lists.

Simple integer sort

When sorting an array with insertion sort, we conceptually separate it into two parts:

The list of elements already inserted, which is always in sorted order and is found at the beginning of the array;
The list of elements we have yet to insert, following.

In outline, our primary module looks like this:

<<InsertionSort.vb>>=
Module InsertionSort
    Sub InsertionSort(ByRef a() As Integer)
        Dim i As Integer
        For i = 0 To a.Length - 1
            insert a(i) into sorted sublist
        Next
    End Sub
    test main
End Module

Here, the index i represents both the index of the next element to insert and the length of the sorted sublist constructed so far. We pass the array by reference so that we can modify it in place.

To insert each element, we need to create a hole in the array at the place where the element belongs, then place the element in that hole. We can combine the creation of the hole with the searching for the place by starting at the end and shifting each element up by one until we find the place where the element belongs. This overwrites the element we're inserting, so we have to save it in a variable first:

<<insert a(i) into sorted sublist>>=
Dim j As Integer, v As Integer = a(i)
For j = i - 1 To 0 Step -1
    If a(j) <= v Then Exit For
    a(j + 1) = a(j)
Next
a(j + 1) = v

On average, we move about half the elements of the already-sorted sublist to insert each element. Consequently, the total number of assignments on average to sort n elements is:

$\sum_{i=0}^{n-1} i/2 = \frac{(n-1)n}{4} = O(n^2)$

The summation starts from zero because the maximum number of assignments is one less than the serial number of the element in the array.

In the worst case, the list is in reverse sorted order, so that each element must push up all other elements encountered so far. The total number of assignments in this case is twice the average case:

$\sum_{i=0}^{n-1} i = \frac{(n-1)n}{2}$

Test driver

To try out the sort, we can write a simple test driver. Our test main will create a small array, sort it, then print out the result:

<<test main>>=
Sub Main()
    Dim a() As Integer = {5, 1, 9, 3, 2}
    Dim i as Integer
    InsertionSort(a)
    print out a
    check that the array is sorted
End Sub

Checking that the array is sorted is a pretty simple loop but we have to make sure that we handle the cases where there are zero or one elements in the array, hence we start at the second element and always compare an element to the one before it.

<<check that the array is sorted>>=
For i = 1 To a.Length - 1
    If a(i - 1) > a(i) Then
        Console.WriteLine("ERROR")
    End If
Next

A better test main might ask for numbers from the user or generate an array of random numbers. For sanity's sake, we will print out the array so that we can visually verify it is sorted. To print the array, we print out each element of the array using Console.WriteLine.

<<print out a>>=
For i = 0 To a.Length - 1
    Console.WriteLine(a(i))
Next

When we run the program, the output is sorted and ERROR is not printed, as desired.

Download code

Retrieved from "http://literateprograms.org/Insertion_sort_%28Visual_Basic_.NET%29"

Categories: Programming language:Visual Basic .NET | Environment:.NET | Insertion sort

Insertion sort (Visual Basic .NET)

From LiteratePrograms

Simple integer sort

Test driver

Views

Navigation