Bubblesort is a simple sorting algorithm that is often taught as the first sort a student will be exposed to. This is because of its ease in understanding and ease in coding. However it has a drawback of terrible runtime complexity.

Bubblesort is a sorting algorithm where a current element is compared to all elements proceeding it. Elements are swapped based on their values to ensure the sequence of elements are either monotonically increasing or decreasing.

Let's look at an example of what this might mean. We are given an array arr=[3,7,5,6]. We wish to sort it such that we end up with arr=[3,5,6,7]. We start with two pointers, one for our current element, and one for our next element. Based on the definition, lets look at what occurs at each step.

• p01=3 p02=7 arr=[3,7,5,6]. No swap.
• p01=3 p02=5 arr=[3,7,5,6]. No swap.
• p01=3 p02=6 arr=[3,7,5,6]. No swap. We've reach the end of the array, increment p01 and set p02 to the element proceeding it.
• p01=7 p02=5 arr=[3,7,5,6]. Swap 7 with 5.
• p01=5 p02=6 arr=[3,5,7,6]. No swap. Reset pointers.
• p01=7 p02=6 arr=[3,5,7,6]. Swap seven with six. Reached end of array.
• arr=[3,5,6,7]. Final array.

So how long did this take? There were three, then two, then one comparisons. Generally, where n is the length of the array, n-1 + n-2 ... + n-k ... + 1. This is known as an arithmetic sequence. From this we know that the sum will be equal to

The first term is a_1 = n-1 and the last term is a_n = 1. Substituting these in we get.

Giving us a runtime complexity of O(n^2). Since swaps occur in place, the space complexity is O(1). At a high enough scale, this quadratic complexity is too high. As we will learn in the next lesson, there exists sorting algorithms that have better runtime complexity at the cost of larger space complexity.

Let's see what this algorithm looks like in code.

Practice Question