Data Structures & Algorithms in Swift: Part 4 — Bubble Sort

Published in

Mac O’Clock

3 min readApr 23, 2020

Bubble sort is the most basic and simplest sorting algorithm used to sort small datasets. This algorithm is not very efficient with a time complexity of O(n2). Although it is space-efficient as it an in place sorting algorithm which basically means it does not need any extra space to sort all the elements of a collection.

Things to note about Bubble Sort

It compares & swaps adjacent values one by one.
In every pass, large values come at the end.
Best case time complexity is O(n), this happens when an array is already sorted.
Worst-case time complexity is O(n2).
It requires n — 1 passes to complete the sort where n is the number of elements in the collection.

Understanding Bubble Sort with an example

Let’s take an array as an example and we go through the steps involved in sorting it using bubble sort. We will sort this array in ascending order.

var arrayToSort = [10, 5, 20, 1]

Pass 1: We will compare 10 and 5 , 10 is greater than 5 so we will swap them. Now our array is [5, 10, 20, 1]
Now we will compare 10 and 20 , they are in the correct order so we will move on to the next step without swapping any values
Now we will compare 20 and 1 , 20 is greater than 1 so we will swap those values and now our array is [5, 10, 1, 20]

Pass 2: After completion of pass 1, the largest value has come to the last index of the array, so now we will run pass 2 from 0th element to the second last element of the array. We will start by comparing 5 and 10 but they are already in the correct order so we will move on to comparing 10 and 1 , here 10 is greater than 1 so we will swap them and our array will be [5, 1, 10, 20]

Pass 3: This will be the final pass as the total number of passes is equal to n-1
We will compare 5 and 1 , 5 is greater than 1 so we will swap them and our array after sorting will look like this [1, 5, 10, 20]

Implementation

We have created a method bubbleSort which takes an array as a parameter which we need to sort. We have used inout keyword so that Swift will not make a copy of array instead it will pass the address of the original array and we can sort in place.

We are first checking if the array length is greater than 1, if it is equal to 1 then we immediately return as an array of length 1 is already sorted.

After that, we have simply used 2 for loops which are comparing adjacent values and swapping them if a greater value is present at lower index. This code simply does what we went through in Understand bubble sort with an example section.