Home | Projects | Notes > Data Structures & Algorithms > Bubble Sort: T = O(n²) , S = O(1)

Bubble Sort: T = O(n²) , S = O(1)

Bubble Sort

• Bubble Sort is a simple sorting algorithm that:

  • Repeatedly compares adjacent elements in an array

  • Swaps them if they are in the wrong order

  • After each full pass, the largest element "bubbles up" to the end

• Bubble sort has a time complexity of O(n²), making it inefficient for large lists.

• Bubble sort has a space complexity of O(1). It sorts the array in place, that is, It does not create additional copies of the array.

Implementation (C++)

Source (bubble_sort.cpp)

x
1
#include <iostream>
2
#include <vector>
3

4
void bubble_sort(std::vector<int> &arr)
5
{
6
    int n = arr.size();
7
    bool swapped;
8
    
9
    for (int i = 0; i < n - 1; ++i)
10
    {
11
        swapped = false;
12
        
13
        for (int j = 0; j < n - i - 1; ++j)
14
        {
15
            if (arr[j] > arr[j + 1])
16
            {
17
                std::swap(arr[j], arr[j + 1]);
18
                swapped = true;
19
            }
20
        }
21
        
22
        // Optimization: if no swaps were made, the array is already sorted
23
        if (!swapped)
24
        {
25
            break;
26
        }
27
    }
28
}
29

30
int main(int argc, char *argv[])
31
{
32
    std::vector<int> arr = {6, 4, 2, 1, 5, 3};
33

34
    bubble_sort(arr);
35

36
    for (auto &elem : arr)
37
    {
38
        std::cout << elem << " ";
39
    }
40

41
    std::cout << std::endl;
42

43
    return 0;
44
}

1
1
1 2 3 4 5 6

Implementation (C)

Source (bubble_sort.c)

x
1
#include <stdio.h>
2
#include <stdbool.h>
3

4
void bubble_sort(int arr[], const int size)
5
{
6
    int i, j, temp;
7
    bool swapped;
8

9

10
    for (i = 0; i < size - 1; ++i)
11
    {
12
        swapped = false;
13

14
        for (j = 0; j < size - i - 1; ++j)
15
        {
16
            if (arr[j] > arr[j + 1])
17
            {
18
                // Swap
19
                temp = arr[j];
20
                arr[j] = arr[j + 1];
21
                arr[j + 1] = temp;
22

23
                swapped = true;
24
            }
25
        }
26

27
        // Optimization: if no swaps were made, the array is already sorted
28
        if (!swapped)
29
        {
30
            break;
31
        }
32
    }
33
}
34

35
int main(int argc, char *argv[])
36
{
37
    int arr[] = {6, 4, 2, 1, 5, 3};
38
    int size = sizeof(arr) / sizeof(arr[0]);
39
    int i;
40

41
    bubble_sort(arr, size);
42

43
    for (i = 0; i < size; ++i)
44
    {
45
        printf("%d ", arr[i]);
46
    }
47

48
    puts("");
49

50
    return 0;
51
}

1
1
1 2 3 4 5 6