Bubble Sort
Contents
Bubble Sort¶
Overview¶
Bubble Sort is a reasonably inefficient algorithm, but it is very straightforward to implement and understand. This is a naive algorithm to start our search for the efficient sort.
The basic idea behind Bubble Sort is to let elements float to the right spot.
To complete a Bubble Sort, we start at the beginning of the array. We compare the first two values. If they are not in the right order, we swap them. This puts those to elements in the right order, but might cause other a different issues. We repeatedly compare pairs of adjacent values until we reach the end of the array.
In one pass over the array, we may have moved some values into the correct positions. The array is closer to sorted, but we don’t know if it is completely sorted.
We can reset to the beginning and check again. Looking at every adjacent pair and swapping when we find issues. If we make it through all adjacent pairs without requiring any swaps, then the array is sorted. Doing more passes won’t change anything. We know we can stop.
The structure of the algorithm is laid out with two nested loops.
While the array is not sorted
Compare two adjacent values
Swap if not in order
To translate this into code we need some variables.
swapped: track if a swap happened in the last iteration
i: counter to track position
We start the at index i=1, because the first pair is A[0] and A[1]. We compare adjacent pairs until we reach the end of the list. If swapped was set to true at any point, then the list is not sorted yet. We reset to i=1 and start again.
Implementation¶
Implementing this sort requires two nested loops. The outer loop runs until the list is sorted. The inner loop makes swaps to fix values in incorrect positions.
If we go through the entire list and don’t need to do any swaps, then the list must be sorted. No elements are out of order, therefore they must all be in order.
Function bubblesort(pointer to array A, integer size)
Let swapped = true
While swapped do
swapped = false
Let i = 1
While i < size do
If A[i-1] > A[i] then
swap values at index i-1 and i of A
swapped = true
End If
i = i + 1
End While
End While
Return
End Function
Analysis¶
Imagine a general array A with n elements in it.
The best case situation for this algorithm is that the very first iteration makes no swaps. The outer loop executes exactly 1 time. The inner loop still has to look at \(n-1\) adjacent pairs. All the pairs were in order, so the list was sorted.
The best case runtime of the algorithm is \(O(n)\). It runs in linear time based on the size of the array.
What is the worst case situation? The worst case situation happens when the first iteration of the loop only puts one value in the correct place. We do the entire inner loop and only one value is correct. Then we need to loop again to fix the rest.
Imagine an array with \(n=6\) elements.
Outer Iteration |
Comparisons |
Correct Positions |
Incorrect Positions |
|---|---|---|---|
0 |
None |
0 |
6 |
1 |
5 |
1 |
5 |
2 |
5 |
2 |
4 |
3 |
5 |
3 |
3 |
4 |
5 |
4 |
2 |
5 |
5 |
5 |
0 |
6 |
5 |
6 |
0 |
At each iteration, we decrease the number of values in incorrect positions by 1. Eventually, we get to the point where there are only 2 incorrect values. When we swap these two, the array will be sorted. The algorithm won’t know that this swap fixed both values. It will need one additional iteration to detect that all value are in the correct place. Even if we could stop one iteration earlier, it would not effect the Big Oh runtime.
Each pass over the array looks at \(n-1\) adjacent pairs. We need to pass over the array a total of \(n\) times. Multiplying the two loops together tells is that we will need \(n*(n-1)=n^2-n\) comparisons.
The runtime of Bubble Sort is \(O(n^2)\).
The memory usage of Bubble Sort is \(O(1)\). We get a pointer to the array we are sorting, not a local copy. The algorithm only needs to store the pointer to the array. It does make a copy of the array size. It also needs two integers and one boolean.
Pointer to Array
Array Size
counter
iswapbooleantemp variable for swapping
We also need constant space for all the instructions and functions. All the memory use is constant.
The memory requirements for Bubble Sort are \(O(1)\).