4.3.5.1–4.3.5.2 - Bubble sort and merge sort (VB.NET)

4.3.5.1–4.3.5.2 - Bubble sort and merge sort (VB.NET)

Learn how adjacent swaps move a largest value into place and how merging smaller sorted sequences builds a sorted result. Trace both sorts and explain their different growth in work as the input gets larger.

VB.NET route status: incomplete: runnable support pending. The native examples and code answers here are written practice.

Bubble-sort passes and swaps

Bubble sort compares adjacent values and swaps an out-of-order pair, gradually moving a largest remaining value to the end of the unsorted region.

For ascending order, swap when the left value is greater than the right value. Save one value temporarily before assigning over it. This native procedure changes the supplied array in place; put it inside a module.

VB.NET
Sub BubbleSort(values As Integer())
    For finish As Integer = values.Length - 1 To 1 Step -1
        Dim swapped As Boolean = False
        For index As Integer = 0 To finish - 1
            If values(index) > values(index + 1) Then
                Dim temporary As Integer = values(index)
                values(index) = values(index + 1)
                values(index + 1) = temporary
                swapped = True
            End If
        Next
        If Not swapped Then Exit For
    Next
End Sub

Start with {5, 1, 4, 2}. The first pass compares 5/1, 5/4 and 5/2, producing {1, 4, 2, 5}. The second compares 1/4 and 4/2, producing {1, 2, 4, 5}. The third compares 1/2 with no swap and terminates. The final positions are excluded from later passes because the earlier passes have already placed their largest values there.

In the worst case, shrinking passes make (n−1)+(n−2)+⋯+1=n(n−1)/2(n-1)+(n-2)+\cdots+1=n(n-1)/2 comparisons, so time is O(n2)O(n^2). Doubling a large input makes the quadratic work roughly four times as large. It is a particularly inefficient sort for large data. With the no-swap stopping rule, already sorted data takes one pass and n−1n-1 comparisons: best-case O(n)O(n). This improvement does not change its quadratic worst case. Empty and one-item arrays require no comparisons.

Merge sort and divide and conquer

Merge sort divides an input into smaller pieces, sorts them and merges their sorted results; the merge step makes the dividing useful.

Divide and conquer

Solve a problem by dividing it into smaller problems of the same kind, solving those, then combining their results.

An array of zero or one element is already sorted. Split a larger array into two halves and recursively sort each. To merge two ascending arrays, compare the next unused value in each. Append the smaller, advance only its pointer, and repeat. When one side is exhausted, append all the remaining values from the other side. They are already sorted and larger than or equal to the values selected so far.

For {7, 2, 5, 1}, the halves are {7, 2} and {5, 1}. Their singletons merge to {2, 7} and {1, 5}. The final merge chooses 1, then 2, then 5, then the remaining 7. Splitting is not the sorting operation by itself.

These native functions belong in a module with Imports System.Collections.Generic. They return a new sorted array and leave the input unchanged. <= takes equal values from the left first, retaining their original relative order across the halves.

VB.NET
Function Merge(left As Integer(), right As Integer()) As Integer()
    Dim result As New List(Of Integer)()
    Dim i As Integer = 0
    Dim j As Integer = 0
    While i < left.Length AndAlso j < right.Length
        If left(i) <= right(j) Then
            result.Add(left(i))
            i += 1
        Else
            result.Add(right(j))
            j += 1
        End If
    End While
    While i < left.Length
        result.Add(left(i))
        i += 1
    End While
    While j < right.Length
        result.Add(right(j))
        j += 1
    End While
    Return result.ToArray()
End Function

Function MergeSort(values As Integer()) As Integer()
    If values.Length <= 1 Then Return CType(values.Clone(), Integer())
    Dim middle As Integer = values.Length \ 2
    Dim left(middle - 1) As Integer
    Dim right(values.Length - middle - 1) As Integer
    Array.Copy(values, 0, left, 0, left.Length)
    Array.Copy(values, middle, right, 0, right.Length)
    Return Merge(MergeSort(left), MergeSort(right))
End Function

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account