Introduction

The sorting of an array holds a place of immense importance in computer science. Its utility is noticed when there is a need to arrange data in a specific order. There are different kinds of sorting algorithms. The most common and widely used sorting algorithm is the Bubble Sort.

Check out our free courses to get an edge over the competition. 

Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.

Explore our Popular Software Engineering Courses

Bubble Sort in C

The technique that is used for sorting in Bubble sort is simple and easy to understand. All it does is compare the current element with the next element and swap it if it is greater or lesser as dictated by the condition. The algorithm is very accurate. Each time an element is compared with other elements until its place is found, it is called a pass.

This algorithm is comparable to bubbles in water as it filters out the top of the array-like bubbles. Among all the algorithms used for sorting, Bubble sort is the easiest and the slowest with time complexity of O(n^2). However, the algorithm can be optimized through the use of a flag variable that exits the loop when swapping is completed. The best case for Bubble sort can be O(n) when the array is sorted.

Check out upGrad’s Advanced Certification in Blockchain

For example, let us take an unsorted array of five numbers as given below

13, 32,26, 34,9

Bubble sort will begin considering the first two elements, and it will compare them to check which one is greater. In this case, 32 is greater than 13. So this portion is already y sorted. Next, we compare 32 with 26. So we find that 32 is greater than 26, so they must be swapped. The new array will look like

13, 26, 32,34,9

Next, we compare 32 and 34. We know that they are already sorted. Thus we move to the last two variables 34 and 9. Since 34 is greater than 9, they have to be swapped.

We swap the values and come to the end of the array after the first iteration. Now the array will look like

13, 26. 32,9,34

After the second iteration, the array will look like

13, 26, 9,32,34

After the third iteration, the array will become

13,9,26,32,34

After the fourth iteration, the array will be completely sorted

9, 13,26,32,34       

Explore Our Software Development Free Courses

Must Read: Project Ideas in C

The algorithm

Here we are assuming that the array has n elements. Further, we assume that the exchange values function is swapping all the values to make the array numbers in sorted order.

Check out upGrad’s Advanced Certification in Cloud Computing

  start BubbleSort (array)

 for all elements of the list

 if array[i]> array[i+1]

 exchange values(array[i], array[i+1] )

end if

end for

return array

end Bubble Sort

In-Demand Software Development Skills

Read: Sorting in Data Structure: Categories & Types

Pseudocode

It is evident in the above algorithm that there is a comparison between each pair of the array element until the whole array is sorted in ascending order. It may result in a few complexity issues, such as the algorithm’s outcome when the array is already sorted in ascending order. For easing out the issue, we will be using one flag variable, which enables us to see if there has been any swapping. If no more swapping is needed, we will come out of the inner loop.

Read our Popular Articles related to Software Development

The pseudocode for the BubbleSort algorithm can be written as follows

procedure BubbleSort (array: items in the array)

iterate= array.count;  

for k=0 to iterate-1 do:

flag= false

for l=0 to iterate-1 do:

if (array[l]> array[l+1]) then

exchange values(array[l], array [l+1])

flag=true

end if

end for

If (not swapped) then

Break

End if

End for

End procedure return array

Let us try out a sample program of bubble sort in C:

# include<stdio.h>

void main

{

   int array [10], i, j, num

   for (i=0; i<=9; i++)

   {

      scanf(“%d”, &array[i])

   }

     for(i=0;i<=9;i++)

         {

           for(j=0;j<=9-i;j++)

            {

                if(array[j]>array[j+1])

                   {

                       num= array[j];

                        array[j]=array[j+1];

                       array[j+1]=num;

                   }

             }

          }

  printf(“The sorted array is /n”);

  for(i=0;i<=9;i++)

       {

          printf(“%d ”,&array[i])

        }

}

As shown in the sample, this bubble sort algorithm accepts 10 numbers from the user and stores it in the array. In the next part, there are two for loops. The outer loop runs for I value, equalling zero to less than equal to nine. The outer loop’s function is to take care of all the elements of the value that have to be compared with other elements.

There is another loop inside the outer loop. It starts from j=0 and runs until it is lesser than or equal to eight. Inside, there is a conditional if statement which compares and checks if array[j] is greater than array [j+1]. If the condition is satisfied the values of array[j] and array [j+1] are swapped with each other.

A variable by the name of num is used for this purpose. First array[j] is assigned to num, then array[j+1] is assigned to array[j], and finally num is assigned to array[j+1]. This process will continue until all the elements in the array are sorted in increasing order. After that, the sorted array is printed. 

upGrad’s Exclusive Software Development Webinar for you –

SAAS Business – What is So Different?

 

Optimized implementation of Bubble Sort

We have an optimized algorithm for bubble sort for improving the results. The use of a flag variable does the optimization. The flag variable will hold 1 if there is a swapping else it will break out from the loop. Below is the optimized bubble sort program in C.

#include<stdio.h>

void main

{

   int array [10], i, j, num, flag=0;

   for (i=0; i<=9; i++)

   {

      scanf(“%d”, &array[i])

   }

     for(i=0;i<=9;i++)

         {

           for(j=0;j<=9-i;j++)

            {

                if(array[j]>array[j+1])

                   {

                       num= array[j];

                        array[j]=array[j+1];

                       array[j+1]=num;

                        flag=1;

                   }

                 if(! flag)

                  {

                          break;

                  }

             }

          }

  printf(“The sorted array is /n”);

  for(i=0;i<=9;i++)

       {

          printf(“%d ”,&array[i])

        }

}

The given program executes in a way that is similar to the normal bubble sort program. The only change is the use of the flag variable. Initially, the flag is set to 0. However, if a swapping takes place, the flag becomes 1. It implies that the array still requires one more checking. On the other hand, if the flag is not 1, implying that swapping has not taken place, we exit from the inner loop, assuming that the array is already sorted. Once executed, we will get the same result as the normal Bubble sort.

Time Complexity

The best-case time complexity for Bubble sort is O(n). It happens when the array is already sorted. The worst case is O(n*n) when the array has not been sorted.  

Read: Top 12 Pattern Programs in Java You Should Checkout Today

What Next?

If you’re interested to learn more about Java, full-stack software development, check out upGrad & IIIT-B’s PG Diploma in Full-stack Software Development which is designed for working professionals and offers 500+ hours of rigorous training, 9+ projects, and assignments, IIIT-B Alumni status, practical hands-on capstone projects & job assistance with top firms.