CS205

Bubble Sort

O(n²)

Repeatedly swaps adjacent elements if they are in the wrong order.

Bubble Sort
64
34
25
12
22
11
90
0
1
2
3
4
5
6
Ready to start
Step 0 of 0
Speed:500ms
Default
Comparing
Swapping
Sorted
Pivot
Algorithm Info

Repeatedly swaps adjacent elements if they are in the wrong order.

Best Case
O(n)
Average Case
O(n²)
Worst Case
O(n²)
Space
O(1)
How It Works
  1. Start at the beginning of the array
  2. Compare adjacent elements (position i and i+1)
  3. If they are in wrong order (arr[i] > arr[i+1]), swap them
  4. Move to the next pair and repeat
  5. After each pass, the largest unsorted element "bubbles up" to its correct position
  6. Repeat until no more swaps are needed
Pseudocode
for i = 0 to n-1:
    for j = 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])
Complexity Analysis
Time Complexity
Best:O(n)
Average:O(n²)
Worst:O(n²)
Space Complexity
O(1)
Stable Sort?
Yes
Advantages & Disadvantages
Advantages
  • Very simple to understand and implement
  • No extra space required (in-place)
  • Stable sort - preserves order of equal elements
  • Can detect if array is already sorted (optimized version)
Disadvantages
  • Very slow - O(n^2) time complexity
  • Not suitable for large datasets
  • Many unnecessary comparisons and swaps
  • Outperformed by almost all other sorting algorithms
When to Use Bubble Sort
  • •Educational purposes - learning sorting concepts
  • •Very small arrays (< 10 elements)
  • •Nearly sorted data (with early termination optimization)
  • •When simplicity is more important than performance