Sorting Algorithms In VB

All too often in an application, there's a need to sort a list of items. In this article, I will cover some of the more common sorting algorithms and give a few tips on choosing the right one for the job. I will cover the classic "Bubble sort" and "Insertion sort," right through to the difficult "Exchange sort" and "Stack sort." Then, you will look into a "Hybrid sort" that is a mix of the "Insertion and Stack sort" algorithms. You also will look at the advantages and disadvantages of each sorting algorithm.

First, look at a list of different sorting algorithms with a short list of details. 'Stable' refers to the ability of the sort algorithm to keep identical items in the original order.

Sort Name Method Stable? Short Description
Bubble Sort Exchanging Yes Basic two-loop sort
Cocktail Sort Exchanging Yes Bi-directional Bubble sort
Comb Sort Exchanging No Faster variation of the Bubble sort
Gnome Sort Exchanging Yes Hybrid (Bubble and Insertion Sort)
Selection Sort Selection No In-place comparison sort
Insertion Sort Insertion Yes Simple comparison sort
Shell Sort Insertion No Generalization of insertion sort
Binary tree sort Insertion Yes Builds a Binary tree of the data and uses the tree to sort
Library Sort Insertion Yes Insertion sort that leaves gaps in the list for subsequent elements
Merge Sort Merging Yes A divide, sort, and merge algorithm
In-Place Merge Sort Merging Yes Space-optimised version of the merge sort
Heap Sort Selection No Two-stage comparison style sort
Smooth Sort Selection No Small variation of a Heap sort
Quick Sort Partitioning No Recursive partition and sort
Intro Sort Hybrid No Hybrid of quick sort and heap sort
Patience Sorting Insertion No Statistical ordering of elements
Stand Sort Selection Yes Useful for data which is stored in a linked list

There are still more sorting algorithms and methods, but some require specific hardware, like the "Bead sort" and "Network Sort," and others are so impractical that they exist solely for demonstration purposes, like the "Bogo Sort" and "Stooge Sort" (named after the Three Stooges).

Sorting Algorithms In VB

Bubble Sort

The bubble sort is the oldest of the sort algorithms that has ever been used. The basic coding used here is set up two loops simply to go through the list of items one at a time and compare an item to an item after it in the list, and place the smaller (or larger) item higher up in the list.

There are two methods of using this algorithm; both are correct and return much the same results it terms of time and passes. One method, "the backward bubble sort," is to set up the outer loop to step up through the list and the inner loop to step down to the outer loop value, and on each pass compare elements adjacent to each other and swap them if they are in the wrong order.

The other method, "the forward bubble sort," is to step both the inner and outer loops down the list and compare the element of the outer loop to the element of the inner loop and swap them if they are in the wrong order.

The main difference between forward and backward bubble sorting is the direction the list is sorted, as denoted by the name. The code length (in almost any language) will be identical, with only a few differences in variable placements. Execution time will be very similar across the two algorithms, and will depend mostly on how the original list is currently sorted.

With Bubble sorts (Forward or Backward), it's worth noting that after the nth pass, either the first or last n items are sorted into their correct positions respectively.

There aren't many advantages to using the bubble sort, except maybe the compiled code length in some languages, like Assembly, or the ease at setting up and debugging the code. One major disadvantage is execution time. The execution time for the algorithm increases exponentially as the size of the list increases.

Now, look at the code. Listing 1 is the backward bubble sort, and Listing 2 is the forward bubble sort. In Listing 3, you make a few changes to the code to get maximum speed out of it. You add a Boolean check so that if there is a pass that does no swaps, you know that the list is sorted and there is no need to carry on. In a semi-sorted list, the code in Listing 3 would be the fastest of the three.

Listing 1

For Loop1 = 1 to Max
    For Loop2 = 0 to Max - Loop1
        If List(Loop2) > List(Loop2 + 1) Then
            Tmp = List(Loop2)
            List(Loop2) = List(Loop2 + 1)
            List(Loop2 + 1) = Tmp
        End If
    Next Loop2
Next Loop1

Listing 2

For Loop1 = 0 to Max -1
    For Loop2 = Loop1 +1 to Max
        If List(Loop1) > List(Loop2) Then
            Tmp = List(Loop2)
            List(Loop2) = List(Loop1)
            List(Loop1) = Tmp
        End If
    Next Loop2
Next Loop1

Listing 3

Limit = Max
Do
    Switch = False
    For Loop1 = 0 To (Limit - 1)
        If List(Loop1) > List(Loop1 + 1) Then
            Tmp = List(Loop1)
            List(Loop1) = List(Loop1 + 1)
            List(Loop1 + 1) = Tmp
            Switch = True
            Limit = Loop1
        End If
    Next Loop1
Loop While Switch

Sorting Algorithms In VB

Insertion Sort

The Insertion sort is one step better than the bubble sort and works on a similar principle. You still loop over the full list from first to last but instead of swapping elements over, you insert the element in the correct position within the already sorted part of the list.

If the list to be sorted were in reverse order, both Bubble and Insertion sorts would take about the same time to sort; however, if the list was semi-sorted, the insertion sort would run much faster.

With Insertion sort, it's interesting to note that after the nth pass the first n items are sorted; however, they are not necessarily in their correct and final positions.

Insertion sort has only a few advantages over other sorting algorithms in that it can be used to sort items in an online fashion, as in the user inputting a list or input from an outside device, a lot quicker that most other sorts.

Listing 4 gives a working example of the Insertion sort.

Listing 4

For Loop1 = 1 To Total
    Tmp = List(Loop1)
    For Loop2 = Loop1 To 1 Step -1
        If List(Loop2 - 1) > Tmp Then
            List(Loop2) = List(Loop2 - 1)
        Else
            Exit For
        End If
    Next Loop2
    List(Loop2) = Tmp
Next Loop1

Selection Sort

The Selection sort is somewhere between the insertion sort and bubble sort; it scans over the remaining unsorted list to find the smallest item and place it at the beginning. Selection sort is also often referred to as Exchange sort because of the method in which items are not shifted up and down but rather will exchange positions to place an item in the correct place.

There is not much that can be said for the selection sort except that, depending on the medium being used where writing to an array is more expensive than reading (memory access times; in other words, on EEPROMS or Flash), a selection sort will run faster than most other sorts due to the number of item swaps that take place.

With Selection sort, it's worthwhile to note that after the nth pass, only n item swaps have taken place and the first n items are sorted into their correct position.

Listing 5 is an example of the Selection sort.

Listing 5

For Loop1 = 0 To Total
    Pos = Loop1
    For Loop2 = Loop1 + 1 To Total
        If List(Loop2) < List(Pos) Then
            Pos = Loop2
        End if
    Next Loop2
    If Pos <> Loop1 Then
        Tmp = List(Pos)
        List(Pos) = List(Loop1)
        List(Loop1) = Tmp
    End If
Next Loop1

Sorting Algorithms In VB

Heap Sort

The Heap sort has a two-step method of sorting; first, the list is semi sorted to build a parent-child tree within the list. Then, the parent child tree is used to sort the list.

There are several methods to implement the heap sort, with some algorithms using secondary arrays to perform the sort. The listing given performs the heap sort within the original list, and has been optimised.

In the first step, the list will appear to be in a worse sorted order than before starting; however, the sorting parent child tree has been built with the largest item in the list on the top. During the second step, after every nth pass, the n last items will be sorted into their correct positions. The parent -child tree ensures that with each pass the next largest item is always shifted to the top of the list.

The heap sort has one disadvantage. Given its code size, it's not practical to use in projects were there is a limited memory available for code; for example, on Micro-controllers and Programmable PICs.

However large the code may be, the heap sort did have the advantage of been the fastest, non-recursive code, sort available for many years, limited to systems where memory read and write access times were similar.

Listing 6 shows an optimised working example of the heap sort.

Listing 6

For Loop1 = 1 To Total
    PercolateUp Loop1
Next Loop1
For Loop1 = Total To 1 Step -1
    Swap 0, Loop1
    PercolateDown Loop1 - 1
Next Loop1

Sub PercolateUp(MaxLevel)
Loop2 = MaxLevel
Do Until Loop2 = 0
    Parent = Loop2 \ 2
    If List(Loop2) > List(Parent) Then
        Tmp = List(Loop2)
        List(Loop2) = List(Loop2 + 1)
        List(Loop2 + 1) = Tmp
        Loop2 = Parent
    Else
        Exit Do
    End If
Loop

Sub PercolateDown(MaxLevel)
Loop2 = 0
Do
    Child = 2 * Loop_2
    If Child > MaxLevel Then Exit Do
    If Child + 1 <= MaxLevel Then
        If List(Child + 1) > List(Child) Then
            Child = Child + 1
        End If
    End If
    If List(Loop_2) < List(Child) Then
        Tmp = List(Loop2)
        List(Loop2) = List(Loop2 + 1)
        List(Loop2 + 1) = Tmp
        Loop_2 = Child
    Else
        Exit Do
    End If
Loop

Shell Sort

The Shell sort improves the Insertion sort by doing comparisons separated by a gap of several positions, with each pass progressively reducing the gap. It was developed by Donald Shell and was published in 1959 in "Communications of the ACM."

Donald Shell's original recommendation was to use n/2 for the first pass and divide by 2 for each pass thereafter, until the gap was 1, at which point the Shell sort is the same as an Insertion sort. The best-known gap sequence for use in the Shell sort is 1, 4, 10, 23, 57, 132, 301, 701. For any lists that are larger, you can calculate the next geometric progression using "NextGap = Gap * 2.3".

Using the above-mentioned gap sequence will improve the speed of the Shell sort, but there are a few drawbacks. The sort code is larger, mostly for the additional instructions required to find and load the next gap sequence. Also, memory usage is increased slightly to store that Gap sequence table.

The Shell sort is one of the fastest, non-recursive code, sorts where memory access and write times are similar.

Listing 7 shows an optimised Shell sort using Donald Shell's original recommendation of n/2.

Listing 7

Offset = Total / 2
Do While Offset > 0
    Limit = Total - Offset
    Do
        Switch = False
        For Loop1 = 0 To Limit
            If List(Loop1) > List(Loop1 + Offset) Then
                Tmp = List(Loop1)
                List(Loop1) = List(Loop1 + Offset)
                List(Loop1 + Offset) = Tmp
                Switch = True
                Limit = Loop1 - Offset
            End If
        Next Loop1
    Loop While Switch
    Offset = Offset / 2
Loop

Sorting Algorithms In VB

Quick Sort

The Quick sort, also known as a Stack sort, partitions the list on a random pivot point, placing all items smaller or larger on either side of the pivot, and then recursively calls itself passing over the split lists. The recursive calls continue until the algorithm receives a list where there are only one or two items in it, at which time this part of the list is sorted into the correct position. Charles Hoare developed it in 1960 for use with the ALGOL-based Elliot systems.

Because of the recursive nature of the algorithm, the Quick sort does require a rather large processor stack, and does use a relatively large amount of memory to store many of the values used in each recursive call. However, in situations where speed is of utmost essence and memory is not a factor, Quick sort does a tremendous job of sorting lists on the fly.

The only disadvantage of using the Quick sort algorithm is if you have a system with a limited stack size, or have added it to a program that makes heavy use of the stack, you may end up with "Out of Stack" or "Stack Overflow" errors when trying to sort relatively larger lists. In the absolute worst case, the Quick sort will do n-2 recursive calls and in the best case it will do log2(n)-recursive calls; however, the general accepted maximum recursive call depth is 4 log2 n. This needs to be taken into consideration and a non-recursive sorting algorithm may need to be used as an alternative if there is insufficient stack space.

An advantage of Quick sort is that, with the divide and sort method, the algorithm can be written so that each recursive call is run in a new thread, and even on a separate processor. Because the list is split and each part of the list is not dependent on the other, parallel processing without the need for cross thread communication can take place, and further speed up the sorting.

Listing 8 shows a Quick sort based on Charles Hoare's original algorithm, using a randomly selected pivot point.

As with almost everything else, there is always place for improvement. Over the years, many variations of the Quick sort have cropped up, many giving only a slight improvement of speed. However, there is a variant that almost halves the amount of sorting time.

Listing 9 shows this variant. The algorithm make a single tail recursive call during processing, which unfortunately does not allow for multi threading. However, with the method of pre and post processing, an effective high speed sort can be accomplished.

Listing 8

Sub StackSort(Low, High)
If Low < High Then
    If High - Low = 1 Then
        If List(Low) > List(High) Then
            Tmp = List(Low)
            List(Low) = List(High)
            List(High) = Tmp
        End If
    Else
        RndIndex = Int(Low + 1 + (Rnd() * (High - Low - 2)))
        Tmp = List(High)
        List(High) = List(RndIndex)
        List(RndIndex) = Tmp
        Part = List(High)
        Do
            TmpL = Low
            TmpH = High
            Do While (TmpL < TmpH) And (List(TmpL) <= Part)
            TmpL = TmpL + 1
        Loop
        Do While (TmpH > TmpL) And List(TmpH) >= Part)
            TmpH = TmpH - 1
        Loop
        If TmpL < TmpH Then
            Tmp = List(TmpL)
            List(TmpL) = List(TmpH)
            List(TmpH) = Tmp
        End If
        Loop While TmpL < TmpH
        Tmp = List(TmpL)
        List(TmpL) = List(High)
        List(High) = Tmp
        StackSort Low, TmpL - 1
        StackSort TmpL + 1, High
    End If
End If

Listing 9

Sub QuickSort(Low, Up)
While Up > Low
    Loop1 = Low
    Loop2 = Up
    Part = List(Low)
    While Loop1 < Loop2
        While List(Loop2) > Part
            Loop2 = Loop2 - 1
        Wend
        List(Loop1) = List(Loop2)
        While (Loop1 < Loop2) And List(Loop1) <= Part
            Loop1 = Loop1 + 1
        Wend
        List(Loop2) = List(Loop1)
    Wend
    List(Loop1) = Part
    QuickSort Low, Loop1 - 1
    Low = Loop1 + 1
Wend


About the Author

Richard Newcombe

Richard Newcombe has been involved in computers since the time of the Commodore 64. Today, he has excelled in programming, and designs. Richard is in his mid 30's and, if or when you looking for him look no further than his computer. Always willing to help and give advice where he can in regard to computer related subjects. At present he is working as a .NET 2008 Software Developer for Syncrony Web Services, South Africa.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Today's agile organizations pose operations teams with a tremendous challenge: to deploy new releases to production immediately after development and testing is completed. To ensure that applications are deployed successfully, an automatic and transparent process is required. We refer to this process as Zero Touch Deployment™. This white paper reviews two approaches to Zero Touch Deployment--a script-based solution and a release automation platform. The article discusses how each can solve the key …

  • On-demand Event Event Date: December 18, 2014 The Internet of Things (IoT) incorporates physical devices into business processes using predictive analytics. While it relies heavily on existing Internet technologies, it differs by including physical devices, specialized protocols, physical analytics, and a unique partner network. To capture the real business value of IoT, the industry must move beyond customized projects to general patterns and platforms. Check out this webcast and join industry experts as …

Most Popular Programming Stories

More for Developers

RSS Feeds