Bubble Sort

Sorting is one of the most fundamental operations in Data Structures and Algorithms. It is the process of arranging data elements in a specific order, such as ascending or descending order.

Among various sorting algorithms, Bubble Sort is one of the simplest and easiest sorting techniques to understand and implement.

Bubble Sort repeatedly compares two adjacent elements and swaps them if they are in the wrong order. This process continues until all elements are arranged correctly.

The algorithm is called Bubble Sort because after each pass, the largest element gradually moves toward the end of the array, similar to a bubble moving upward in water.

What is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm that repeatedly compares adjacent elements and exchanges their positions if they are not arranged in the required order.

In ascending order sorting:

  • If the left element is greater than the right element, they are swapped.
  • If the left element is smaller, no swap is performed.

The process is repeated multiple times until the entire array becomes sorted.

Working Principle of Bubble Sort

Bubble Sort works by performing multiple passes through the array.

During each pass:

  1. Adjacent elements are compared.
  2. Incorrectly ordered elements are swapped.
  3. The largest unsorted element moves to the end.

For an array containing n elements:

  • The first pass places the largest element.
  • The second pass places the second-largest element.
  • The process continues until all elements are sorted

Example: Bubble Sort

Let’s sort the array {5, 1, 4, 2, 8}

Pass 1

  • Compare 5 and 1 → swap → {1, 5, 4, 2, 8}
  • Compare 5 and 4 → swap → {1, 4, 5, 2, 8}
  • Compare 5 and 2 → swap → {1, 4, 2, 5, 8}
  • Compare 5 and 8 → no swap → {1, 4, 2, 5, 8}

Pass 2

  • Compare 1 and 4 → no swap
  • Compare 4 and 2 → swap → {1, 2, 4, 5, 8}
  • Compare 4 and 5 → no swap
  • Compare 5 and 8 → no swap

Pass 3

  • Compare 1 and 2 → no swap
  • Compare 2 and 4 → no swap
  • Compare 4 and 5 → no swap → sorted
  • Array is now sorted: {1, 2, 4, 5, 8}

When to Use Bubble Sort?

  • When simplicity is more important than efficiency
  • For teaching and learning purposes
  • When working with very small or nearly sorted arrays
  • To introduce the idea of sorting and swapping elements

Bubble Sort Algorithm

The basic Bubble Sort algorithm can be written as:

BubbleSort(array)

1. Start from the first element.

2. Compare each pair of adjacent elements.

3. If the first element is greater than the second element:
      Swap them.

4. Continue comparing until the end of the array.

5. Repeat the process for all elements.

6. Stop when the array becomes sorted.

Time and Space Complexity

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)If array is already sorted (with optimisation)
Average CaseO(n²)Nested loops for each element
Worst CaseO(n²)Array sorted in reverse order
SpaceO(1)In-place sorting, no extra memory used

Space Complexity

Bubble Sort does not require additional memory.

It performs swapping directly inside the array.

Therefore:

Space Complexity = O(1)

Bubble Sort is an in-place sorting algorithm.

Advantages of Bubble Sort

1. Simple to Understand

Bubble Sort is one of the easiest sorting algorithms.

It is commonly used for teaching basic sorting concepts.

2. Easy Implementation

The algorithm requires only:

  • Comparison
  • Swapping
  • Loops

3. Requires Less Memory

Since Bubble Sort is in-place:

Extra Space = O(1)

4. Stable Sorting

It maintains the order of equal elements.

Disadvantages of Bubble Sort

1. Slow for Large Data

Bubble Sort requires:

O(n²)

time in average and worst cases.

It becomes inefficient for large datasets.

2. Many Comparisons

Even when the array is almost sorted, many comparisons may be performed.

3. Less Efficient Than Advanced Algorithms

Algorithms like:

  • Merge Sort
  • Quick Sort
  • Heap Sort

perform much better for large data.

Bubble Sort Applications

Although Bubble Sort is not used for large-scale applications, it is useful in some situations.

1. Educational Purpose

Bubble Sort is widely used for teaching:

  • Sorting concepts
  • Algorithm analysis
  • Complexity calculation

2. Small Data Sets

For a small number of elements, Bubble Sort can be sufficient.

3. Detecting Sorted Data

The optimized version can quickly check whether data is already sorted.

Numerical Questions for Bubble Sort

  1. Sort {64, 34, 25, 12, 22, 11, 90} using Bubble Sort.
  2. Apply Bubble Sort on {9, 7, 5, 3, 1} and count the number of swaps.
  3. Sort the following array using Bubble Sort and show all the passes {5, 2, 9, 1, 5, 6}
  4. Apply Bubble Sort on the array {99, 88, 77, 66, 55} . Show How many total comparisons and swaps are needed?
  5. Sort the numbers using Bubble Sort {64, 25, 12, 22, 11} Count the total number of swaps performed.
Next Post
Sequential Search
1 person found this article helpful

Was this article helpful?