Bubble Sorting with example in C/C++/Java
Bubble sorting is one of the simplest sorting algorithm that we can use to sort an array or a structure. Though it is so simple to implement in a C program, bubble sort is also considered as an inefficient sorting algorithm. Bubble sort comes handy in cases where the total number of elements to be sorted is so small (may be in the 100′s range). When the data size is large/huge bubble sort is seldom used in practical programming world. Let’s analyse bubble sort algorithm in detail by implementing it as a C program.
Note:- Since the algorithm is implemented with the help of 2 FOR loops only, it can be used as such for any programming languages like C/C++ or Java
The working of Bubble sort:-
Consider an array of 5 elements in the order 5 , 4 , 3 , 2 , 1. We need to sort this list in ascending order using bubble sort. The concept of bubble sort algorithm is simple, we can explain it in 2 steps.
For the simplicity of explanation, I am going to consider sorting in ascending order.
- Step1:- The first member of the list is compared with the next element. To sort in ascending order we usually begin the process by checking if first element is greater than next element. If yes, we interchange their position accordingly. i.e first element is moved to second element’s position and second element is moved to first element’s position. If No, then we dont interchange any elements. As next step, the element in second position is compared with element in third position and the process of interchanging elements is performed if required. The whole process of comparing and interchanging is repeated till last element. When the process gets completed, the largest element in array will get placed in the last position of the list/array.
- Note 1 for Step 1:- Here the point to note is that, we compare two elements in succession i.e we compare 1st and 2nd element – then 2nd and 3rd element – then 3rd and 4th and finally 4th and 5th. So the total number of comparisons is 4 (for an array/list of 5 elements). If there are ‘n’ elements to be sorted, then the total number of comparisons to be made is = n-1
- Step 2:- The whole process in step 1 is repeated 5 times to get the sorted array in order 1 , 2 , 3 , 4 , 5. If there are n elements to be sorted, the whole process of step 1 is repeated ‘n’ times.
Now you can easily find the efficiency of “Bubble Sort” algorithm. If there are ‘n’ elements, it is of the order of n*n. This is simply because it takes nearly n comparisons to be made n times.
Modifying the Bubble sort:-
I recommend you analyse the two steps (step 1 and step 2) and the two images carefully. Now you can observe one fact. The number of comparisons to be made can be reduced by 1 after each pass of the first FOR loop. In the above example to sort in ascending order, the largest number 5 gets to the last position after first pass. It”s a fixed position and we are sure there is no number greater than 5 in this list. Thus we can reduce the number of comparisons to be made in next pass by 1. Similarly after the second pass, the second largest number (4) gets fixed in second last position (just before 5). Thus we can reduce the number of comparison again by 1 in next pass. This modification improves the speed of bubble sort. The modified code snippet is given below.