Bubble Sort
Time Complexity
| Best | Average | Worst |
|---|---|---|
| Ω(n) | Θ(n^2) | O(n^2) |
Space Complexity
| Worst |
|---|
| O(1) |
Overview
Bubble Sort is a simple comparison-based (yes, another one) sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list in each pass (just like an air bubble will bubble up from the bottom of a water tank to the top).
So here's how the Bubble Sort works step-by-step with the input from the animation [3, 2, 1, 6, 4, 5]:
Pass 1:
- Compare 3 and 2. Since 2 is smaller, swap them. List becomes
[2, 3, 1, 6, 4, 5]. - Compare 3 and 1. Since 1 is smaller, swap them. List becomes
[2, 1, 3, 6, 4, 5]. - Compare 3 and 6. No need to swap. List remains
[2, 1, 3, 6, 4, 5]. - Compare 6 and 4. Since 4 is smaller, swap them. List becomes
[2, 1, 3, 4, 6, 5]. - Compare 6 and 5. Since 5 is smaller, swap them. List becomes
[2, 1, 3, 4, 5, 6].
After the first pass, the largest element, 6, has "bubbled up" to the end of the list.
Pass 2:
- Compare 2 and 1. Since 1 is smaller, swap them. List becomes
[1, 2, 3, 4, 5, 6]. - Compare 2 and 3. No need to swap. List remains
[1, 2, 3, 4, 5, 6]. - Compare 3 and 4. No need to swap.
- Compare 4 and 5. No need to swap.
- Compare 5 and 6. No need to swap.
After the second pass, the second largest element, 5, has "bubbled up" to its correct position.
Pass 3:
- Compare 1 and 2. No need to swap. List remains
[1, 2, 3, 4, 5, 6]. - Compare 2 and 3. No need to swap.
- Compare 3 and 4. No need to swap.
- Compare 4 and 5. No need to swap.
- Compare 5 and 6. No need to swap.
After the third pass, the third largest element, 4, has "bubbled up" to its correct position.
Pass 4: (Optimization) In the animation, the algorithm continues with the next passes to illustrate how the algorithm will originally work, but this and the following passes require no swapping and are basically not needed because Bubble Sort can be optimized to avoid unnecessary passes when the list is already sorted. This optimization can significantly improve the algorithm's performance for partially or fully sorted lists.
The optimization involves adding a flag that tracks whether any swaps were made during a pass. If no swaps were made during a pass, it means the list is already sorted, and the algorithm can terminate early.
If we have optimized the algorithm, it will stop here with a sorted list. But if we've used the classical version of the algorithm as in the animation, we proceed as follows:
- Compare 1 and 2. No need to swap.
- Compare 2 and 3. No need to swap.
- Compare 3 and 4. No need to swap.
- Compare 4 and 5. No need to swap.
- Compare 5 and 6. No need to swap.
After the fourth pass, the fourth largest element, 3, has "bubbled up" to its correct position.
Pass 5:
- Compare 1 and 2. No need to swap.
- Compare 2 and 3. No need to swap.
- Compare 3 and 4. No need to swap.
- Compare 4 and 5. No need to swap.
- Compare 5 and 6. No need to swap.
After the fifth pass, the fifth largest element, 2, has "bubbled up" to its correct position.
Pass 6:
- Compare 1 and 2. No need to swap.
- Compare 2 and 3. No need to swap.
- Compare 3 and 4. No need to swap.
- Compare 4 and 5. No need to swap.
- Compare 5 and 6. No need to swap.
After the sixth pass, the sixth largest element, 1, has "bubbled up" to its correct position.
Now, the list is fully sorted in ascending order: [1, 2, 3, 4, 5, 6]. Bubble Sort has a time complexity of O(n^2) in the average and worst cases, and it's considered inefficient for large datasets. But just like Insertion and Selection Sort - it is easy to understand and implement and is great for learning, practicing and also for exams and interviews.
Code
These code examples use the optimized version with the 'swapped' flag since it's the most common form of the algorithm
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
# Example usage:
input_list = [3, 2, 1, 6, 4, 5]
sorted_list = bubble_sort(input_list)
print(sorted_list) # Output: [1, 2, 3, 4, 5, 6]
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) {
break;
}
}
return arr;
}
// Example usage:
const inputArray = [3, 2, 1, 6, 4, 5];
const sortedArray = bubbleSort(inputArray);
console.log(sortedArray); // Output: [1, 2, 3, 4, 5, 6]
import java.util.Arrays;
public class BubbleSort {
public static int[] bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return arr;
}
public static void main(String[] args) {
int[] inputArray = {3, 2, 1, 6, 4, 5};
int[] sortedArray = bubbleSort(inputArray);
System.out.println(Arrays.toString(sortedArray)); // Output: [1, 2, 3, 4, 5, 6]
}
}
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n; i++) {
int swapped = 0;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) {
break;
}
}
}
int main() {
int inputArray[] = {3, 2, 1, 6, 4, 5};
int n = sizeof(inputArray) / sizeof(inputArray[0]);
bubbleSort(inputArray, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", inputArray[i]);
}
printf("\n"); // Output: Sorted array: 1 2 3 4 5 6
return 0;
}function bubbleSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
$swapped = false;
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
list($arr[$j], $arr[$j + 1]) = array($arr[$j + 1], $arr[$j]);
$swapped = true;
}
}
if (!$swapped) {
break;
}
}
return $arr;
}
// Example usage:
$inputArray = [3, 2, 1, 6, 4, 5];
$sortedArray = bubbleSort($inputArray);
print_r($sortedArray); // Output: Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 )