Introduction

Bubble Sort is one of the simplest sorting algorithms.

The idea is:

  • repeatedly compare adjacent elements
  • swap them if they are in wrong order
  • largest elements gradually move to the end

This movement looks like bubbles rising upward, hence the name:

 Bubble Sort

This problem helps in understanding:

  • sorting basics
  • swapping
  • nested loops
  • comparison-based sorting

Example

Input:arr = [5, 1, 4, 2, 8]
Output:
[1, 2, 4, 5, 8]

Explanation:
Adjacent elements are compared and swapped repeatedly until array becomes sorted.

Constraints

 1 <= arr.length <= 10^5-10^4 <= arr[i] <= 10^4

Approach 1 : Basic Bubble Sort

Explanation

The simplest way to sort using Bubble Sort is:

  1. Traverse array repeatedly
  2. Compare adjacent elements
  3. Swap if left element is greater
  4. Continue until array becomes sorted

After every pass:

  • largest unsorted element
    moves to correct position

Steps

  1. Traverse array.
  2. Compare adjacent elements.
  3. Swap if elements are unordered.
  4. Repeat for all passes.
  5. Return sorted array.

Dry Run

Input:[5, 1, 4, 2, 8]

Pass 1:
5 > 1

Swap:
[1, 5, 4, 2, 8]
5 > 4

Swap:
[1, 4, 5, 2, 8]
5 > 2

Swap:
[1, 4, 2, 5, 8]
5 < 8

No swap

Largest element fixed:
8

Continue remaining passes...

Final Result:
[1, 2, 4, 5, 8]

Basic Bubble Sort Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Nested loops compare all pairs.

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Approach 2 : Optimized Bubble Sort

Explanation

The optimized version improves performance by checking:

 Was any swap performed?

If no swap occurs:

  • array is already sorted
  • traversal stops early

This reduces unnecessary passes.

Steps

  1. Traverse array.
  2. Track swap occurrence.
  3. Swap unordered elements.
  4. If no swaps occur:
    • stop traversal early
  5. Return sorted array.

Dry Run

Input:[1, 2, 3, 4]

Pass 1:
1 < 2
No swap

2 < 3
No swap

3 < 4
No swap

No swaps occurred
Array already sorted

Final Result:
[1, 2, 3, 4]

Optimized Bubble Sort Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Already sorted array requires only one pass.

Average Case Time Complexity: O(n²)

Worst Case Time Complexity: O(n²)

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Edge Cases

  1. Empty array
  2. Single element array
  3. Already sorted array
  4. Reverse sorted array
  5. Duplicate elements present

Why This Problem is Important

Bubble Sort helps in understanding:

  1. Sorting fundamentals
  2. Swapping logic
  3. Nested loop traversal
  4. Comparison-based sorting
  5. In-place sorting

It is one of the most basic sorting algorithms taught in DSA.

Real-World Applications

Bubble Sort concepts are used in:

  1. Educational visualization
  2. Small datasets
  3. Embedded systems
  4. Sorting demonstrations
  5. Algorithm teaching tools

Common Mistakes

  1. Incorrect loop bounds
  2. Missing swap logic
  3. Wrong comparison conditions
  4. Forgetting optimization flag

Interview Tips

Interviewers often expect:

  1. Sorting fundamentals
  2. Time complexity explanation
  3. Optimization understanding

Always explain why:

  • largest element moves to end
    after every pass

Related Questions

  1. Selection Sort
  2. Insertion Sort
  3. Merge Sort
  4. Quick Sort
  5. Sort 0s 1s 2s

Final Takeaway

Bubble Sort is a fundamental sorting algorithm that teaches comparison-based sorting and swapping techniques. Understanding Bubble Sort builds a strong foundation for advanced sorting algorithms and interview problems.