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).
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:
#Code by COPYASSIGNMENT.COM
#Implementation of Bubble Sort
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:
//Code By COPYASSIGNMENT.COM
#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 completely run and execute all its operations.
Bubble Sort algorithm has a time complexity of O(n2) for all three cases as explained below.
- 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).
- 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).
- 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:
#Code by COPYASSIGNMENT.COM
#Implementation of Bubble Sort
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) Ouput:
Original Array : [64, 34, 25, 12, 22, 11, 90] Final Sorted array : [11, 12, 22, 25, 34, 64, 90]
Properties
- 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.
- It can also be used to sort the elements in a list data structure e.g., in sorting the elements of a linked list.
- 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.
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends!
Happy Coding!
