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

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

Bubble Sort

• A simple sorting algorithm that repeatedly steps through a list of elements, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated for each pair of adjacent elements until the entire list is sorted.

• Gets its name from the way smaller elements "bubble" to the beginning of the list with each pass.

• 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.

Algorithm

1. Input: An array of elements to be sorted.

2. Loop: Start a loop that will run for the total number of elements in the array.

3. Inner Loop: Within the loop, iterate through the array from the beginning to the second-to-last element.

4. Compare and Swap: For each pair of adjacent elements in the inner loop, compare them. If the elements are in the wrong order (i.e., the current element is greater than the next element), swap them.

5. Repeat: Continue this process for each pair of adjacent elements in the array for each iteration of the outer loop.

6. One Pass Complete: After each pass of the inner loop, the largest (or smallest, depending on the sorting order) element "bubbles up" to the end (or beginning) of the array.

7. Reduce Inner Loop: In the next iteration of the outer loop, you can reduce the range of the inner loop by one, as the largest (or smallest) element is already in its correct position.

8. Repeat Outer Loop: Repeat steps 3 to 7 for the remaining unsorted portion of the array until the entire array is sorted.

Pseudo-code

xxxxxxxxxx
6
1
BubbleSort(arr):
2
    n = length(arr)
3
    for i from 0 to n-1:
4
        for j from 0 to n-i-2:
5
            if arr[j] > arr[j+1]:
6
                swap(arr[j], arr[j+1])

Code

xxxxxxxxxx
35
1
#include <iostream>
2

3
using namespace std;
4

5
void bubbleSort(int arr[], int size)
6
{
7
    for (int i = 0; i < size; i++)
8
    {
9
        for (int j = 0; j < size - i - 1; j++)
10
        {
11
            if (arr[j] > arr[j + 1])
12
            {
13
                // Swap
14
                int temp = arr[j];
15
                arr[j] = arr[j + 1];
16
                arr[j + 1] = temp;
17
            }
18
        }
19
    }
20
}
21

22
int main(void)
23
{
24
    int arr[] = {6, 4, 2, 1, 5, 3};
25
    int size = sizeof(arr) / sizeof(arr[0]);
26
    
27
    bubbleSort(arr, size);
28
    
29
    for (auto val : arr)
30
        cout << val << " ";
31
    
32
    cout << endl;
33
    
34
    return 0;
35
}

xxxxxxxxxx
1
1
1 2 3 4 5 6