Android Tutorial Sorting algorithms - Teaching with Basic4android

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.b4x.com/android/files/tutorials/Sorting.zip

 

[psevet]

Sort algorythms in video

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

 

[melamoud]

stackoverflow

hi,

if all the values are the same (or most of them anyway) I get (on quicksort) stackoverflow

try it with 500 numbers, why is that ? can you fix it ?

thanks

 

[Erel]

Google for "Quicksort stack overflow". You will see all kinds of possible optimizations that also handle this case. The code here is just an example of a simple quicksort implementation. You should use List.Sort to sort any real data.

 

[melamoud]

I have a list of arrays of strings and I need to sort by a specific index how can I do that ?

Thanks

 

[Erel]

If you can use custom types instead of arrays then you can use List.SortType. Otherwise you can use this code:

Type SortHelper(SortKey As String, Value As Object) 'add in Process_Globals

Sub SortListOfArrays(Table As List, Index As Int) As List
   Dim temp As List
   temp.Initialize
   For Each row() As String In Table
      Dim sh As SortHelper
      sh.SortKey = row(Index)
      sh.Value = row
      temp.Add(sh)
   Next
   temp.SortType("SortKey", True)
   Table.Clear
   For Each sh As SortHelper In temp
      Table.Add(sh.Value)
   Next
   Return Table
End Sub

 

[melamoud]

seems like a huge overhead, I use selection sort for now.

 

[Erel]

It takes 40ms on average (on Galaxy Nexus) to sort an array of 500 random integers (changed the type to Int).

You should test your code and check which one is faster.