Bubble Sort

sorting-algorithms

Definition

Bubble Sort

Bubble sort is an in-place sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each full pass, the largest remaining unsorted element has moved to the end of the list.

Complexity

Worst-case time

$O(n^2)$

This occurs when many inversions must be removed, for example in a reverse-sorted array. Bubble sort may need about $n$ passes, each scanning almost the whole array.

Average-case time

$O(n^2)$

On typical unsorted input, bubble sort still performs a quadratic number of comparisons and many swaps.

Best-case time

$O(n)$ with early termination

If the array is already sorted, one full pass detects that no swap is needed and the algorithm stops immediately.

Space

$O(1)$

Bubble sort works in place and uses only a constant amount of additional memory for temporary swapping.

Approach

Basic idea

Repeatedly scan the array from left to right. Whenever two adjacent elements $a_i$ and $a_{i+1}$ satisfy $a_i>a_{i+1}$, swap them. Stop when a complete pass performs no swap.

Example

One pass

For

$$[5,1,4,2]$$

one pass produces:

$$[1,5,4,2]\to [1,4,5,2]\to [1,4,2,5]$$

The largest element has moved to the end.