SDD Topic has been refreshed!

Bubble Sort

What is a Bubble Sort?

Algorithm - Fixed Loop Bubble Sort

Pseudocode - Fixed Loop Bubble Sort

Python Implementation - Bubble Sort - Fixed Loops

Bubble Sort - Conditional Loop

Bublle Sort - Conditional Loop (Python)

Swapping Parallel Arrays using Bubble Sort

Sorting Parallel Arrays

Sorting Arrays of records

Sorting arrays of objects

Sorting 2D Arrays

Sorting by a column

Sorting by rows

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.