Bubble Sort Algorithm in C / C++ with Program Examples
Table of Contents
Bubble Sort Algorithm:
Bubble Sort Algorithm- In this tutorial, you will learn how bubble sort works. Also, you will find the working example of bubble sort in C/C++.
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list.
This simple algorithm performs poorly in real-world use and is used primarily as an educational tool. More efficient algorithms such as timsort, or merge sort are used by the sorting libraries built into popular programming languages such as Python and Java
Amazon Purchase Links:
*Please Note: These are affiliate links. I may make a commission if you buy the components through these links. I would appreciate your support in this way!
What is a Bubble Sort?
The bubbles 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, then the other, than the two elements are exchanged. Through the exchange of elements, the larger value slowly floats or bubbles up to the top.
Bubble sort method is a slow process. It is used for sorting only 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 sorting of data in an array in ascending order using Bubbles Sort method.
In first bubble sort iteration, the value of 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 till 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 bubble sort 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 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: [4 3 2 1]
To sort this array in ascending order three (n-1) iterations will be required these are:
Bubble sort first Iteration:
In first iteration the value of element data[0] is compared with element data[1]. Since 3 is less than 4. there will be 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 moves to the last position in the array.
Bubble sort second Iteration:
In 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 third iteration bubbles sort 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 bubbles sort works.
Example:
write a program which sort the data in ascending order using bubble sort algorithm in C++
#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; }
Implementation:
Pseudocode implementation
In pseudocode the algorithm can be expressed as (0-based array):
procedure bubbleSort(A : list of sortable items) n := length(A) repeat swapped = false for i := 1 to n - 1 inclusive do /* if this pair is out of order */ if A[i - 1] > A[i] then /* swap them and remember something changed */ swap(A[i - 1], A[i]) swapped := true end if end for until not swapped end procedure
Optimizing Bubble Sort:
The bubbles sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time:
procedure bubbleSort(A : list of sortable items) n := length(A) repeat swapped := false for i := 1 to n - 1 inclusive do if A[i - 1] > A[i] then swap(A[i - 1], A[i]) swapped = true end if end for n := n - 1 until not swapped end procedure
More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. This allows to skip over many elements, resulting in about a worst case 50% improvement in comparison count (though no improvement in swap counts), and adds very little complexity because the new code subsumes the “swapped” variable:
To accomplish this in pseudocode, the following can be written:
procedure bubbleSort(A : list of sortable items) n := length(A) repeat newn := 0 for i := 1 to n - 1 inclusive do if A[i - 1] > A[i] then swap(A[i - 1], A[i]) newn := i end if end for n := newn until n ≤ 1 end procedure
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.