Bubble Sort Algorithm In C / C++ With Program Example
Introduction:
Bubble Sort- this is a very detail tutorial about the Bubble Sort algorithm in c / c++ and you will also learn how this algorithm works.
So let’s get started!
What is the Bubble Sort :
The bubble sort method is used to arrange values of an array in ascending or in descending order.
To arrange an array in ascending order, two neighboring elements are compared. If one element is larger than the other, the two are exchanged. Through the exchange of elements, the larger value slowly floats or bubbles up to the top.
The bubble sort method is a slow process. It is used for sorting only a small amount of data. This method can be easily programmed.
To sort data in an array of n elements, n-1 iterations are required. The following explains the sorting of data in an array in ascending order using this method.
In the first iteration, the value of the first element of the array is compared with the second element. The values of the elements are interchanged if the value in the second element is greater than the value in the first element. Similarly, the value in the second element of the array is compared with the third element and these values are interchanged, if necessary. This process is repeated until the last element of the array. Thus at the end of the first bubble sort iteration, the largest value moves to the last position in the array. In the second bubble sort iteration, the above process is repeated. The values are compared up to the n-l element of the array. In this iteration, the second-largest value moves to the second last position in the array. This process is repeated n-1 times in an array of n elements. At the end of the n-1 iterations, the data is arranged in ascending order. To understand the bubble sort, a numerical example is given below. Suppose the name of the array is data and it has four elements with the following values:
To sort this array in ascending order three(n-1) iterations will be required these are:
Iterations:
bubble sort first Iteration:
In the first iteration, the value of element data[0] is compared with element data[1]. Since 3 is less than 4. there will be the change in the list i.e. elements are interchanged. The value of element data[1] is compared with element data[2]. Since 4 is greater than 2, the values are interchanged. The value of element data[2] is compared with element data[3]. Since 4 is greater than 1, the values are interchanged. Thus at the end of the first iteration, the largest values move to the last position in the array.
bubble sort Second Iteration:
In the second iteration, the value of element data[0] is compared with element data[1]. Since 3 is greater than 2, the values are interchanged. The value of second element data[1] is compared with third element data[2]. Since 3 is greater than 1, the values are interchanged. At the end of the second iteration, the second-largest value moves to the second last position in the array.
bubble sort third Iteration:
In the third iteration, the value of element data[0] is compared with element data[1]. Since 2 is greater than 1. the values are interchanged. At the end of the third iteration, the third-largest value moves to the third last position in the array In this way a bubble sorting works.
Example write a program which sorts the data in ascending order using bubble sort algorithm in c++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<iostream.h> #include<conio.h> main() { int i,u,t, data[4]={4,3,2,1}; clrscr(); for(u=3; u>=1; u--) for(i=0; i<u; i++) if(data[i] > data[i+1]) { t=data[i]; data[i]=data[i+1]; data[i+1]=t; } cout<<”data is sorted ”<<endl; for(i=0; i<3; i++) cout<<data[i]<<endl; } |
Bubble Sort Conclusion:
The main advantage of Bubbles Sort is the simplicity of the algorithm. In bubble sort, with every pass, the largest element bubbles up to the end of the list if the array is sorted in ascending order.
Similarly for the list to be sorted in descending order, the smallest element will be in its proper place at the end of every pass.
Being the simplest and easy to implement sorting technique, bubbles sort is usually taken for introducing sorting to the audience. Secondly, bubble sort is also used in application like computer graphics wherein filling of polygon edges, etc. require bubbles sort to sort the vertices lining the polygon.
In our upcoming tutorial, we will learn about the Selection Sort in detail.
