Back to home

- Bubble Sort Algorithm: Steps On How it Works:
- Characteristics of Bubble Sort
- Implementation
- Optimized Bubble Sort Algorithm
- Time & Space Complexity Analysis

Logicmojo - Updated Sept 18, 2021

The Bubble Sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface. Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements in an array when a condition is met. For example, a simple bubble sort function would be to numerically order the elements in an array from least to greatest.

It also referred to as comparison sort, is a simple sorting algorithm that repeatedly goes through the list, compares adjacent elements and swaps them if they are in the wrong order. This is the most simplest algorithm and inefficient at the same time. Yet, it is very much necessary to learn about it as it represents the basic foundations of sorting.

1. In an unsorted array of 5 elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater).

2. Compare the second and third element to check which one is greater, and sort them in ascending order.

3. Compare the third and fourth element to check which one is greater, and sort them in ascending order.

4. Compare the fourth and fifth element to check which one is greater, and sort them in ascending order.

5. Repeat steps 1ā5 until no more swaps are required.

Below is an image of an array, which needs to be sorted. We will use the Bubble Sort Algorithm, to sort this array:

**Algorithm**

bubbleSort(array)

for i <- 1 to indexOfLastUnsortedElement-1

if leftElement > rightElement

swap leftElement and rightElement

end bubbleSort

**Characteristics of Bubble Sort**

1. Large values are always sorted first.

2. It only takes one iteration to detect that a collection is already sorted.

3. The best time complexity for Bubble Sort is O(n). The average and worst time complexity is O(nĀ²).

4. The space complexity for Bubble Sort is O(1), because only single additional memory space is required.

**Implementation in Python**

# Bubble sort in Python def bubbleSort(array): # loop to access each array element for i in range(len(array)): # loop to compare array elements for j in range(0, len(array) - i - 1): # compare two adjacent elements # change > to < to sort in descending order if array[j] > array[j + 1]: # swapping elements if elements # are not in the intended order temp = array[j] array[j] = array[j+1] array[j+1] = temp data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

**Implementation in C++**

// Bubble sort in C++ #include <iostream> using namespace std; // perform bubble sort void bubbleSort(int array[], int size) { // loop to access each array element for (int step = 0; step < size; ++step) { // loop to compare array elements for (int i = 0; i < size - step; ++i) { // compare two adjacent elements // change > to < to sort in descending order if (array[i] > array[i + 1]) { // swapping elements if elements // are not in the intended order int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } } // print array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n"; } int main() { int data[] = {-2, 45, 0, 11, -9}; // find array's length int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:\n"; printArray(data, size); }

**Optimized Bubble Sort Algorithm**

In the above algorithm, all the comparisons are made even if the array is already sorted. This increases the execution time.

To solve this, we can introduce an extra variable swapped. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is set false.

After an iteration, if there is no swapping, the value of swapped will be false. This means elements are already sorted and there is no need to perform further iterations.

This will reduce the execution time and helps to optimize the bubble sort.

bubbleSort(array)

swapped <- false

for i <- 1 to indexOfLastUnsortedElement-1

if leftElement > rightElement

swap leftElement and rightElement

swapped <- true

end bubbleSort

**Implementation in Python**

# Optimized Bubble sort in Python def bubbleSort(array): # loop through each element of array for i in range(len(array)): # keep track of swapping swapped = False # loop to compare array elements for j in range(0, len(array) - i - 1): # compare two adjacent elements # change > to < to sort in descending order if array[j] > array[j + 1]: # swapping occurs if elements # are not in the intended order temp = array[j] array[j] = array[j+1] array[j+1] = temp swapped = True # no swapping means the array is already sorted # so no need for further comparison if not swapped: break data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

**Implementation in C++**

// Optimized bubble sort in C++ #include using namespace std; // perform bubble sort void bubbleSort(int array[], int size) { // loop to access each array element for (int step = 0; step < (size-1); ++step) { // check if swapping occurs int swapped = 0; // loop to compare two elements for (int i = 0; i < (size-step-1); ++i) { // compare two array elements // change > to < to sort in descending order if (array[i] > array[i + 1]) { // swapping occurs if elements // are not in intended order int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; swapped = 1; } } // no swapping means the array is already sorted // so no need of further comparison if (swapped == 0) break; } } // print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { cout << " " << array[i]; } cout << "\n"; } int main() { int data[] = {-2, 45, 0, 11, -9}; // find the array's length int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:\n"; printArray(data, size); }

**Best case scenario:** The best case scenario occurs when the array is already sorted. In this case, no swapping will happen in the first iteration
(The swapped variable will be false). So, when this happens, we break from the loop after the very first iteration. Hence, time complexity in the best
case scenario is O(n) because it has to traverse through all the elements once.

**Worst case and Average case scenario:** In Bubble Sort, n-1 comparisons are done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So, the total number of comparisons will be:

Sum = (n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

Sum = n(n-1)/2

Hence, the time complexity is O(n^{2}).

**Space Complexity of Bubble sort**

The space complexity for the algorithm is O(1), because only a single additional memory space is required i.e. for temporary variable used for swapping.

With this article at Logicmojo, you must have the complete idea of analyzing Bubble Sort algorithm.

**Good Luck & Happy Learning!!**