Quick Info

Category: Sorting
Time Complexity: O(n²)
Space Complexity: O(1)
Stable: Yes
In-Place: Yes

Bubble Sort

Sorting Easy

Description

Bubble Sort is one of the simplest sorting algorithms that works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed, which means the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list with each iteration.

How It Works

  1. Start with the first element and compare it with the second element
  2. If the first element is greater than the second element, swap them
  3. Move to the next pair of adjacent elements and repeat step 2
  4. Continue this process until the end of the array
  5. Repeat steps 1-4 until no more swaps are needed

Visualization

Click Start to begin visualization

Implementation


def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Flag to optimize if no swapping occurs
        swapped = False
        
        # Last i elements are already in place
        for j in range(0, n - i - 1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # If no swapping occurred, array is already sorted
        if not swapped:
            break
    
    return arr

# Usage example
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    bubble_sort(arr)
    print("Sorted array:", arr)
                      

#include <iostream>
#include <vector>

class BubbleSort {
public:
    static void sort(std::vector<int>& arr) {
        int n = arr.size();
        
        for (int i = 0; i < n; i++) {
            bool swapped = false;
            
            // Last i elements are already in place
            for (int j = 0; j < n - i - 1; j++) {
                // Swap if the element found is greater than the next element
                if (arr[j] > arr[j + 1]) {
                    std::swap(arr[j], arr[j + 1]);
                    swapped = true;
                }
            }
            
            // If no swapping occurred, array is already sorted
            if (!swapped) {
                break;
            }
        }
    }
};

// Usage example
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    BubbleSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}
                      

public class BubbleSort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;
        
        for (int i = 0; i < n; i++)
        {
            bool swapped = false;
            
            // Last i elements are already in place
            for (int j = 0; j < n - i - 1; j++)
            {
                // Swap if the element found is greater than the next element
                if (arr[j] > arr[j + 1])
                {
                    (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
                    swapped = true;
                }
            }
            
            // If no swapping occurred, array is already sorted
            if (!swapped)
            {
                break;
            }
        }
    }
    
    // Usage example
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Complexity Analysis

Case Time Complexity
Best O(n)
Average O(n²)
Worst O(n²)

Advantages and Disadvantages

Advantages

  • Simple to understand and implement
  • Requires no additional memory space
  • Stable sorting algorithm
  • Adaptive - O(n) when nearly sorted

Disadvantages

  • O(n²) complexity makes it inefficient for large lists
  • Not suitable for large datasets
  • Poor performance compared to other sorting algorithms