Sorting Algorithms: Implementing Bubble Sort Using Swift

In the previous article, we analyzed Merge Sort and made an implementation of it using an array extension. We’re going to keep looking at sorting algorithms, and this time it’s Bubble Sort that is up for inspection.

XCode Playground Files with implementations are available on this link.

What Is Bubble Sort?

Chances are that you’ve actually implemented some version of this algorithm before. Bubble Sort is a very common first resort when you need to sort a bunch of elements, but don’t have access to any standard library functions to carry out the operation. The name comes from how the algorithm carries out the sorting, where the largest elements seem to “bubble up” to the far end of the array.

The time complexity of Bubble Sort is in the O(n²) division, which makes it a pretty slow moving algorithm when sorting large amounts of data. However, the sorting is done in-place and the overhead costs for starting up are pretty much non-existent. This means that, compared to Merge Sort or Heap Sort, Bubble Sort will still have a decent computation time on smaller data sets (say less than 100 elements). Another good thing about Bubble Sort is that we can design it so that it performs considerably better than O(n²) on arrays that are close to being sorted. The closer to…