Bubble Sorting

In this post, we are going to discuss an important Sorting Algorithm, Bubble Sorting, and program of bubble sort in c/c++.

What is sorting?
Sorting in a way of representing a data set in either ascending or descending order.

Data sets can be an array, linked-list, tree, etc.

Why is sorting required?
In our real life, a sorted dataset makes our life easier. It makes the dataset a lot easier to read.[Learh 0-1 Knapsack problem]

It makes it easier to implement in search algorithms in order to find or retrieve an item from the entire dataset.

Applications of Sorting are Binary Search, Binary Search Tree, Priority Queues, etc.

Technical Definition

Bubble Sort is a technique to sort a data-set. Bubble Sort is also called a Sinking sort.

Why is it called “Bubble Sort” ?

The concept of Bubble Sort or Sinking Sort is something like after each step the heavier or lighter object bubbles on the top of the data-set.

Practically, this Algorithm compares every element with its adjacent elements and swaps it accordingly.

Now let us discuss what actually the Algorithm is and then after we discuss the program of bubble sort in c/c++.

Example

Let us consider an example of an array,

bubble sort algorithm

Let us first observe something,

bubble sort algorithm

If we observe carefully, we are following a pattern in the above representation.

Observing pattern of Bubble sort

Yes you guessed it right, we are comparing two adjacent array elements at a time, and if the first element is greater than the second element, we are simply swapping it.

We are following this pattern until we reach the last index.[Read Greedy algorithms]

Now I want you guys to observe one thing in the above pictorial representation.

What output did we get after following the pattern ?

If we observe carefully, we got the largest element of the array at the last position and it is obvious because we are comparing two adjacent elements at a time from starting index to the last index and at every step, we are pushing the greater element to the right side.

So ultimately after all the iteration, we will obviously get the greatest element of the array on the rightmost index.

Yes, this is the main logic of Bubble Sorting.

We compare two adjacent elements at one go and push the greater element on the right side and ultimately we get the greatest element of the array.

Let us write some code to implement the above Logic.

Raw Code:

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n-1; i++)
      {
            if(arr[i] > arr[i+1]) {
                   swap(arr[i], arr[i+1]);
            }
      }
}

I hope the code is very clear to you all. I represented the same logic which we discussed earlier.

Now tell me one thing, did we get a sorted array after performing the above algorithm?

No, our array is still unsorted but this algorithm guarantees that after performing it, we will always get the greatest element at the end.

bubble sort algorithm

There are 7 elements in the array initially, of which we get the greatest element in one overall iteration from the beginning index to the end index.

Now let us consider, we will again perform the same algorithm on the remaining 6 elements excluding the last element.

What do we expect?


Yes, you guessed it right, at last, we will get our 2nd last element of the array.

Now let me ask you a Question,

Can we get a sorted array, if we perform the same algorithm repeatedly for the rest of the elements?

Yes we will get a sorted array at the end and this is obvious because for each iteration, we will get the greatest element of the remaining elements.

Let us make it simpler by taking the same example,

Now we will perform the same Algorithm again on the above array.

bubble sort

We get the second largest element at 2nd last index after performing the above algorithm for one more time.

NOTE that this time we performed the above algorithm on the remaining six elements excluding the last one.

Similarly, if we perform the algorithm, again and again, we will finally get a sorted array and this is the masterstroke logic of Bubble Sorting.

Now let us see the program of bubble sort in C/C++.

Complete program of bubble sort in C/C++

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n; i++) 
      {
            for(int j = 0; j < n-i-1; j++) {
                   if(arr[i] > arr[i+1]) {
                          swap(arr[i], arr[i+1]);
                   }
            }
      }
}

This is the complete Bubble Sort code and hopes it is clear to you. I have represented the same logic with the help of the code.[Learn about prefix sum]

Analysis of Bubble Sort

The above Algorithm takes two nested loops, so the overall time Complexity of the Algorithm will be O(n^2).

Can we improve this time Complexity..?

Yes, we can improve the complexity, now let us consider that a sorted array is given to us and we have to perform a bubble sort to it.

bubble sort

From the above Algorithm, although we will not perform any swapping still our code will run for (n * n) times which will unnecessarily increase the overall complexity of the code.

So how to improve it..??

NOTE that worst-case complexity will always remain O(n^2), but we can improve best-case complexity.


Optimized Bubble Sort Algorithm

Now we will discuss how can we improve the complexity of the best case.

The idea is that if we don’t perform any swapping at any stage we will simply jump out of the main for a loop because no swapping means our array is already sorted.

Let us understand by the above example,

optimized bubble sort

We didn’t perform any swapping in the above iteration which ensures that our array is already sorted.

This small observation can improve our code.

Now let us see the optimized code, program of bubble sort in C/C++.

Program of optimized bubble sort in C/C++

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n; i++) 
      {
            bool flag = false;
            for(int j = 0; j < n-i-1; j++) {
                   if(arr[i] > arr[i+1]) {
                          swap(arr[i], arr[i+1]);
                          flag = true;
                   }
            }
            if(flag == false) break;
      }
}

We have declared a flag variable that will keep track of whether any swapping is taking place or not. If no swapping took place, it will simply break the loop and come out of it.

Time Complexity: O(n) Best Case
Time Complexity: O(n^2) Average and worst Case

NOTE Bubble Sorting is an in-place and stable Algorithm. In-place means that we don’t need any extra space to perform it and stable means if two equal elements occur, the relative order will be maintained.

Hope Bubble Sort is clear to you, usually, bubble Sort is not used because of its complexity. There are many sorting algorithms that are more efficient than Bubble Sorting and we will discuss all of it later.

That’s all folks..!!! [Wikipedia]

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

Your email address will not be published. Required fields are marked *