The bubble sort algorithm is a reliable sorting algorithm. This algorithm has a worst-case time complexity of O(n2). The bubble sort has a space complexity of O(1). The number of swaps in bubble sort equals the number of inversion pairs in the given array. When the array elements are few and the array is nearly sorted, bubble sort is effective and efficient.
What Is a Bubble Sort Algorithm?
Bubble sort algorithm, also known as sinking sort, is the simplest sorting algorithm that runs through the list repeatedly, compares adjacent elements, and swaps them if they are out of order.
The process of traversing the list is repeated until the list is sorted. The comparison sort algorithm is named after smaller or larger elements "bubble" at the top of the list. The following image depicts the real-time implementation of Bubble Sort.
Bubble sorting is accomplished by recursively comparing adjacent elements and sifting them in ascending or descending order.
You will now look at how the bubble sort algorithm works after you better understand what it is.
How Does the Bubble Sort Algorithm Work?
Let's assume an array.
Assume you’re attempting to arrange the elements in ascending order.
An array contains five elements. That means you must perform four comparisons for the most significant (greatest) element to bubble to the top of the array.
Why do you have four comparisons?
N = The number of elements in an array
N-1 = The number of time comparisons that occur
Therefore: 5 - 1 = 4
First Pass
- Compare the first and second elements, starting with the first index.
- They are swapped if the first element is greater than the second.
- Compare the second and third elements now. If they are not in the correct order, swap them.
- The preceding procedure is repeated until it reaches the final element.
Second Pass
- The process is repeated for the remaining iterations.
- The most significant element among the unsorted elements is placed at the end of each iteration.
Third Pass
The comparison is performed up to the last unsorted element in each iteration.
Fourth Pass
When all of the unsorted elements are placed in their correct positions, the array is sorted.
After understanding how it works, you will now look at the algorithm and pseudocode of the bubble sort algorithm.
Algorithm and Pseudocode for Bubble Sort
Algorithm of the Bubble Sort Algorithm
Assume the array is an n-element array. You also need to assume that the function "switch" the values of the array elements given to it.
|
begin BubbleSortAlgorithm( Array ) For all the elements of the array if array[i] > array [i + 1] switch ( array[i] , array[i+!]) end if end for return array end BubbleSortAlgorithm |
Pseudocode of the Bubble Sort Algorithm
|
Procedure bubblesortalgorithm ( array: array of items ) size = array.count; for i = 0 to size -1 do: switch = false for j = 0 to size - 1 do: if array[j] > array{j + 1} then switch ( array [j] >array[j + 1] ) switch = true end if end for If ( not switch ), then Break end if end for end procedure bubblesortalgorithm return array |
Continuing with this tutorial, you will learn how to optimize it.
Optimizing Bubble Sort Algorithm
If you can determine that the array is sorted, you should halt further passes. It is an improvement on the original bubble sort algorithm.
If there is no swapping in a particular pass, the array has become sorted, and you should skip the remaining passes. For this, you can use a flag variable that is set to true before each pass and is set to false when swapping occurs.
|
void bubbleSortAlgorithm(int *array, int ele) // ele is the number of elements in an array { for(int i=0; i<ele; i++) { flag = false; for(int j=0; j<ele-i-1; j++) { if(array1[j]>array1[j+1]) { flag = true; int x = array1[j+1]; array1[j+1] = array1[j]; array1[j] = x; } } // Swapping is not required as array is already sorted if(!flag){ return; } } } |
Following the optimization part, you will look at some variations of the bubble sort.
Variations of Bubble Sort Algorithm
The following are some variations of the bubble sort:
- For message passing systems, odd-even sort is a parallel version of bubble sort.
- Passes can be made from right to left as well as left to right. This is more efficient for lists that include unsorted items at the end.
- Cocktail shaker sorting alternates between left and right passes.
After looking at variations of the bubble sort, you will now look at the complexity of the bubble sort algorithm.
The Complexity of the Bubble Sort Algorithm
The Time Complexity of the Bubble Sort Algorithm
- Bubble sort employs two loops: an inner loop and an outer loop.
- The inner loop performs O(n) comparisons deterministically.
Worst Case
- In the worst-case scenario, the outer loop runs O(n) times.
- As a result, the worst-case time complexity of bubble sort is O(n x n) = O(n x n) (n2).
Best Case
- In the best-case scenario, the array is already sorted, but just in case, bubble sort performs O(n) comparisons.
- As a result, the time complexity of bubble sort in the best-case scenario is O(n).
Average Case
- Bubble sort may require (n/2) passes and O(n) comparisons for each pass in the average case.
- As a result, the average case time complexity of bubble sort is O(n/2 x n) = O(n/2 x n) = O(n/2 x n) = O(n/2 x n) = O (n2).
The Space Complexity of the Bubble Sort Algorithm
- Bubble sort requires only a fixed amount of extra space for the flag, i, and size variables.
- As a result, the space complexity of bubble sort is O. (1).
- It is an in-place sorting algorithm, which modifies the original array's elements to sort the given array.
In this tutorial, you will see some of the benefits and drawbacks of the bubble sort.
Advantages of Bubble Sort Algorithm
- Besides the memory that the array or list occupies, the bubble sort requires very little memory.
- The bubble sort is made up of only a few lines of code.
- With a best-case running time complexity of O(n), the bubble sort is helpful in determining whether or not a list is sorted. Other sorting methods frequently cycle through their entire sorting sequence, taking O(n2) or O(n log n) time to complete.
- The same is true for data sets with only a few items that must be swapped a few times.
Now, you will learn some of the drawbacks.
Disadvantages of Bubble Sort Algorithm
- The main disadvantage is the amount of time it takes. It is highly inefficient for large data sets, with a running time of O(n2).
- Furthermore, the presence of turtles can significantly slow the sort.
This tutorial will conclude with a code implementation of the bubble sort.
Code Implementation of Bubble Sort Algorithm
|
#include<stdio.h> void BucketSortAlgo(int arr[], int num) { int i, j; int array1[num]; for (i=0; i < num; i++) { array1[i] = 0; } for (i=0; i < num; i++) { (array1[arr[i]])++; } for (i=0,j=0; i < num; i++) { for (; array1[i]>0;(array1[i])--) { arr[j++] = i; } } } int main() { int array[100]; int num; int i; printf("Enter the number of elements : "); scanf("%d",&num); printf("Enter the %d elements to be sorted:\n",num); for (i = 0; i < num; i++ ) { scanf("%d",&array[i]); } printf("\nThe array before sorting : \n"); for (i = 0;i < num;i++) { printf("%d ", array[i]); } printf("\nThe array after sorting : \n"); BucketSortAlgo(array, num); for (i = 0;i < num;i++) { printf("%d ", array[i]); } printf("\n"); return 0; } |
Output
Ranked No.1 Best Coding Bootcamp, our Post Graduate Program in Full Stack Web Development, can help you accelerate your career as a software developer. Enroll today!
Next Steps
In this tutorial, you learned everything there is to know about the bubble sort algorithm, including how to implement it and how to use it.
The next topic will be the Binary Search Algorithm, and you will look at how to implement it. If you want to learn more about data structures and programming languages, enrol in Simplilearn’s Post Graduate Program in Full Stack Web Development in collaboration with Caltech CTME. This is a comprehensive program designed to get you the right skills needed to be a successful Full Stack Developer today.
Please leave any questions about the "Bubble Sort Algorithm" tutorial in the comments section below. We will gladly help you resolve your issues as soon as possible.
