10.2 Arrays (inc. sorting)
Specification
Candidates should be able to:
Use the technical terms associated with arrays - Including index, upper and lower bound
Select a suitable data structure (1D or 2D array) to use for a given task
Write pseudocode for 1D and 2D arrays
Write pseudocode to process array data
Sort using a bubble sort
Search using a linear search
As there is very little that can be added on top of the lesson slides or textbooks, this page will remain slimmed down.
Sort Comparison
Above are two interesting videos comparing different sort algorithms. You'll notice bubble sort is the worst performing. CIE only require you to know insertion and bubble sort from these.
Here are some of the same algorithms again, but in colour and with sound representing the sorted elements.
Finally, a more spaced out, hypnotic version
If you are interested in making your own visualisation, check out the Coding Train video (it uses Processing (Java)).
Bubble Sort
Here is my implementation of the bubble sort in VB,NET. I have also included an output of the elements following the sort.
Dim Array() = {33, 6, 5, 8, 3, 11, 1}
Dim OuterLoop, InnerLoop, Temp, Length As Integer
Length = Array.Length
For OuterLoop = Length - 1 To 1 Step -1
For InnerLoop = 0 To OuterLoop - 1
If Array(InnerLoop) > Array(InnerLoop + 1) Then ' Compare elements
Temp = Array(InnerLoop)
Array(InnerLoop) = Array(InnerLoop + 1)
Array(InnerLoop + 1) = Temp
End If
Next InnerLoop
Next OuterLoop
For Each a As Integer In Array
Console.WriteLine(a)
Next
Console.ReadLine()
The textbook (Chapter 10.2) gives more detail on bubble sorts. a more improved version of the algorithm that replaces the outer loop with a WHILE loop that ends execution once the inner loop completes without making any swaps. Try and re-create this with the code above.