BUBBLE SORT
Introduction
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. In every iteration, the largest element bubbles up towards the end and hence the name bubble sort.
This algorithm falls under Brute Force Technique which is a straight forward approach to solve a problem. Let's look at the working of this algorithm.
Working Procedure
Do refer the code available the end of this section to understand the following theory.
- Consider an array of n elements.
- Loop the array from i = 0 to n-2(Outer loop).
- Loop the array from j = 0 to n-i-1(Inner loop).
- If a[j] > a[j+1] then swap these two elements.(It means that in every iteration, if the current element is greater than the next element then we swap them. So the greatest element in the array gets bubbled towards the end.)
- After both the loop ends, we get the required sorted array.
Time Complexity
PS: We give random inputs because the no. of input will generally be 100 or 1000 to find the time complexity and manually giving so many inputs is cumbersome work.
The basic operation in this algorithm is the comparision between current element and the next element(step 4 in the above working procedure). So increment the count variable above this if condition to get the count of no. of times the basic operation has been performed.
Time Complexity: O(n2)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for BUBBLE SORTThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!