Bubble Sort
What is a Bubble Sort?
A bubble sort compares adjacent items e.g. 1 and 2, 2 and 3 etc.
The largest values will ‘bubble’ to the top
If the first item is larger than the second then items are swapped
Repeats the process from the beginning of the list with the unsorted part of the list
Stops when no further swaps take place
By Swfung8 - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14953478
Bubble Sort Example - Cards
We will look at the following list of cards and perform 2 passes of a bubble sort algorithm. A reminder that when performing a bubble sort a pass is one complete iteration through the list.
After 1 Pass
After 2 Passes
Bubble Sort Example
Algorithm - Fixed Loop Bubble Sort
A bubble sort can be implemented using a fixed loop or a conditional loop. We will look at the fixed loop implementation first.
Pseudocode - Fixed Loop Bubble Sort
What the outer loop (first loop) does is ensure that the place the new values in their correct position - the first value to be put in its final position will be a maximum of the length of the array - 2.
There is a length -1 condition as remember that a loop of 5 items will have a length of 5 but a maximum index of 4 so the last two pairs we want to check are in position [3] and [4]. The outer loop will start at length - 2 and go to 0 in steps of -1.
The inner loop compares the two values in adjacent positions and if they are in the incorrect position then they are swapped - using a temporary variable to hold one of the values.
Python Implementation - Bubble Sort - Fixed Loops
Bubble Sort Example
How do we know if a list is sorted when using a bubble sort??
If we use the bubble sort algorithm below - when we would we know when the list of cards below are sorted if we are using the algorithm?
Swaps are key
If we complete and entire pass through the array and compare the pairs of values making no swaps then we know that the list is sorted.
Bubble Sort - Conditional Loop
Bublle Sort - Conditional Loop (Python)
Swapping Parallel Arrays using Bubble Sort
We want to sort these two parallel arrays so that ages (and corresponding names) are in ascending order of age.
So we will run our algorithm below:
a problem...
Sorting Parallel Arrays
We will need to ensure that when we perform a swap that we swap the corresponding value in the other parallel array.
The elements in green will be swapped on the first iteration
Sorting Arrays of records
Similar to sorting parallel arrays but we are using the following record structure shown to the right
Our record structure
Our array of records
The highlighted Lines 13-15 ensure that we mimic the shifts in the second parallel array (names).
If there were more than two parallel arrays then you would need to repeat this bold section for each parallel array used.
Sorting arrays of objects
Sorting arrays of objects are similar to sorting arrays of records except you must ensure that where applicable you use the appropriate getter method to access a relevant property.
You will notice that is very similar to the algorithm for sorting the record of arrays.
This time we use the appropriate getter method e.g. getAge() in order to retrieve the appropriate value of an instance variable for use in the comparison.
Sorting 2D Arrays
Sorting by a column
You can apply any sort algorithm to a 2D array. If you consider that the following 2D array with names and 5 scores
We want to sort the score array into alphabetical order (first column)
Initial State
We want to sort the score array into alphabetical order (first column)
Goal state
The whole rows have now been swapped to their final position
Sorting by rows
We want to sort the scores in each row into ascending order
Initial State
We want to sort the scores in each row into ascending order
Goal state
We have sorted the scores in each row into ascending order
