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
| Why Learn to Code? How Learn to Code? | How to Install Specific Version of NPM Package? | Types of Inheritance in C++ What Should You Know? |
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.
Why is sorting necessary?
Sorting is a method of arranging the items in a set in a specific order. In other words, it arranges a vast number of elements in a certain order, such as alphabetical, highest-to-lowest value, or shortest-to-longest distance. The input is sorted in the output. In computer science, sorting is one of the most significant categories of the algorithm, and a lot of studies have gone into it. It is frequently used for database algorithms and search operations since it is easier and faster to identify things in a sorted list. In software, sorting can be used to sort an array for subsequent searching or output to an ordered file or report.
Why is Bubble sort preferred in sorting algorithms?
One of the most basic types of sorting in programming is the bubble sort. Bubble sort algorithms run through a group of data (usually numbers) and restructure them one by one into ascending or descending order. Bubble sort gets its name from how smaller and bigger pieces bubble to the head of a dataset. For the opposite reason, bubble sort is also known as sinking sort since certain data pieces sink to the bottom of the dataset. The simplicity of bubble sort is one of its strongest features. It has only a few lines of code, is simple to understand, and can be used anywhere in your software. For bigger collections of numbers, however, it is exceedingly wasteful and should be avoided.
What are the uses of C programming?
C programming is used in a variety of sectors and can be utilized in numerous ways since it has built-in functions and operators that can be used to address a variety of complicated issues. C is a language that combines the features of both low-level and high-level languages. It's utilized in embedded systems and for the creation of system applications. It's also used in the creation of desktop apps and the vast majority of Adobe products. C is a programming language that is used to create browsers and their extensions. It's also used in the creation of databases, such as MySQL and operating systems. It's used to make compilers and in the Internet of Things applications.
![JSP Interview Questions and Answers For Beginners [2024]](https://prod-eks-app-alb-1037681640.ap-south-1.elb.amazonaws.com/blog/wp-content/uploads/2020/09/1105-300x170.png)
