Bubble Sort in Data Structures

Bubble Sort in Data Structures

06 Jun 2024
Intermediate
7.76K Views
24 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course with Certificate

Algorithm for Bubble Sort: An Overview

Bubble Sort is the easiest and the fundamental sorting algorithm in data structures. It works by repeatedly swapping the adjacent elements if they are in the wrong order. In this DSA tutorial, we will understand the Bubble Sort algorithm, implementation, complexity, etc.

To further enhance your understanding and application of bubble sort, consider enrolling in the best Data Structures and Algorithms Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Bubble Sort in Data Structures?

In this sorting method, the algorithm repeatedly compares the adjacent elements, from left to right, and swaps them if they are out-of-order. We start by comparing the first two elements of an array and swapping them if necessary so that the smaller one comes before the larger one. We then move on to compare the next two elements and perform the same swap if needed. This process continues until the array ends.

Bubble Sort in Data Structures

More On Sorting Algo: 1. Selection Sort in Data Structures 2. Insertion Sort in Data Structures 3. Merge Sort in Data Structures 4. Quick Sort in Data Structures 5. Counting Sort in Data Structures

Bubble Sort Algorithm

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Working of Bubble Sort Algorithm

Let's suppose we have to sort the elements in ascending order.
  1. First Iteration (Compare and Swap)
    1. Starting from the first index, compare the first and the second elements.
    2. If the first element is greater than the second element, they are swapped.
    3. Now, compare the second and the third elements. Swap them if they are not in order.
    4. The above process goes on until the last element.
    5. Compare the Adjacent Elements

  2. Remaining Iteration

    The same process goes on for the remaining iterations. After each iteration, the largest element among the unsorted elements is placed at the end.

    Put the largest element at the end

    In each iteration, the comparison takes place up to the last unsorted element.

    Compare the adjacent elements

    The array is sorted when all the unsorted elements are placed at their correct positions.

    The array is sorted if all elements are kept in the right order

Read More - Data Structure Interview Questions for Experienced

Implementation of Bubble Sort in Different Languages in Data Structures(Python, Java & C++)


# 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 they are not in the intended order
                temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp

def print_list(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
    
arr = [-79, 46, 0, 28, -122]

# Print the original array
print('Original Array:', end=" ")
print_list(arr)

bubbleSort(arr)

# Print the sorted array in ascending order
print('Sorted Array in Ascending Order:', end=" ")
print_list(arr)

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Swapping elements if they are not in the intended order
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {-79, 46, 0, 28, -122};

        // Print the original array
        System.out.print("Original Array: ");
        printArray(arr);

        // Perform Bubble Sort
        bubbleSort(arr);

        // Print the sorted array in ascending order
        System.out.print("Sorted Array in Ascending Order: ");
        printArray(arr);
    }
}
 

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Swapping elements if they are not in the intended order
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {-79, 46, 0, 28, -122};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Print the original array
    cout << "Original Array: ";
    printArray(arr, size);

    // Perform Bubble Sort
    bubbleSort(arr, size);

    // Print the sorted array in ascending order
    cout << "Sorted Array in Ascending Order: ";
    printArray(arr, size);

    return 0;
}

Output

Original Array: -122 46 0 28 -79 
Sorted Array in Ascending Order: -122 -79 0 28 46 

How to Optimize Bubble Sort in Data Structures?

In the above algorithm, all the comparisons are made even if the array is already sorted. This increases the execution time. To overcome this problem, we will introduce an extra variable "swapped". The value of "swapped" is set to true if there occurs a swapping of elements. Otherwise, it is set to 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.

Optimized Bubble Sort Algorithm

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

Implementation of Optimized Bubble Sort in Different Languages in Data Structures



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
def print_list(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
    
arr = [-79, 46, 0, 28, -122]

# Print the original array
print('Original Array:', end=" ")
print_list(arr)

bubbleSort(arr)

# Print the sorted array in ascending order
print('Sorted Array in Ascending Order:', end=" ")
print_list(arr)

import java.util.Arrays;

public class OptimizedBubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;

        for (int i = 0; i < n; i++) {
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Swapping elements if they are not in the intended order
                    int 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 (!swapped) {
                break;
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {-79, 46, 0, 28, -122};

        // Print the original array
        System.out.print("Original Array: ");
        printArray(arr);

        // Perform Optimized Bubble Sort
        bubbleSort(arr);

        // Print the sorted array in ascending order
        System.out.print("Sorted Array in Ascending Order: ");
        printArray(arr);
    }
}

#include <iostream>
using namespace std;

void bubbleSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        bool swapped = false;

        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Swapping elements if they are not in the intended order
                int 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 (!swapped) {
            break;
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {-79, 46, 0, 28, -122};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Print the original array
    cout << "Original Array: ";
    printArray(arr, size);

    // Perform Optimized Bubble Sort
    bubbleSort(arr, size);

    // Print the sorted array in ascending order
    cout << "Sorted Array in Ascending Order: ";
    printArray(arr, size);

    return 0;
}

Output

Original Array: -79 46 0 28 -122 
Sorted Array in Ascending Order: -122 -79 0 28 46

Complexity Analysis of Bubble Sort Algorithm

  1. Time Complexity
    CaseTime Complexity
    Best O(n)
    AverageO(n^2)
    WorstO(n^2)
  2. Space Complexity: The space complexity of the simple bubble sort algorithm is O(1) due to the fixed number of variables, and we do not need any extra memory space apart from the loop variables and auxiliary variable that includes temp.

    The space complexity of the optimized bubble sort algorithm is O(2). This is because we are using 2 extra variables – temp for swapping, and a flag variable called swapped.

Advantages of Bubble Sort

  1. Bubble sort is easy to understand and implement.
  2. It does not require any additional memory space.
  3. It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort

  1. Bubble sort has a time complexity of O(n^2) which makes it very slow for large data sets.
  2. Bubble sort is a comparison-based sorting algorithm, which means that it requires a comparison operator to determine the relative order of elements in the input data set. It can limit the efficiency of the algorithm in certain cases.
Summary

The use of the bubble sort algorithm in combination with other algorithms is a great way to maximize productivity and efficiency. We saw every aspect of the bubble sort algorithm in data structures. As it's the most basic sorting algorithm, understanding it is highly important. To apply your knowledge of the selection sort algorithm, enroll in our Data Structures Certification.

Similar Sorting Algorithms

FAQs

Q1. How many comparisons does it take to perform a bubble sort on a list of n elements?

A bubble sort will take n-1 comparisons to sort a list of n elements.

Q2. Why Bubble Sort is called “Bubble” Sort?

It is called Bubble Sort because with each iteration, the largest element “bubbles up” to the top of the list.

Q3. What is the worst-case time complexity of a bubble sort algorithm?

The worst-case time complexity of a bubble sort algorithm is O(n^2). This means that, in the worst-case scenario, the algorithm will take n^2 steps to sort a list of n elements.

Q4. In what order should the input data be given to a bubble sort algorithm for it to work correctly?

The data should be given in ascending order.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
ASP.NET Core Certification TrainingNov 08MON, TUE, WED, THU, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
Azure Developer Certification TrainingNov 09SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
.NET Solution Architect Certification TrainingNov 09SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Microservices Certification TrainingNov 09SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Microsoft Azure Cloud Architect with AINov 10SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
ASP.NET Core Certification TrainingNov 10SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Angular Certification TrainingNov 17SAT, SUN
Filling Fast
06:00PM to 08:00PM (IST)
Get Details
Software Architecture and Design TrainingNov 24SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
.NET Solution Architect Certification TrainingNov 24SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor at Scholarhat)

As a software developer with a wealth of experience, he brings a unique combination of technical acumen and a passion for mentorship to my role. With 6 years of experience, he has honed the skills in C/C++, Java, Python, SQL, C#, JavaScript, React, Java Spring etc. and has a proven track record of delivering high-quality, scalable software solutions and core Computer fundamental knowledge DSA, OOPs, CN, OS etc.

As a teacher, his approach revolves around interactive techniques, prioritizing hands-on learning and real-world projects. He explains concepts clearly, offer practical examples, and encourage questions to foster a supportive environment.
Accept cookies & close this