Nobody likes chaos in their life!!
This is why sorting things is required. Sorting is everywhere, Whether it is real-life or you are writing code.
With that, let’s discuss one of the simplest sorting algorithms to sort the given list or array. You guessed it right! We are going to discuss bubble sort in this post.
The bubble sort algorithm is the most basic sorting algorithm. This comparison-based algorithm compares the element to its adjacent element and swaps the locations if needed.
Do you want to learn how it works? So let’s learn this algorithm in detail.
What Is A Bubble Sort?
It evaluates the position of an element by comparing the element to its adjacent element. In case it analyses that the element is out of order, it will swap the location of the element of the array.
Repeat this traversing process until you sort the complete list. This algorithm considers elements as bubbles present at the top of the list, hence the name.
Sort the whole list by comparing the neighboring elements and the sort them in descending and ascending order.
You will understand the whole process in a better way with an example.
Working Of Bubble Sort
It is okay if you still have confusion about how this algorithm works. Here, let’s consider the following example and understand better how this actually works:
You are given the following array:
14, 33, 27, 35, 10
In the first iteration, initially, compare 14 with 33. These elements are already sorted. So, the locations need not be swapped.
After this, compare 33 with 27. These elements are not sorted. So, the locations will be swapped.
Next, compare 33 with 35. Here, the elements are sorted. So, the locations will not be swapped.
Lastly, compare 35 with 10. Here, the elements are not sorted. So, the locations will be swapped.
So, after the first iteration, the given list will look like this:
14, 27, 33, 10, 35
In the same way, all the elements will be compared again in the second iteration. After the second iteration, the list will look like this:
14, 27, 10, 33, 35
When done, in the third iteration, you will have to sort this list again. After the third iteration, the list will look like this:
14, 10, 27. 33, 35
Lastly, this list will be again sorted. After the last iteration, the list will look like this:
10, 14, 27, 33, 35
The given list was small and was sorted in fewer steps. However, what if the list is way too long? To solve such a problem and learn what can help, you can learn about ninjas training problem.
It will help you brush up on your basics and resolve advanced problems. Ninjas training is defined as a coding problem where you have to perform the largest task out of all the tasks given.
This problem would be of great help in arrays and bubble sort algorithms.
Now you have understood this example, let’s make the concept of bubble sort algorithm more clear to you.
Bubble Sort Algorithm
When you are writing a code, a proper algorithm needs to be followed. So, we have come up with the bubble sort algorithm for you. Check out below:
Start bubblesort(arr)
For the whole array
If arr[i]> arr[i+1]
swap(arr[i], arr[i+1])
End if
End for
Return arr
End buublesort
Benefits Of Bubble Sort
Here are the following benefits of using this sorting algorithm to sort the given list of elements:
- Other than the memory occupied by the given array or list, bubble sort itself requires very less memory.
- Bubble sort is easier to use and implement. You can write it in a few lines of code.
- The best-case time complexity of the bubble sort algorithm is O(n) whereas other algorithms use O(n logn) and O(n2).
Disadvantages Of Bubble Sort
Bubble sort also comes up with some disadvantages. Here are some of the disadvantages of this sorting algorithm that you must know before choosing to sort an array.
- The major disadvantage of using bubble sort is the time it takes to sort an array. For larger data sets, bubble sort is not suitable because it will be very less efficient.
- Other than this, if there are certain turtles in the process, it will take up a lot more time to complete the process.
Bubble Sort Variations
The bubble sort algorithm can be used in different cases and in different ways. Here, are all the variations of bubble sort.
- Sorting can be done from left to right or right to left. This variation is suitable when the given list includes unsorted elements at the end.
- Odd-even sort is a parallel version of the bubble sort which is suitable for message passing systems.
- For right and left passes, you can use the cocktail shaker sorting.
Bubble Sort Time Complexity
Before using any algorithm, it is of utmost importance to understand its time and space complexity. Here we are going to discuss the space and time complexity of this sorting algorithm.
Time Complexity
The bubble sort uses one inner loop and an outer loop. Out of the two loops, the inner loop of the sorting algorithm goes through O(n) comparisons.
Worst-Case Complexity
The worst-case complexity of this algorithm will be O(nxn)= O(nxn) O(n2). This occurs when the outer loop also needs to perform O(n) comparisons.
Average Case Complexity
The average-case complexity of this algorithm is O(n/2 x n)= O(n2). This occurs when it will need O(n) and n/2 passes to sort the elements.
Best-Case Complexity
The best-case complexity of this algorithm is O(n). This is due to the list already being sorted.
Space Complexity:
- It needs a certain amount of extra space including i, size variable, and Flag.
- Therefore, the space complexity of the algorithm is O.(1).
Example Of Bubble Sort Code in Python
// 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) {
// compare two adjacent elements
// 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[] = {-2, 45, 0, 11, -9};
// find array’s length
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout << “Sorted Array in Ascending Order:\n”;
printArray(data, size);
}
Conclusion
In this blog, we’ve tried to include all that one needs to know about the basics of the bubble sort algorithm. Also we have tried to explain the concepts in an extremely simple and easy manner. Sorting elements of a list or an array are one of the fundamental concepts that you must know as a programmer. The bubble sort algorithm is the easiest to understand and write.
This is the basic method to sort elements but at the same time, it is more time-consuming. So, if you are working on larger data sets, then this algorithm is not the one for you.
However, if you are not familiar with coding or you wish to go for competitive exams, try enrolling to any online coding training. The experienced mentors will help you understand the concepts in a way that you will never forget!!
Also Read – What Is Learning Management System?
Add Comment