Bubble Sort in Swift
The classic sorting algorithm
Difficulty: Beginner* | Easy | Normal | Challenging
This article covers the classic sorting algorithm Bubble Sort in Swift.
- This is seen as a beginner topic (first year Computer Science degree fare) but is certainly not easy.
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.
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 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.
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
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
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
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²).
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!
The Twitter contact:
Any questions? You can get in touch with me HERE