Bubble Sort - Algorithm, Visualization, Examples

Visualization Player

Problem Statement

Given an array of integers, your task is to sort the array in ascending order using the Bubble Sort algorithm.

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The largest unsorted element 'bubbles up' to its correct position after each pass.

Your goal is to return the sorted array after all necessary passes are completed.

Examples

Input Array Sorted Output Description
[5, 1, 4, 2, 8] [1, 2, 4, 5, 8] Multiple elements in random order; standard caseVisualization
[3, 2, 1] [1, 2, 3] Completely reverse sorted; maximum swaps neededVisualization
[1, 2, 3] [1, 2, 3] Already sorted; best case (0 swaps)Visualization
[7] [7] Single-element array is always sortedVisualization
[] [] Empty array; nothing to sort
[4, 2, 2, 8, 4] [2, 2, 4, 4, 8] Array with duplicate valuesVisualization
[5, -1, 0, -3] [-3, -1, 0, 5] Array with negative numbersVisualization

Solution

Step-by-Step Solution: Understanding and Applying Bubble Sort

Problem Understanding: We are given an array of numbers and asked to sort them in increasing order. One simple way to do this is using Bubble Sort, a sorting algorithm that compares adjacent elements and repeatedly swaps them if they are in the wrong order.

The key idea is to "bubble up" the largest elements to the end of the array with each full pass through the list. This continues until the array is completely sorted.

Let’s Solve It with an Example:

Given the array: [5, 1, 4, 8, 2]

  1. Start with the first two elements: 5 and 1. Since 5 > 1, we swap them. Now the array becomes: [1, 5, 4, 8, 2]
  2. Compare 5 and 4. Swap again → [1, 4, 5, 8, 2]
  3. Compare 5 and 8. No swap needed.
  4. Compare 8 and 2. Swap → [1, 4, 5, 2, 8]

After the first pass, the largest number (8) is at the end. We repeat the process for the rest of the array (ignoring the sorted part at the end) until no more swaps are needed.

Handling Edge Cases

  • Reverse Sorted Array (Worst Case): [3, 2, 1]
    Each element needs to travel all the way to its correct position. This requires the most comparisons and swaps.
  • Already Sorted Array (Best Case): [1, 2, 3]
    If we add a small check to see whether any swaps were made in a pass, the algorithm can exit early. This saves time!
  • Array with Duplicates: [4, 2, 2, 8, 4]
    Bubble Sort doesn’t mind repeated numbers. It compares them like any other values and puts them in the correct order: [2, 2, 4, 4, 8].
  • Array with Negative Numbers: [5, -1, 0, -3]
    Works the same way. Negative numbers are handled just like positive ones. Final result: [-3, -1, 0, 5].
  • Single Element: [7]
    No sorting is needed. The array is already sorted by default.
  • Empty Array: []
    There's nothing to sort. The algorithm simply returns the empty array.

Final Thoughts:

Bubble Sort is great for understanding how sorting works because it’s simple and easy to follow. However, for large datasets, more efficient algorithms are preferred.

Algorithm Steps

  1. Start from the first element in the array.
  2. Compare the current element with the next element.
  3. If the current element is greater than the next element, swap them.
  4. Move to the next element and repeat steps 2 and 3 for the entire array.
  5. After one complete pass, the largest element will be at the end.
  6. Repeat the process for the remaining unsorted elements (excluding the last sorted ones).
  7. Continue until the array is completely sorted.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        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;
            }
        }
    }
}
int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the array is already sorted. Bubble Sort makes one pass through the array without any swaps, and with an optimized version that checks for swaps, it terminates early. Hence, the time complexity is linear.
Average CaseO(n^2)On average, Bubble Sort compares and possibly swaps each pair of elements in a nested loop. This results in roughly n*(n-1)/2 operations, leading to quadratic time complexity.
Worst CaseO(n^2)In the worst case (when the array is sorted in reverse order), Bubble Sort performs the maximum number of comparisons and swaps, resulting in n*(n-1)/2 operations — hence, O(n^2).

Space Complexity

O(1)

Explanation: Bubble Sort is an in-place sorting algorithm. It requires only a constant amount of extra space for swapping elements — typically a temporary variable and loop counters.

Detailed Step by Step Example

Let us take the followign array, and apply Bubble Sort algorithm to sort the array.

{ "array": [6,3,8,2,7,4], "showIndices": false, "specialIndices": [] }

Pass 1

➜ Comparing 6 and 3

{ "array": [6,3,8,2,7,4], "showIndices": false, "highlightIndices": [0,1], "highlightIndicesGreen": [], "specialIndices": [] }

6 > 3.
Swap 6 and 3.
We need to arrange them in ascending order.

{ "array": [3,6,8,2,7,4], "showIndices": false, "highlightIndicesBlue": [0,1], "highlightIndicesGreen": [], "specialIndices": [] }

➜ Comparing 6 and 8

{ "array": [3,6,8,2,7,4], "showIndices": false, "highlightIndices": [1,2], "highlightIndicesGreen": [], "specialIndices": [] }

6 <= 8.
No swap needed.
They are already in ascending order.

➜ Comparing 8 and 2

{ "array": [3,6,8,2,7,4], "showIndices": false, "highlightIndices": [2,3], "highlightIndicesGreen": [], "specialIndices": [] }

8 > 2.
Swap 8 and 2.
We need to arrange them in ascending order.

{ "array": [3,6,2,8,7,4], "showIndices": false, "highlightIndicesBlue": [2,3], "highlightIndicesGreen": [], "specialIndices": [] }

➜ Comparing 8 and 7

{ "array": [3,6,2,8,7,4], "showIndices": false, "highlightIndices": [3,4], "highlightIndicesGreen": [], "specialIndices": [] }

8 > 7.
Swap 8 and 7.
We need to arrange them in ascending order.

{ "array": [3,6,2,7,8,4], "showIndices": false, "highlightIndicesBlue": [3,4], "highlightIndicesGreen": [], "specialIndices": [] }

➜ Comparing 8 and 4

{ "array": [3,6,2,7,8,4], "showIndices": false, "highlightIndices": [4,5], "highlightIndicesGreen": [], "specialIndices": [] }

8 > 4.
Swap 8 and 4.
We need to arrange them in ascending order.

{ "array": [3,6,2,7,4,8], "showIndices": false, "highlightIndicesBlue": [4,5], "highlightIndicesGreen": [], "specialIndices": [] }

8 is now at its correct position.

{ "array": [3,6,2,7,4,8], "showIndices": false, "highlightIndicesGreen": [5], "specialIndices": [] }

Pass 2

➜ Comparing 3 and 6

{ "array": [3,6,2,7,4,8], "showIndices": false, "highlightIndices": [0,1], "highlightIndicesGreen": [5], "specialIndices": [] }

3 <= 6.
No swap needed.
They are already in ascending order.

➜ Comparing 6 and 2

{ "array": [3,6,2,7,4,8], "showIndices": false, "highlightIndices": [1,2], "highlightIndicesGreen": [5], "specialIndices": [] }

6 > 2.
Swap 6 and 2.
We need to arrange them in ascending order.

{ "array": [3,2,6,7,4,8], "showIndices": false, "highlightIndicesBlue": [1,2], "highlightIndicesGreen": [5], "specialIndices": [] }

➜ Comparing 6 and 7

{ "array": [3,2,6,7,4,8], "showIndices": false, "highlightIndices": [2,3], "highlightIndicesGreen": [5], "specialIndices": [] }

6 <= 7.
No swap needed.
They are already in ascending order.

➜ Comparing 7 and 4

{ "array": [3,2,6,7,4,8], "showIndices": false, "highlightIndices": [3,4], "highlightIndicesGreen": [5], "specialIndices": [] }

7 > 4.
Swap 7 and 4.
We need to arrange them in ascending order.

{ "array": [3,2,6,4,7,8], "showIndices": false, "highlightIndicesBlue": [3,4], "highlightIndicesGreen": [5], "specialIndices": [] }

7 is now at its correct position.

{ "array": [3,2,6,4,7,8], "showIndices": false, "highlightIndicesGreen": [4,5], "specialIndices": [] }

Pass 3

➜ Comparing 3 and 2

{ "array": [3,2,6,4,7,8], "showIndices": false, "highlightIndices": [0,1], "highlightIndicesGreen": [4,5], "specialIndices": [] }

3 > 2.
Swap 3 and 2.
We need to arrange them in ascending order.

{ "array": [2,3,6,4,7,8], "showIndices": false, "highlightIndicesBlue": [0,1], "highlightIndicesGreen": [4,5], "specialIndices": [] }

➜ Comparing 3 and 6

{ "array": [2,3,6,4,7,8], "showIndices": false, "highlightIndices": [1,2], "highlightIndicesGreen": [4,5], "specialIndices": [] }

3 <= 6.
No swap needed.
They are already in ascending order.

➜ Comparing 6 and 4

{ "array": [2,3,6,4,7,8], "showIndices": false, "highlightIndices": [2,3], "highlightIndicesGreen": [4,5], "specialIndices": [] }

6 > 4.
Swap 6 and 4.
We need to arrange them in ascending order.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesBlue": [2,3], "highlightIndicesGreen": [4,5], "specialIndices": [] }

6 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesGreen": [3,4,5], "specialIndices": [] }

Pass 4

➜ Comparing 2 and 3

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndices": [0,1], "highlightIndicesGreen": [3,4,5], "specialIndices": [] }

2 <= 3.
No swap needed.
They are already in ascending order.

➜ Comparing 3 and 4

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndices": [1,2], "highlightIndicesGreen": [3,4,5], "specialIndices": [] }

3 <= 4.
No swap needed.
They are already in ascending order.

4 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesGreen": [2,3,4,5], "specialIndices": [] }

Pass 5

➜ Comparing 2 and 3

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndices": [0,1], "highlightIndicesGreen": [2,3,4,5], "specialIndices": [] }

2 <= 3.
No swap needed.
They are already in ascending order.

3 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesGreen": [1,2,3,4,5], "specialIndices": [] }

Pass 6

2 is now at its correct position.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [] }

Array is fully sorted.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...