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.