Introduction
I like to imagine bubble sort as an algorithm where adjacent elements within individual bubbles are repeatedly swapped if they're in the wrong order.
Let's break down bubble sort, covering everything from its pros and cons and an implementation within C, to a calculation of its time complexity.
So... Why Bubble Sort?
While bubble sort is relatively simpler and generally uses less system resources than other sorting algorithms, it does certainly skimp on efficiency.
Let's enumerate some of the pros and cons of this searching method.
Advantages:
Relatively easy to understand and implement
In-place algorithm
does not require additional memory usage (e.g. creation of new arrays)
Stable algorithm
elements with the same value retain their index's relative order from the original array
Practical for smaller datasets
Disadvantages:
Impractical for larger datasets
time complexity of Ο(n^2)
Unnecessary Comparisons
will continue to compare pairs of values despite the array being sorted
large number of swaps harms time efficiency
Bubble Sort in C
Before we jump into a formal implementation of bubble sort in C, let's break it down step by step:
Loop over the array from the first element to the second last element
Then, loop over the array again from the first element to the second last element, decreasing the size by one each time (i.e. on the first iteration of the outer loop, inner loop goes from 0 to n - 1, on the second iteration, 0 to n - 2, ...)
The program then compares each element to the element to its right
If the element to the right is less than the current element, swap the values
After each iteration of the outer loop, the last element should be in the correct position
Finally, if no swaps occur, the array is sorted, and the program exits early
Although it sounds a bit complicated in English, maybe seeing the algorithm in action will clear up any confusion--let's use the list [ 5, 3, 9, 8] to simulate bubble sort.
Note that blocks filled with blue are those being compared.
At step 6, the list is officially sorted.
Now, onto the actual code...
Note that the comments (denoted with //) can be helpful in understanding what each part of the program does!
#include <stdbool.h>
#include <stdio.h>
// swaps the addresses rather than values
// of the parameters to bypass problem of scope
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// function performing bubble sort
void bubbleSort(int arr[], int len)
{
// tracks whether any values have been swapped / if the list
// is already sorted or not
bool swapped;
// loops over length of the list - 1 because if the rest left
// half is sorted, the final value must also be sorted
for (int i = 0; i < len - 1; i++) {
swapped = false;
// loops over length of list - i - 1 because every time
// the outer loop completes, the last element in the list
// is sorted and doesn't need to be looped over again
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// passes the addresses of array elements
swap(&arr[j], &arr[j + 1]);
swapped = true;
}
}
// if no two elements were swapped by inner loop,
// then exit loop
if (swapped == false)
break;
}
}
// function to print array
void printArray(int arr[], int len)
{
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int len = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, len);
printArray(arr, len);
return 0;
}Calculating Time Complexity
Computer scientists measure algorithmic efficiency by calculating its time complexity, written using Big-O Notation (worst case scenario) and Big-Omega Notation (best case scenario), on which you can find more about in my CS50's Week 3 blog!
Let's find the upper and lower bounds of bubble sort.
Best Case Scenario: all elements in the array are pre-sorted
Because of that if statement constantly checking whether any swaps were made during one iteration of the outer loop, we know that in the best case, the outer loop will run once, and the inner loop, n - i - 1 times.
Mathematically...
0 n - i - 2 0
Σ Σ c = Σ c(n - i - 1) = c(n - 1)
i = 0 j = 0 i = 0
Since n is the most prominent term, we can express the lower bound of binary search as Ω(n).
Worst Case Scenario: all elements in the array are in reverse order
In this case, our if statement will never result in true, meaning both the outer and inner loop will run the maximum number of times.
Again...
n - 2 n - i - 2 n - 2
Σ Σ c = Σ c(n - 1 - i) = c[(n - 1)(n - 1) - (n - 2)(n - 1)/2] = (c/2)(n)(n - 1)
i = 0 j = 0 i = 0
Because the most prominent term is n^2, we can express this upper bound as Ο(n^2).
Final Thoughts
While bubble sort certainly is one of the easier ones to implement, you might want to consider algorithms like merge sort if you're dealing with larger datasets.
That's all for bubble sort!
Comments