Summary
| Algorithm Name | Bubble Sort | |
| Category |  Sorting Algorithms | |
| Core Technique | Compare, swap, and bubble the largest to the top, step by step. | |
| Best Case Time Complexity | Ω(n) | Linear |
| Average Case Time Complexity | Θ(n^2) | Quadratic |
| Worst Case Time Complexity | O(n^2) | Quadratic |
| Space / Memory Complexity | O(1) | In-place |
Intro
Bubble sort is one of the most common sorting algorithms. It is a really simple sorting algorithm, but it is a very inefficient algorithm to handle large set of data.
In this algorithm, we go through the data set, and bubble up the largest number(item) to the end of the list. We do it one by one, and by traversing through the set of data, and swapping the largest number to the end.
Use Cases
Bubble sort is not a very efficient algorithm(with the complexity of O(n^2), and that’s why there are no significant use cases we can recommend for this algorithm.
Mostly used for educational purposes or to explore the sorting mechanism.
Algorithm Visualizer
Let’s visualize how the numbers are bubbled up, one by one, in a Bubble sort algorithm-
Enter integers separated by commas(Example: 5,3,8,4,2,7,1,9,6).
Click ‘Start Sorting’ to visualize bubble sort.
Click ‘Reset’ to clear and re-enter numbers.
Click ‘Start Sorting’ to visualize bubble sort.
Click ‘Reset’ to clear and re-enter numbers.
Bubble Sort Visualizer Logs…
Implementation Steps
Keep the elements of the items(that we want to sort) in an array, or any other similar data structure. We are assuming that items are in an array, and it has N number of elements..
Now let’s start processing step by step-
- Start with the first elemetn of the array. The first element is selected/marked as “current” element, at this point.
- Compare the current element with the next element.
- If the current element is larger than the next element, then swap those two. This way, the largest element goes to the right.
- If the current element is smaller(or equal) than the next element, then do nothing.
- Move to the next element, and repeat this process, of Step #2, for all the elements, till the end of the array. This way, the largest element will be moved to the last place of the array.
- Next time, run this process from the beginning, to one less element at the end. As, after each full loop, the last element will be at the end of the array.
- Ignore one more last element each time the process is run.
- Repeat the process from Step #1 to Step #5 until the full array is sorted.
- When a full swap is done, for N-1 elements, then stop. So we do not need to do anything when only the first element is left.
Pseudocode
Here is the pseudocode for Bubble sort. I will make the implementation steps clear-
// Pseudocode for Bubble Sort
procedure BubbleSort(array A)
n = length(A) // Get the size of the array
// Outer loop for each pass
for i from 0 to n-1 do
// Inner loop compares adjacent elements
// Last i elements are already sorted, so we can skip them
for j from 0 to n-i-2 do
if A[j] > A[j+1] then // If current element is greater than next
swap A[j] and A[j+1] // Swap them
end if
end for
end for
end procedureWe can improve the processing by adding a check for is swapped. If there was no swapping in the last loop, that means the rest of the elements are already sorted.
// Pseudocode for Bubble Sort
// Improved version with is swapped checking
procedure BubbleSort(array A)
n = length(A) // Get the size of the array
// Outer loop for each pass
for i from 0 to n-1 do
swapped = false // Flag to check if any swap happened in this pass
// Inner loop compares adjacent elements
// Last i elements are already sorted, so we can skip them
for j from 0 to n-i-2 do
if A[j] > A[j+1] then // If current element is greater than next
swap A[j] and A[j+1] // Swap them
swapped = true // Mark that a swap occurred
end if
end for
// If no swaps happened in this pass, array is already sorted
if swapped == false then
break // Stop early
end if
end for
end procedure
Implementation
/**
* Bubble Sort Algorithm
* @param {number[]} arr - The array to sort
* @returns {number[]} - The sorted array
*/
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) { // If elements are in wrong order
// Swap them
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// Or you can use a temporary variable
// let temp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = temp;
}
}
}
return arr;
}Demo
const demoCases = [
{ name: "Random order", arr: [5, 3, 8, 4, 2] },
{ name: "Already sorted", arr: [1, 2, 3, 4, 5] },
{ name: "Reverse sorted", arr: [5, 4, 3, 2, 1] },
{ name: "With duplicates", arr: [3, 1, 2, 3, 2, 1] },
{ name: "Single element", arr: [42] },
{ name: "Empty array", arr: [] }
];
demoCases.forEach(({ name, arr }) => {
const inputArr = [...arr]; // Copy to avoid mutation
const sortedArr = bubbleSort(inputArr);
console.log(`\nCase: ${name}`);
console.log("Input Array:", arr);
console.log("Sorted Array:", sortedArr);
});Output:
Case: Random order
Input Array: [ 5, 3, 8, 4, 2 ]
Sorted Array: [ 2, 3, 4, 5, 8 ]
Case: Already sorted
Input Array: [ 1, 2, 3, 4, 5 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: Reverse sorted
Input Array: [ 5, 4, 3, 2, 1 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: With duplicates
Input Array: [ 3, 1, 2, 3, 2, 1 ]
Sorted Array: [ 1, 1, 2, 2, 3, 3 ]
Case: Single element
Input Array: [ 42 ]
Sorted Array: [ 42 ]
Case: Empty array
Input Array: []
Sorted Array: []Tests
import { describe, it, beforeEach, expect } from "vitest";
import bubbleSort from "./bubble-sort.js";
describe("Bubble Sort", () => {
it("should sort an array of numbers in ascending order", () => {
const sortedArr = bubbleSort([5, 3, 8, 4, 2]);
expect(sortedArr).toEqual([2, 3, 4, 5, 8]);
});
it("should handle an already sorted array", () => {
const sortedArr = bubbleSort([1, 2, 3, 4, 5]);
expect(sortedArr).toEqual([1, 2, 3, 4, 5]);
});
it("should handle an array with duplicate values", () => {
const sortedArr = bubbleSort([3, 1, 2, 3, 2, 1]);
expect(sortedArr).toEqual([1, 1, 2, 2, 3, 3]);
});
it("should handle an empty array", () => {
const sortedArr = bubbleSort([]);
expect(sortedArr).toEqual([]);
});
it("should handle an array with a single element", () => {
const sortedArr = bubbleSort([42]);
expect(sortedArr).toEqual([42]);
});
it("should handle an array with all identical elements", () => {
const sortedArr = bubbleSort([7, 7, 7, 7]);
expect(sortedArr).toEqual([7, 7, 7, 7]);
});
it("should handle an array with negative numbers", () => {
const sortedArr = bubbleSort([3, -1, -4, 2, 0]);
expect(sortedArr).toEqual([-4, -1, 0, 2, 3]);
});
it("should handle an array with very large and very small numbers", () => {
const sortedArr = bubbleSort([999999, -999999, 0, 1, -1]);
expect(sortedArr).toEqual([-999999, -1, 0, 1, 999999]);
});
it("should handle an array with non-integer numbers", () => {
const sortedArr = bubbleSort([2.5, 3.1, 1.2, 4.8]);
expect(sortedArr).toEqual([1.2, 2.5, 3.1, 4.8]);
});
it("should handle an array with only two elements", () => {
const sortedArr = bubbleSort([2, 1]);
expect(sortedArr).toEqual([1, 2]);
});
it("should handle an array with a single repeated value and others", () => {
const sortedArr = bubbleSort([1, 2, 1, 3, 1]);
expect(sortedArr).toEqual([1, 1, 1, 2, 3]);
});
});Source Code
| Source Code of | Implementation Code | Demo Code | Test Case Code | Benchmark Code |
|---|---|---|---|---|
| Bubble Sort Visualizer | Bubble Sort Visualizer – GitHub | |||
| Bubble Sort Pseudocode | Bubble Sort Pseudocode – GitHub Bubble Sort Improved Pseudocode – GitHub | |||
| Bubble Sort Implementation in JS | Bubble Sort Implementation in JS – GitHub | Bubble Sort Demo in JS – GitHub | Bubble Sort Tests in JS – GitHub | Bubble Sort Benchmark in JS – GitHub |