Sorting algorithms - Teaching with Basic4android

[Erel]

There are several customers who like to use Basic4android for teaching purposes.
The following code can be useful for these purposes.
You should also check the Linked list tutorial.

Note that Basic4android is sold at half the price for academic usage.
Contact erel@basic4ppc.com for more information.

Implementations of sorting algorithms are useful for teaching fundamental concepts such as algorithms analysis, complexity and data structures.

The following code includes implementations of the following sorting algorithms: bubble sort, selection sort, quick sort, merge sort and binary tree sort.
The code should be pretty straightforward once you understand the algorithm.




Code (file is also attached):

'Activity module
Sub Process_Globals
    Type TreeElement(Value As Int, Left As TreeElement, Right As TreeElement)
End Sub

Sub Globals
    Dim lv As ListView
    Dim data(100) As Int
End Sub

Sub Activity_Create(FirstTime As Boolean)
    lv.Initialize("lv")
    Activity.AddView(lv, 0, 0, 100%x, 100%y)
    lv.SingleLineLayout.Label.TextSize = 13
    lv.SingleLineLayout.ItemHeight = 40dip
    FillWithRandomNumbers
    DisplayData
    Activity.AddMenuItem("Randomize", "mnuRandomize")
    Activity.AddMenuItem("Bubble Sort", "mnuBubbleSort")
    Activity.AddMenuItem("Quick Sort", "mnuQuickSort")
    Activity.AddMenuItem("Merge Sort", "mnuMergeSort")
    Activity.AddMenuItem("Selection Sort", "mnuSelectionSort")
    Activity.AddMenuItem("Binary Tree Sort", "mnuBinaryTreeSort")
End Sub
Sub lv_ItemClick (Position As Int, Value As Object)
    Activity.OpenMenu
End Sub

Sub FillWithRandomNumbers
    For i = 0 To data.Length - 1
        data(i) = Rnd(0, 10000)
    Next
End Sub

Sub DisplayData
    lv.Clear
    For i = 0 To data.Length - 1
        lv.AddSingleLine(data(i))
    Next
End Sub
Sub mnuRandomize_Click
    FillWithRandomNumbers
    DisplayData
End Sub

Sub mnuBubbleSort_Click
    Dim s As Long
    s = DateTime.Now
    BubbleSort
    ToastMessageShow("Bubble Sort took: " & (DateTime.Now - s) & " ms", False)
    DisplayData
End Sub

Sub mnuQuickSort_Click
    Dim s As Long
    s = DateTime.Now
    QuickSort(0, data.Length - 1)
    ToastMessageShow("Quick Sort took: " & (DateTime.Now - s) & " ms", False)
    DisplayData
End Sub

Sub mnuMergeSort_Click
    Dim s As Long
    s = DateTime.Now
    data = MergeSort(data)
    ToastMessageShow("Merge Sort took: " & (DateTime.Now - s) & " ms", False)
    DisplayData
End Sub

Sub mnuSelectionSort_Click
    Dim s As Long
    s = DateTime.Now
    SelectionSort
    ToastMessageShow("Selection Sort took: " & (DateTime.Now - s) & " ms", False)
    DisplayData
End Sub

Sub mnuBinaryTreeSort_Click
    Dim s As Long
    s = DateTime.Now
    Dim root As TreeElement
    root.Initialize
    root.Value = data(0)
    For i = 1 To data.Length - 1
        InsertTreeElement(root, data(i))
    Next
    TraverseTree(root, 0)
    ToastMessageShow("Binary Tree Sort took: " & (DateTime.Now - s) & " ms", False)
    DisplayData
End Sub

Sub Swap(index1 As Int, index2 As Int)
    Dim temp As Int
    temp = data(index1)
    data(index1) = data(index2)
    data(index2) = temp
End Sub

Sub BubbleSort
    Dim swapped As Boolean
    swapped = True
    Do While swapped
        swapped = False
        For i = 1 To Data.Length - 1
            If data(i - 1) > data(i) Then
                Swap(i-1, i)
                swapped = True
            End If
        Next
    Loop
End Sub

Sub SelectionSort
    Dim minIndex As Int
    For i = 0 To data.Length - 1
        minIndex = i
        For j = i + 1 To data.Length - 1
            If data(j) < data(minIndex) Then minIndex = j
        Next
        Swap(i, minIndex)
    Next
End Sub

Sub QuickSort (left As Int, right As Int)
    If right > left Then
        Dim pivotIndex, pivotNewIndex As Int
        pivotIndex = Rnd(left, right + 1) 'max value is exclusive
        pivotNewIndex = Partition(left, right, pivotIndex)
        QuickSort(left, pivotNewIndex - 1)
        QuickSort(pivotNewIndex + 1, right)
    End If
End Sub

Sub Partition (left As Int, right As Int, pivotIndex As Int) As Int
    Dim pivotValue, storeIndex As Int
    pivotValue = data(pivotIndex)
    Swap(pivotIndex, right)
    storeIndex = left
    For i = left To right - 1
        If data(i) <= pivotValue Then
            Swap(i, storeIndex)
            storeIndex = storeIndex + 1
        End If
    Next
    Swap(storeIndex, right)
    Return storeIndex
End Sub

Sub MergeSort(arr() As Int) As Int()
    If arr.Length <= 1 Then Return arr
    Dim middle As Int
    middle = arr.Length / 2
    Dim left(middle) As Int
    Dim right(arr.Length - middle) As Int
    For i = 0 To middle - 1
        left(i) = arr(i)
    Next
    For i = middle To arr.Length - 1
        right(i - middle) = arr(i)
    Next
    left = MergeSort(left)
    right = MergeSort(right)
    Return Merge(left, right)
End Sub

Sub Merge(left() As Int, right() As Int) As Int()
    Dim leftIndex, rightIndex As Int 'initialized to 0
    Dim result(left.Length + right.Length) As Int
    For i = 0 To result.Length - 1
        If rightIndex = right.Length OR _ 
            (leftIndex < left.Length AND left(leftIndex) < right(rightIndex)) Then
            result(i) = left(leftIndex)
            leftIndex = leftIndex + 1
        Else
            result(i) = right(rightIndex)
            rightIndex = rightIndex + 1
        End If
    Next
    Return result
End Sub

Sub InsertTreeElement(Parent As TreeElement, Value As Int)
    Dim leaf As TreeElement
    If Parent.IsInitialized = False Then
        Parent.Initialize
        Parent.Value = Value
    Else If Value < Parent.Value Then
        InsertTreeElement(Parent.Left, Value)
    Else
        InsertTreeElement(Parent.Right, Value)
    End If
End Sub

Sub TraverseTree (Parent As TreeElement, ArrayIndex As Int) As Int
    If Parent.IsInitialized = False Then Return ArrayIndex
    ArrayIndex = TraverseTree(Parent.Left, ArrayIndex)
    Data(ArrayIndex) = Parent.Value
    ArrayIndex = ArrayIndex + 1
    ArrayIndex = TraverseTree(Parent.Right, ArrayIndex)
    Return ArrayIndex
End Sub

Program is available here: http://www.basic4ppc.com/android/fil...ls/Sorting.zip

[psevet]

Hello,

For the wannabee programers as I am :

Bubble sort algorythm : YouTube - Bubble-sort with Hungarian ("Csángó") folk dance

Select sort algorythm : YouTube - Select-sort with Gypsy folk dance

Insert-sort algorythm : YouTube - Insert-sort with Romanian folk dance

Enjoy

Pierre

[Gary Miyakawa]

If you want to dig WAY deeper on the sorting stuff... The bible used to be "Donald E. Knuth" Sorting and Searching Algorithms... Heavy reading if you are into that kind of stuff..

Cheers,

Gary M

[nfordbscndrd]

As a result of another thread, I looked at the Quick Sort routine in the code above and it doesn't look like QS routines I've used in the past, so I Googled Quick Sort and looked at some QS routines there and the tutorial routine doesn't look like what's going on in any of them either.

Here is a routine from VB - Quick Sort algorithm (very fast sorting algorithm) - VBForums

Private Sub QuickSort(C() As String, ByVal First As Long, ByVal Last As Long)
    Dim Low As Long, High As Long
    Dim MidValue As String
    
    Low = First
    High = Last
    MidValue = C((First + Last) \ 2)
    
    Do
        While C(Low) < MidValue
            Low = Low + 1
        Wend
        
        While C(High) > MidValue
            High = High - 1
        Wend
        
        If Low <= High Then
            Swap C(Low), C(High)
            Low = Low + 1
            High = High - 1
        End If
    Loop While Low <= High
    
    If First < High Then QuickSort C, First, High
    If Low < Last Then QuickSort C, Low, Last
End Sub

And this is the code in this tutorial:

Sub QuickSort (left As Int, right As Int)
    If right > left Then
        Dim pivotIndex, pivotNewIndex As Int
        pivotIndex = Rnd(left, right + 1) 'max value is exclusive
        pivotNewIndex = Partition(left, right, pivotIndex)
        QuickSort(left, pivotNewIndex - 1)
        QuickSort(pivotNewIndex + 1, right)
    End If
End Sub

Sub Partition (left As Int, right As Int, pivotIndex As Int) As Int
    Dim pivotValue, storeIndex As Int
    pivotValue = data(pivotIndex)
    Swap(pivotIndex, right)
    storeIndex = left
    For i = left To right - 1
        If data(i) <= pivotValue Then
            Swap(i, storeIndex)
            storeIndex = storeIndex + 1
        End If
    Next
    Swap(storeIndex, right)
    Return storeIndex
End Sub

In particular, the part of the code which says

While C(Low) < MidValue
    Low = Low + 1
Wend
        
While C(High) > MidValue
    High = High - 1
Wend

is common to every QS routine I've used or seen, but I can't figure how the tutorial code is accomplishing this, though this is very likely just my inability to figure out the tutorial code. So if you could straighten me out, I would appreciate it.

[Erel]

It is based on the in-place sorting algorithm described here: http://en.wikipedia.org/wiki/Quicksort