Faangprep Logo
Log inStart free
Browse curriculum

Bubble Sort

Bubble sort is a sorting algorithm that only ever compares neighbours: each pass swaps any out-of-order adjacent pair, so the largest remaining value ends up at the end, in O(n²) time.

Intuition

Imagine air bubbles rising to the surface of water. The larger bubbles rise faster. Similarly, in Bubble Sort, the largest elements "bubble" to the top (end of the array) by repeatedly swapping with their neighbors.

Concept

Bubble sort only ever compares neighbours. Each pass walks the array once and swaps any adjacent pair that is out of order, so the largest remaining value drifts to the end of the unsorted part, like a bubble rising. After pass k, the last k positions are final. If a whole pass makes no swaps, the array is already sorted and the algorithm can stop early.

How it Works

  1. Start at the beginning of the array.
  2. Compare the first two elements. If the first is greater than the second, swap them.
  3. Move to the next pair and repeat.
  4. After one full pass, the largest element is guaranteed to be at the end.
  5. Repeat the process for the remaining unsorted elements.

Step-by-Step Breakdown

  1. Compare: Look at two neighbors.
  2. Swap?: If Left > Right, switch places.
  3. Move: Shift one step to the right.
  4. Repeat: Keep doing this until the biggest number reaches the end.
Trace: [5, 3, 8, 4, 2]
Pass 1
STEP 1
53842

Compare 5 > 3? YES

Swap them.
Result

[3, 5, 8, 4, 2]

STEP 2
35842

Compare 5 > 8? NO

Order is correct. No swap.
Result

[3, 5, 8, 4, 2]

STEP 3
35842

Compare 8 > 4? YES

8 bubbles up past 4.
Result

[3, 5, 4, 8, 2]

STEP 4
35482

Compare 8 > 2? YES

8 bubbles to the end.
Result

[3, 5, 4, 2, 8]

Pass 1 Complete: Largest element (8) is now sorted!

When to Use

  • Educational Purposes: It's the simplest algorithm to implement and understand concepts like swapping.
  • Small Datasets: When N is very small (e.g., < 20), the O(n²) penalty is negligible.
  • Nearly Sorted Data: With the "swapped" flag optimization, it runs in O(n) for already sorted arrays.

When NOT to Use

  • Large Datasets: O(n²) complexity makes it impractical for N > 10,000.
  • Performance Critical Systems: Merge Sort or Quick Sort are significantly faster (O(n log n)).

How to Identify

You likely won't use Bubble Sort directly in an interview unless asked, but you might need the "adjacent swap" concept. If a problem asks for the "minimum number of adjacent swaps to sort an array", it is directly related to the number of inversions.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Rabin-Karp

Next

Selection Sort

Frequently Asked Questions

Why is it called "Bubble Sort"?

The algorithm gets its name because smaller elements "bubble" to the top while larger elements sink to the bottom, much like bubbles in water.

Is Bubble Sort stable?

Yes, Bubble Sort is a stable sorting algorithm. It maintains the relative order of equal elements.

What is the time complexity of Bubble Sort?

The average and worst-case time complexity is O(n²). However, with a "swapped" flag optimization, the best-case complexity for a sorted array is O(n).