| In this topic we'll discuss 3 sort methods, the selection, the bubble and the insertion sort.
To illustrate the sorting techniques well use an array contain some random numeric values, that well try to sort from low to high : |
| index 0 1 2 3 4
value 88 75 93 81 21 |
Selection Sort
| We'll use a sorted part, which contains no elements before sorting, and a unsorted part, which contains all elements before sorting.
The selection sort will keep switching the positions of the smallest value and the first value of the unsorted part. This will be repeated for an unsorted part that keeps getting smaller : |
| [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21
first smallest |
| Switch the smallest (21) and first value (88) of the unsorted part : |
| [-sorted-] [-unsorted----------------------------------]
index 0 1 2 3 4
value 21 75 93 81 88
smallest
first |
| Switch the smallest (75) and first value (75) of the unsorted part : |
| [-sorted------------] [-unsorted-----------------------]
index 0 1 2 3 4
value 21 75 93 81 88
first smallest |
| The switch was unnecessary, but harmless.
Switch the smallest (81) and first value (93) of the unsorted part : |
| [-sorted-----------------------] [-unsorted------------]
index 0 1 2 3 4
value 21 75 81 93 88
first smallest |
| Switch the smallest (88) and first value (93) of the unsorted part : |
| [-sorted----------------------------------] [-unsorted-]
index 0 1 2 3 4
value 21 75 81 88 93 |
| When the unsorted part contains only 1 element, then the complete array is sorted. |
| Module SelectionSortExample
Sub Main()
Dim count As Integer = 5
Dim upperbound As Integer = count - 1
Dim numbers(upperbound) As Integer
Dim index As Integer
For index = 0 To upperbound
numbers(index) = (count ^ index) * 93 Mod 97 - (count \ (index + 1))
Next
Console.Write("unsorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Dim unsortedCount As Integer = count
Do While unsortedCount > 1
Dim startIndexUnsortedPart As Integer = count - unsortedCount
Dim indexSmallestElement As Integer = startIndexUnsortedPart
For index = startIndexUnsortedPart To upperbound
If numbers(index) < numbers(indexSmallestElement) Then
indexSmallestElement = index
End If
Next
Dim backup As Integer = numbers(indexSmallestElement)
numbers(indexSmallestElement) = numbers(startIndexUnsortedPart)
numbers(startIndexUnsortedPart) = backup
unsortedCount -= 1
Console.Write("temporary array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Loop
Console.Write("sorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.ReadLine()
End Sub
End Module
Download Broncode |
| Output : unsorted array : 88 75 93 81 21
temporary array : 21 75 93 81 88
temporary array : 21 75 93 81 88
temporary array : 21 75 81 93 88
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 |
 Up
Bubble Sort
| The bubble sort will compare all two consecutive values and switch the values if necessary. This will sink all heavy values to the bottom, and drive all light values to the surface : |
| [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21 |
| Values 88 and 75 are compared, 88 > 75 => switch both values : |
| [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 93 81 21 |
| Values 88 and 93 are compared, 88 <= 93 => don't switch : |
| [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 93 81 21 |
| Values 93 and 81 are compared, 93 > 81 => switch both values : |
| [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 81 93 21 |
| Values 93 and 21 are compared, 93 > 21 => switch both values : |
| [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 88 81 21 93 |
| The heaviest element has now sunken to the bottom of the array. The unsorted part now starts at index 0 and ends at index 3 :
Values 75 and 88 are compared, 75 <= 88 => don't switch : |
| [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 88 81 21 93 |
| Values 88 and 81 are compared, 88 > 81 => switch both values : |
| [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 81 88 21 93 |
| Values 88 and 21 are compared, 88 > 21 => switch both values : |
| [-unsorted---------------------] [-sorted--------------]
index 0 1 2 3 4
value 75 81 21 88 93 |
| Values 75 and 81 are compared, 75 <= 81 => don't switch : |
| [-unsorted---------------------] [-sorted--------------]
index 0 1 2 3 4
value 75 81 21 88 93 |
| Values 81 and 21 are compared, 81 > 21 => switch both values : |
| [-unsorted----------] [-sorted-------------------------]
index 0 1 2 3 4
value 75 21 81 88 93 |
| Values 75 and 21 are compared, 75 > 21 => switch both values : |
| [-sorted-----------------------------------------------]
index 0 1 2 3 4
value 21 75 81 88 93 |
| Module BubbleSortExample
Sub Main()
Dim count As Integer = 5
Dim upperbound As Integer = count - 1
Dim numbers(upperbound) As Integer
Dim index As Integer
For index = 0 To upperbound
numbers(index) = (count ^ index) * 93 Mod 97 - (count \ (index + 1))
Next
Console.Write("unsorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Dim unsortedCount As Integer = count
Do While unsortedCount > 1
Dim endIndexUnsortedPart As Integer = unsortedCount - 2
For index = 0 To endIndexUnsortedPart
If numbers(index) > numbers(index + 1) Then
Dim backup As Integer = numbers(index)
numbers(index) = numbers(index + 1)
numbers(index + 1) = backup
End If
Next
unsortedCount -= 1
Console.Write("temporary array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Loop
Console.Write("sorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.ReadLine()
End Sub
End Module
Download Broncode |
| Output : unsorted array : 88 75 93 81 21
temporary array : 75 88 81 21 93
temporary array : 75 81 21 88 93
temporary array : 75 21 81 88 93
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 |
Up
Insertion Sort
| In the insertion sort every element of the unsorted part is inserted at the correct position of the sorted part.
We'll start with an sorted part containing the first element : |
| [-sorted-] [-unsorted----------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21 |
| The first element of the unsorted part is put aside ( saved for later purposes ) and is the value we need to insert. We iterate ( in reverse order ) over the values of the sorted part, and shift these values to the right when they are more than the value we need to insert.
We can stop iteration over the values of the sorted part the moment we're confronted with a value that is less than or equal to the value we need to insert.
The value that is put aside, can now be inserted on the position of the last shifted value.
75 is put aside, 88 is more than 75 and is copied to the right, 75 is placed on the position of the last shifted value ( original position of 88 ) : |
| [-sorted------------] [-unsorted-----------------------]
index 0 1 2 3 4
value 75 88 93 81 21 |
| 93 is put aside, 88 is less than 75, so 93 can be place on its own original position : |
| [-sorted-----------------------] [-unsorted------------]
index 0 1 2 3 4
value 75 88 93 81 21 |
| 81 is put aside, 93 is more than 81 and is copied to the right, 88 is more than 81 and is copied to the right, 75 is less than 81, so 81 is copied on the original position of the last shifted value ( 88 ) : |
| [-sorted----------------------------------] [-unsorted-]
index 0 1 2 3 4
value 75 81 88 93 21 |
| 21 is put aside, 93 is more than 21 and is copied to the right, 88 is more than 21 and is copied to the right, 81 is more than 21 and is copied to the right, 75 is more than 21 and is copied to the right, 21 is placed on the original position of the last shifted value ( 75 ) : |
| [-sorted-----------------------------------------------]
index 0 1 2 3 4
value 21 75 81 88 93 |
| Module InsertionSortExample
Sub Main()
Dim count As Integer = 5
Dim upperbound As Integer = count - 1
Dim numbers(upperbound) As Integer
Dim index As Integer
For index = 0 To upperbound
numbers(index) = (count ^ index) * 93 Mod 97 - (count \ (index + 1))
Next
Console.Write("unsorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Dim unsortedCount As Integer = count - 1
Do Until unsortedCount = 0
Dim startIndexUnsortedPart As Integer = count - unsortedCount
Dim backup As Integer = numbers(startIndexUnsortedPart)
index = startIndexUnsortedPart - 1
Do While index >= 0 AndAlso numbers(index) > backup
numbers(index + 1) = numbers(index)
index -= 1
Loop
numbers(index + 1) = backup
unsortedCount -= 1
Console.Write("temporary array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Loop
Console.Write("sorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.ReadLine()
End Sub
End Module
Download Broncode |
| Output : unsorted array : 88 75 93 81 21
temporary array : 75 88 93 81 21
temporary array : 75 88 93 81 21
temporary array : 75 81 88 93 21
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 |
Up
Predefined Sort Methods
| Although it is a good exercise on working with arrays, it is rarely necessary to code a sorting algorithm. For sorting one-dimensional arrays, predefined functionalities exist. |
| Module Example
Sub Main()
Dim count As Integer = 5
Dim upperbound As Integer = count - 1
Dim numbers(upperbound) As Integer
Dim index As Integer
Dim random As Random = New Random
For index = 0 To upperbound
numbers(index) = random.Next(1, 101)
Next
Console.Write("unsorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Array.Sort(numbers)
Console.Write("sorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.ReadLine()
End Sub
End Module
Download Broncode |
| Output : unsorted array : 24 37 88 82 46
sorted array : 24 37 46 82 88 |
| The shared method Sort from the class Array will sort array numbers ( "Quick Sort" ).
The random values assigned to the elements of the numbers array are here the result of the Next method of an instance ( an object ) of the Random class.
Later on more about this quicksort and Random class.
When other collection types ( other than one-dimensional arrays ) are used, it can be necessary to code your own sorting functionality. |
Up
Performance of the Sort Methods
| When an array of 5 elements is sorted using the selection sort, first 4 values need to be compared to find/select the smallest value, then 3 values are compared to select the smallest values, then 2 values. |
| With N elements : Maximum comparisons
if N = 5 : 4+3+2 = 9
if N = 10 : 9+8+7+6+5+4+3+2 = 44
if N = 20 : 19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2 = 189
generally : ( ( (N - 1) + 2 ) * (N - 2) ) / 2
or : ( ( N + 1 ) * (N - 2) ) / 2
or : ( N² + N - 2N - 2 ) / 2
or : ( N² - N - 2 ) / 2 |
| Expressed in Big-O : "O((N^2-N-2)/2)" or simplified "O(N^2)".
When an array of 5 elements is sorted using the bubble sort, first 4 comparisons are needed, then 3 comparisons, then 2.
Again running time is quadratic ( "O(N^2)" ).
When an array of 5 elements is sorted using the insertion sort, first a maximum of 4 values are compared and possibly shifted to the right, then maximum 3 comparisons, then maximum 2.
Again, but this time only in worst case scenario, running time is quadratic ( "O(N^2)" ).
In best case scenario only 1 comparison ( per value to insert ) is needed, so minimum running time is linear ( "O(N)" ). |
Up
Exercise
| Task :
Complete module ExerciseTask.
When a currency is added, insert the currency and conversion value in the arrays currencies and conversionValues at the correct position.
Strings can be compared using the operators <, >, <= and >=. Expression "ABC" < "ABD" for instance will be True, because "ABC" alphabetically comes before "ABD". |
| Module ExerciseTask
Sub Main()
Dim count As Integer = 10
Dim currencies As String() = {"ATS", "DEM", "ESP", "FIM", "FRF", _
"IEP", "ITL", "LUF", "NLG", "PTE"}
Dim conversionValues As Decimal() = {13.7603, 1.95583, 166.386, _
5.94573, 6.55957, 0.787564, _
1936.27, 40.3399, 2.20371, 200.482}
Do
Console.Write("Currencies : ")
Dim index As Integer
For index = 0 To count - 2
Console.Write(currencies(index) & " / ")
Next
Console.WriteLine(currencies(index))
Console.Write("Currency ? : ")
Dim currency As String = Console.ReadLine()
Dim found As Boolean
If found Then
Else
Console.Write("Add Currency ( Y/N ) ? : ")
Dim addCurrency As Char = Console.ReadLine()
If addCurrency = "y"c OrElse addCurrency = "Y"c Then
Console.Write("Conversion Value " & currency & _
" ( = 1 EUR ) ? : ")
Dim conversionValue As Decimal = Console.ReadLine()
End If
End If
Loop
End Sub
End Module
Download Broncode |
| Output : Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : <i>DEM</i>
Amount DEM ? : <i>1,95583</i>
Conversion : 1,95583 DEM = 1 EUR
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : <i>BEF</i>
Add Currency ( Y/N ) ? : <i>n</i>
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : <i>BEF</i>
Add Currency ( Y/N ) ? : <i>y</i>
Conversion Value BEF ( = 1 EUR ) ? : <i>40,3399</i>
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : <i>BEE</i>
Add Currency ( Y/N ) ? : <i>N</i>
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : <i>BEF</i>
Amount BEF ? : <i>40,3399</i>
Conversion : 40,3399 BEF = 1 EUR
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : |
| Module ExerciseSolution
Sub Main()
Dim count As Integer = 10
Dim currencies As String() = {"ATS", "DEM", "ESP", "FIM", "FRF", _
"IEP", "ITL", "LUF", "NLG", "PTE"}
Dim conversionValues As Decimal() = {13.7603, 1.95583, 166.386, _
5.94573, 6.55957, 0.787564, _
1936.27, 40.3399, 2.20371, 200.482}
Do
Console.Write("Currencies : ")
Dim index As Integer
For index = 0 To count - 2
Console.Write(currencies(index) & " / ")
Next
Console.WriteLine(currencies(index))
Console.Write("Currency ? : ")
Dim currency As String = Console.ReadLine()
Dim lowerbound As Integer = 0
Dim upperbound As Integer = count - 1
Dim middle As Integer
Dim found As Boolean = False
Dim done As Boolean = False
Do Until found OrElse done
middle = (lowerbound + upperbound) \ 2
found = (currency = currencies(middle))
If Not found Then
done = (upperbound - lowerbound < 1)
If Not done Then
If currency > currencies(middle) Then
lowerbound = middle + 1
Else
upperbound = middle - 1
End If
End If
End If
Loop
If found Then
Console.Write("Amount " & currencies(middle) & " ? : ")
Dim amount As Decimal = Console.ReadLine()
Console.WriteLine("Conversion : " & amount & " " & _
currencies(middle) & " = " & _
amount / conversionValues(middle) & " EUR")
Else
Console.Write("Add Currency ( Y/N ) ? : ")
Dim addCurrency As Char = Console.ReadLine()
If addCurrency = "y"c OrElse addCurrency = "Y"c Then
Console.Write("Conversion Value " & currency & _
" ( = 1 EUR ) ? : ")
Dim conversionValue As Decimal = Console.ReadLine()
ReDim Preserve currencies(count)
ReDim Preserve conversionValues(count)
count += 1
index = count - 1
Do While (index - 1 >= 0) AndAlso _
(currencies(index - 1) > currency)
currencies(index) = currencies(index - 1)
conversionValues(index) = conversionValues(index - 1)
index -= 1
Loop
currencies(index) = currency
conversionValues(index) = conversionValue
End If
End If
Loop
End Sub
End Module
Download Broncode |
This version ( published on 2008-06-24 ) is printed from http://www.studyvb.com, visit the website for more recent information.
|
