One of the first, and arguably one of the worst, sorting algorithms many people learn or "reinvent" is the Bubble Sort. The name comes from the way values "bubble" up to the end or beginning of the array.
Bubble Sort Animation
Here's what these actions look like with a small dataset:
Credit: Swfung8, CC BY-SA 3.0, via Wikimedia Commons
Bubble Sort Big O Complexity
The big O complexity of bubble sort is $`O(n^2)`$, where n is the number of elements in the array. This is because insertion sort involves nested loops; for each element in the array, it may need to compare and shift elements multiple times. This requires nested loops, and the complexity therefore grows exponentially.
Bubble Sort Algorithm in Java
You'll see why it's the worst as you dig into the code, which sorts data in ascending order (from smallest to largest):
public static int[] bubbleSort(int[] nums){
int n = nums.length;
for (int i = 0; i <= n-2; i++) {
for (int j = 0; j <= n-i-2; j++) {
// check to see if the two adjacent elements are out of order
if (nums[j] > nums[j+1]) {
// if so, swap the two elements that are out of order
// create a copy of the value at "nums[j]"
int temp = nums[j];
// copy the value at "nums[j+1]" to "nums[j]"
nums[j] = nums[j+1];
// place the original value of "nums[j]"
// (that you created a copy of earlier) at "nums[j+1]"
nums[j+1] = temp;
}
}
}
// return the sorted array
return nums;
}
So, what's happening here? You set up two nested loops:
- The outer loop visits almost all the items in the array, from index 0 to index
n-2. - The inner loop also visits almost all the items but stops when it gets to the next to last item minus however many items are already sorted, given by the expression
n-i-2.
Why does the inner loop stop early like this? It ensures you have a place at the end of the array to put the largest item at index n-1. It also makes sure that value doesn't move again once it's set.
Within the inner loop, you compare the item at nums[j] to the next item nums[j+1] and swap the two values if they're larger. This has the effect of bubbling larger values through the array to the end, giving this algorithm its name.
You can see an animation of this below -- note how each value moves multiple times before it finally ends up at its final location:
One thing to note is the three lines of code inside the if statement:
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
This code swaps the two values at nums[j] and nums[j+1], using a single extra variable temp. This code is so heavily used in sorting algorithms it's often written as a separate method or function.
The presence of a nested for loop should give you some ideas about this algorithm and its Big O analysis. As mentioned, this algorithm has a complexity of $`O(n^2)`$, which is horrible for any but the smallest arrays. You can improve it somewhat by modifying some of the loops, but you can do much better by choosing a different algorithm.
Bubble Sort in Python
The Python example below defines a bubble_sort function that takes a list nums as a parameter and sorts the nums list using the bubble sort algorithm. The algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire list is sorted.
def bubble_sort(nums):
"""
This function performs the bubble sort algorithm on a list.
:param nums: A list of comparable elements
:return: The sorted list in ascending order
"""
n = len(nums)
# Iterate through all array elements
for i in range(n):
# Last i elements are already in place
# so you don't need to check them
for j in range(0, n - i - 1):
# Iterate the array from 0 to n-i-1
# Swap if the element found is greater than the next element
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
# Example usage:
unsorted_list = [87, 34, 566, 12, 900, 45, 862, 345]
sorted_list = bubble_sort(unsorted_list)
print("Sorted array:", sorted_list)
Summary: Bubble Sort
The most primitive sorting algorithm available, Bubble Sort, with a Big O complexity of $`O(n^2)`$ works by comparing each number to all the others, swapping their positions as needed to move them closer to their final sorted locations. The effect is that values move like bubbles in a soda toward their correct place. While Bubble Sort is good for small datasets, its Big O complexity makes it a poor choice when good performance is required.