|
| 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 |
Predefined Sort Methods - Quick Sort
| 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 ? : DEM
Amount DEM ? : 1,95583
Conversion : 1,95583 DEM = 1 EUR
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Add Currency ( Y/N ) ? : n
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Add Currency ( Y/N ) ? : y
Conversion Value BEF ( = 1 EUR ) ? : 40,3399
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEE
Add Currency ( Y/N ) ? : N
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Amount BEF ? : 40,3399
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 |
|
|
|
