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):

Program is available here: http://www.basic4ppc.com/android/files/tutorials/Sorting.zip

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):

B4X:

```
'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/files/tutorials/Sorting.zip

Last edited: