 # Bubble Sort in Data Structures

Amit Kumar Ghosh  21 min read
10 Jun 2023
Intermediate
308 Views

## Bubble Sort

### Introduction

If you're taking a computer science course, or just interested in technology, chances are you've heard of the bubble sort algorithm. Bubble sort is one of the most fundamental algorithms to learn and understand because it's used for so many aspects of computing from sorting data to searching for items in databases. Not only does understanding this algorithm provide insight into modern programming techniques, but it can also give you an edge when solving coding challenges! In this article, we'll go over exactly what bubble sorting is, how it works, and discuss some of its advantages and disadvantages. So whether you're studying computer science or simply curious about tech keep reading to discover more about bubble sort!

## What is the bubble sort algorithm Sorting is one of the fundamental operations in computer science, and there are many algorithms that can help achieve this task. One of them is the bubble sort algorithm. In this sorting method, 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 end of the array is reached. Then, the user repeats the process from the beginning until there are no more elements that need to be swapped. While it may not be the most efficient algorithm for large sets of data, bubble sort working is simple to understand and implement. It’s also an important concept to know for anyone interested in computer science or programming.

## Bubble sort working algorithm

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

``````
# 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):
# 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 = [ -122, 46, 0, 28, -79]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)``````
``````

// Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -122, 46, 0, 28, -79 };
// call method using class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}``````
``````
// 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) {
// 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[] = {-122, 46, 0, 28, -79};
// find array's length
int size = sizeof(data) / sizeof(data);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}``````

#### Output

``` ```Sorted Array in Ascending Order:
[-79, -122, 0, 28, 46]``````

## Bubble sort complexity

Bubble sort is a simple comparison-based sorting algorithm that compares adjacent pairs of elements and swaps them if they are in the wrong order. It repeats this process until the array is sorted. There are two types of complexity in the bubble sort algorithm, which are

The time complexity of bubble sort- Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. The time complexity of bubble sort depends on the number of comparisons and swaps it performs. In the worst case, where the input array is in reverse order, bubble sort makes n*(n-1)/2 comparisons and swaps, where n is the number of elements in the array. Therefore, the time complexity of bubble sort is O(n^2), where "O" stands for Big O notation, which is used to describe the upper bound of the running time of an algorithm. Bubble sort is not an efficient algorithm for large datasets, as its time complexity is quadratic. However, it can be useful for small datasets or for educational purposes, as it is easy to understand and implement

The space complexity of bubble sort- The space complexity of bubble sort is O(1), which means that the algorithm sorts the input array in place, without using any additional memory or data structures other than the input array itself. Bubble sort works by comparing adjacent elements in the array and swapping them if they are in the wrong order. The algorithm continues to iterate through the array until no more swaps are needed, indicating that the array is sorted. Because bubble sort only requires a constant amount of additional memory to store temporary variables used in the swapping process, its space complexity is O(1).

## Optimized Bubble Sort

There are a few Optimized Bubble Sort that can improve its performance, those are

• Optimized Swapping: In the standard implementation of Bubble Sort, adjacent elements are swapped regardless of whether they are in the correct order or not. This means that the algorithm may perform unnecessary swaps. An optimization is to keep track of whether a swap has been made during an iteration. If no swaps were made, then the list is already sorted, and the algorithm can terminate. This optimization can significantly reduce the number of iterations required.
• Early Termination: Bubble Sort iterates over the entire list multiple times, even if the list is already sorted. An optimization is to add a check after each iteration to see if any swaps were made. If no swaps were made, then the list is already sorted, and the algorithm can terminate early.
• Adaptive Bubble Sort: This optimization takes advantage of the fact that the largest element in the list will "bubble" to the end in each pass. After the first iteration, the algorithm only needs to iterate up to the last swapped index, as elements beyond that index are already sorted.
• Combining with other sorting algorithms: Combining Bubble Sort with another algorithm can improve its performance. For example, the cocktail shaker sort is a variation of Bubble Sort that sorts in both directions. This approach reduces the number of iterations required to sort the list.

## 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``````

``````
# 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):
# 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 = [-122, 46, 0, 28, -79]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)``````
``````
// Optimized Bubble sort in Java
import java.util.Arrays;
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = array.length;
// loop to access each array element
for (int i = 0; i < (size-1); i++) {
// check if swapping occurs
boolean swapped = false;
// loop to compare adjacent elements
for (int j = 0; j < (size-i-1); j++) {
// compare two array elements
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// swapping occurs if elements
// 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 main(String args[]) {
int[] data = { -122, 46, 0, 28, -79 };
// call method using the class name
Main.bubbleSort(data);
System.out.println("Sorted Array in Ascending Order:");
System.out.println(Arrays.toString(data));
}
}``````
``````
// Optimized 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-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[] = {-122, 46, 0, 28, -79};
// find the array's length
int size = sizeof(data) / sizeof(data);
bubbleSort(data, size);
cout << "Sorted Array in Ascending Order:\n";
printArray(data, size);
}``````

#### Output

``` ```Sorted Array in Ascending Order:
-122, -79, 0, 28, 46``````
##### Summary

In conclusion, the bubble sort algorithm is an effective tool to help organize data. It is relatively easy to learn and can be adapted for more powerful sorting with greater complexity. With the proper analysis and application, it can quickly produce useful results with the right dataset. The use of the bubble sort algorithm in combination with other algorithms is a great way to maximize productivity and efficiency. For those looking to master one of the fundamental sorting techniques, this should absolutely be something that you take into account as you continue learning computer science concepts. As always, feel free to reach out if you have any questions or suggestions regarding this article.

Similar Articles 