Data Structures & Algorithms: Bubble Sort Algorithm using Python

Bubble Sort is one of the simplest and easiest sorting algorithms in Data Structures. It is a comparison and swapping-based sorting algorithm which is used to arrange the elements of an array (in ascending order).

Data Structures & Algorithms: Bubble Sort Algorithm using Python

For Example –

INPUT Array — 13 12 96 42 21 67

OUTPUT Array — 12 13 21 42 67 96

In this article, we are going to see how we can implement a Bubble Sort Algorithm in Data Structures and Algorithms using the Python programming language. First, we will see the working, then we will move on to the algorithm after that we will see the actual code in Python and C++ language.

Table of Contents:

How does the Bubble Sort Algorithm work?

Stepwise Algorithm

Bubble Sort Algorithm implementation in Python [Complete Code]

Bubble Sort Algorithm implementation in C++ [Complete Code]

Time Complexity

Space Complexity

Is Bubble Sort an in-place sorting algorithm?

Does Bubble Sort show a stable nature?

Is Bubble Sort an adaptive sorting algorithm?

A better version of Bubble sort

Properties

How does the Bubble Sort Algorithm work?

In Bubble Sort Algorithm, the given array is sorted by repeatedly selecting a pair of adjacent elements and comparing their values. If the pair of element is itself sorted i.e., if the first element of the pair is smaller than the second element of the pair then it will remain the same and the pointer will move forward otherwise if the elements are placed incorrectly then a swap operation will be performed between the elements and thus both the elements will be arranged in ascending order.

In every iteration, the same process is repeated until the array gets completely sorted (in ascending order) and all the elements get placed at their correct position.

Algorithm

Step1: Start with the first element present at an index equal to zero and compare the current element with the next element present in the array.

Step2: If the current element is greater than the next element swaps them.

Step3: If the current element is less than the next element, move to the next element. Repeat Step 1.

Bubble Sort Algorithm in Python

Code:

def bubbleSort(arr):

n = len(arr)

#Traversing through all array elements

for i in range(n):

for j in range(0, n-i-1):

#Traversing the array from 0 to n-i-1

#Swap if the element found is greater than the next element

if arr[j] > arr[j+1] :

#Swapping

arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code

arr = [64, 34, 25, 12, 22, 11, 90]

#Printing original array

print("Original Array : ", arr)

#Calling Function

bubbleSort(arr)

#Printing Sorted Array

print ("Final Sorted array : ", arr)

Output:

Original Array :  [64, 34, 25, 12, 22, 11, 90]

Final Sorted array :  [11, 12, 22, 25, 34, 64, 90]

Bubble Sort Algorithm in C++

Code:

#include <iostream>

using namespace std;

//Shifts largest element to end

void bubble_sort(int a[], int n)

{

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n - i; j++)

{

if (a[j + 1] < a[j])

swap(a[j + 1], a[j]);

}

}

}

int main()

{

int n;

cout << "Enter size of array : ";

cin >> n; //Taking size of array

int arr[n];

cout << "Enter " << n << " elements : ";

for (int i = 0; i < n; i++)

{

cin >> arr[i]; //Takig array elements

}

bubble_sort(arr, n); //Calling Function

cout << "Final Array : ";

for (int i = 0; i < n; i++)

cout << arr[i] << " "; //Printing Sorted array

return 0;

}

Output:

Enter size of array : 5

Enter 5 elements : 34 12 65 23 21

Final Array : 12 21 23 34 65

Time complexity of Algorithm

Time Complexity — In an algorithm, the time complexity is defined as the amount of time taken by it to run and execute all its operations completely.

The bubble Sort algorithm has a time complexity of O(n2) for all three cases as explained below.

1. Best Case Complexity — Best case is considered when the given array is itself sorted i.e., elements are arranged in an ascending manner. But, even in that case, all the comparison operations will be performed for each and every element of the array due to which the execution time increases. Thus, its time complexity will remain the same i.e., O(n2) although the number of swaps will be O(1).
2. Average Case Complexity — This is the generalized amount of time taken by the algorithm for all the possible averaged inputs. Inputs, in this case, are likely to occur more frequently. Here, again all the comparison operations will be performed for the elements of the array. Thus, the time complexity will remain the same i.e., O(n2), and the number of swaps will also be of O(n2).
3. Worst Case Complexity — Worst case is considered when the given array is reversely sorted i.e., all the elements in descending order. This is the case where all the swapping operations and all the comparison operations will be performed for all the elements of the array. Thus, time complexity, in this case, will be again O(n2).

Space complexity of Algorithm

Space Complexity — For an algorithm, space complexity is defined as the memory space occupied by it to run and execute all its operations.

In the Bubble Sort Algorithm, all the elements are swapped within the space of a single array, given initially and does not require any extra memory space or array or any other data structure for its execution except one variable temp, which is used to store the element being swapped at a temporary location. Thus, it has a space complexity of O(1).

In-place sorting algorithm?

Yes, it is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. All the swapping operations are done within the space of a single input array given initially.

Stable sorting algorithm?

Yes, it is a stable sorting algorithm because if the given list contains two elements of the same value then the element occurring at first in the input array will also occur first in the output array.

Let us understand this with an example –

Input — 4A 5 3 2 4B 1

Output — 1 2 3 4A 4B 5

Note : Subscripts are added only for the purpose of understanding.

Adaptive sorting algorithm?

Yes, It is an adaptive sorting algorithm because if some of the elements of the array are sorted itself or we can say if the array is almost sorted, then it will take into account the ‘already sorted’ elements and the overall estimations will come down to O(n).

A Better version of Bubble Sort: Modified Bubble sort

There is a better version of bubble sort, known as modified bubble sort which includes a flag in the inner loop. We initialize that flag with false. If a swap is made after an entire iteration of the outer loop then we set the flag to true otherwise keep it as it is. If the flag remains false then it should be clear that the array is already sorted because no two elements are swapped. In that case, there is no need for sorting and the sort should end. The new best-case order for this algorithm is O(n). Let’s see the code for the modified version in python. It only requires a few changes to the previous code.

Modified Bubble Sort In Python

Code:

def bubbleSort(arr):

n = len(arr)

#Traversing through all array elements

for i in range(n):

flag = False

for j in range(0, n-i-1):

#Traversing the array from 0 to n-i-1

#Swap if the element found is greater than the next element

if arr[j] > arr[j+1] :

#Swapping

arr[j], arr[j+1] = arr[j+1], arr[j]

flag = True

if flag is False:

break;

# Driver code

arr = [64, 34, 25, 12, 22, 11, 90]

#Printing original array

print("Original Array : ", arr)

#Calling Function

bubbleSort(arr)

#Printing Sorted Array

print ("Final Sorted array : ", arr)

Output:

Original Array :  [64, 34, 25, 12, 22, 11, 90]

Final Sorted array :  [11, 12, 22, 25, 34, 64, 90]

Properties

1. It is one of the slowest sorting algorithms and thus occupies memory space for a longer time. Thus, it is not suitable for large data sets.
2. It can also be used to sort the elements in a list data structure e.g., in sorting the elements of a linked list.
3. Since the code length for this sort is quite short as compared to other sorting algorithms, thus it is preferred more in the case of complex programs.

Let’s be friends! Follow me on Twitter and FaceBook and connect with me on LinkedIn. You can visit My website Too . Don’t forget to follow me here on Medium as well for more technophile content.