# Bubble Sort in Swift

## The classic sorting algorithm

Difficulty: Beginner* | Easy | Normal | Challenging

• This is seen as a beginner topic (first year Computer Science degree fare) but is certainly not easy.

# Terminology

Algorithm: A process or set of rules to be followed

Big O Notation: A mathematical notation to describe the limiting behaviour of a function when an argument tends towards infinity

Bubble Sort: A sorting algorithm where the largest items bubble up one at a time

Sorting: Putting something into order. For example, to put 2,3,1 into order it would become 1,2,3.

Swap: The action of swapping two elements.

# Bubble Sort

The Bubble Sort Algorithm is so called because elements tend to bubble up into the correct order, much like bubbles rising to the surface.

Bubble Sort is typically used for studying sorting rather than used in production code, and the implementation shown here is not recommended to be copied and pasted into production code under any circumstances!

## The algorithm

The Bubble Sort algorithm has the input of an unsorted array, and processes the array into a sorted array. The example here will produce an ascending sorted array.

Bubble Sort relies on repeatedly swapping adjacent elements (if they are in the wrong order) until the whole Array is sorted.

The pseudocode

Which obeys the following flowchart:

This can then be translated into Swift code. How can this be translated into Swift? It turns out that it isn’t too difficult.

This can then be called with `bubbleSort([1,3,6,2,4,5])`.

However, we do not know that works properly for all inputs. In order to do so we need to make this work as a function, and also write tests that will be suitable to test the functionality of our Bubble Sort implementation.

These tests are NOT complete, but are enough to give us some idea of whether the algorithms works. Now to get this to work in Playgrounds you will need to `import XCTest` and `BSTests.defaultTestSuite.run()`

which couples with the following BubbleSort function

# Different bubble sort implementations

We can use `swapAt(i: Int, j: Int) `to make the code slightly easier to read. Equally, I wouldn’t introduce a While loop in Swift due to the inelegant boolean introduced to tell whether a swap has taken place.

Rather, my approach would be to replace the while with another for loop — since we know how many iterations of the second loop needs to take place.

We need to recognise that the array must be longer than a single element (this makes sense, since an array with a single element is naturally already sorted — and this is ensured with a `guard` statement.

There is also a little efficiency saving here. We compare each element of the array with all other elements we don’t have to heck the end `i-1` elements that are already in place! This makes the algorithm slightly more efficient, but unfortunately the algorithm is still O(n²) as shown because there are two loops (one inside another) — making it a classic worst case scenario of O(n²).

# Conclusion

Bubble Sort is a tricky one. Often taught in Computer Science classes but seldom used in production (particularly since there is a better `sort()` algorithm built in Swift).

However, we have been through the process to implement Bubble Sort in Swift, and this should give you some idea of how this classic sorting algorithm works!

Any questions? You can get in touch with me HERE

Written by