The Bubble Sort Algorithm

Written by Raza on. Posted in C++

Two weeks ago, I explained to you a basic and easy sorting algorithm which was Selection Sort. Moving onwards, there is yet another basic algorithm by the name of Bubble Sort. It is known as Bubble sort because it brings the small values on the top of the list just like the light bubbles in water tend to come to the surface. Let us see how it works in depth.

Bubble sort works by comparing the values in the List. In one complete round, each value in the list is compared with the next value. If the next value is less than that value, they get swapped. One complete round is known as a Pass. One complete Pass is repeated till the size of the List.

Suppose we have an Array of integers as our list to be sorted. We run through the array and start comparing values from the first index. In the first turn, first and second elements are compared. Then second and third elements are compared, third and fourth elements are compared and so on and so forth. When we reach the last index, can we compare it with another element? No. So we have to run through the Array one less than its total size in one complete Pass. After one pass, we move on to the second Pass.

In this case, we have the following Array.

(7, 8, 1, 2, 5, 4)

Let us apply bubble sort and observe its condition in each pass. Size of the Array is 6 so total passes would be 6 as well. The two elements to be compared in each step are shown in bold letters.

First Pass:

(7, 8, 1, 2, 5, 4)  —>   (7, 8, 1, 2, 5, 4)  —>   No swap.

(7, 8, 1, 2, 5, 4)  —>   (7, 1, 8, 2, 5, 4)  —>   Swap, as 8 > 1.

(7, 1, 8, 2, 5, 4)  —>   (7, 1, 2, 8, 5, 4)  —>   Swap, as 8 > 2.

(7, 1, 2, 8, 5, 4)  —>   (7, 1, 2, 5, 8, 4)  —>   Swap, as 8 > 5.

(7, 1, 2, 5, 8, 4)  —>   (7, 1, 2, 5, 4, 8)  —>   Swap, as 8 > 4

 

Second Pass:

( 7, 1, 2, 5, 4, 8 )  —>   ( 1, 7, 2, 5, 4, 8 )  —>   Swap, as 7 > 1.

( 1, 7, 2, 5, 4, 8 )  —>   ( 1, 2, 7, 5, 4, 8 )  —>   Swap, as 7 > 2.

( 1, 2, 7, 5, 4, 8 )  —>   ( 1, 2, 5, 7, 4, 8 )  —>   Swap, as 7 > 5.

( 1, 2, 5, 7, 4, 8 )  —>   ( 1, 2, 5, 4, 7, 8 )  —>   Swap, as 7 > 4.

( 1, 2, 5, 4, 7, 8 )  —>   ( 1, 2, 5, 4, 7, 8 )  —>   No swap.

Third Pass:

( 1, 2, 5, 4, 7, 8 )  —>   ( 1, 2, 5, 4, 7, 8 )  —>   No swap.

( 1, 2, 5, 4, 7, 8 )  —>   ( 1, 2, 5, 4, 7, 8 )  —>   No swap.

( 1, 2, 5, 4, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   Swap, as 5 > 4.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

Fourth Pass:

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

Fifth Pass:

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

Sixth Pass:

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, website like this 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

( 1, 2, 4, 5, 7, 8 )  —>   ( 1, 2, 4, 5, 7, 8 )  —>   No swap.

The procedure shown above is quite self-explanatory. Notice that the Array got sorted in the third pass but three empty Passes were carried out uselessly. So Bubble sort allows us to stop the sorting procedure when the Array gets into its proper order. It can also detect if the Array is already sorted or not. So it is better to use than selection sort where no such method exists.

With the procedure at our finger tips, we can very easily write the source code for Bubble Sort. It would be like this.

</p>
<p>void Bubble_Sort (int arr [], int size)</p>
<p>{</p>
<p>&nbsp; &nbsp; bool pass ;</p>
<p>&nbsp; &nbsp; for (int j = 0 ; j < size ; ++j) &nbsp; //Bigger Loop, for Passes</p>
<p>&nbsp; &nbsp; {</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; pass = false ; &nbsp; //checks if even a single swap takes place</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0 ; i < size - 1 ; ++i) &nbsp; //Comparison Loop</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; {</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (arr[i] > arr[i+1])</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pass = true ; &nbsp; //indicates a pass has occurred</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap (arr[i], arr[i+1]) ;</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; }</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; if (!pass) &nbsp; //if no pass has occurred in whole loop,</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; break ; &nbsp; //array is sorted</p>
<p>&nbsp; &nbsp; }</p>
<p>}</p>
<p>&nbsp;</p>
<p>int main (int argc, char *argv [])</p>
<p>{</p>
<p>&nbsp; &nbsp; const int SIZE = 6 ;</p>
<p>&nbsp; &nbsp; int arr [SIZE] = {7, 8, 1, 2, 5, 4} ;</p>
<p>&nbsp; &nbsp; Bubble_Sort (arr, SIZE) ;</p>
<p>}</p>
<p>

Notice that the variable ‘pass’ is checking when the array gets sorted. If the array has already been sorted, the outer loop would run only once and thus system resources would be saved.

I want you to learn two terminologies commonly used in sorting. Two types of elements present difficulties in any sorting procedure. The smaller elements present at the end and larger elements present at the beginning of the List. For the smaller ones at the end have to be brought at the start. They are known as turtles. The larger ones at the beginning have to be brought at the end and are known as rabbits. Generally turtles are more difficult to handle than rabbit.

Finally, bubble sort is not a good sorting technique. For larger lists, it becomes highly inefficient to apply. Bubble sort runs n*n times, i.e. it runs n times the size of the array, making it very time consuming. Also, it is very unlikely being a natural process to be followed; you won’t be sorting a shuffled deck of cards by the bubble sort technique in real life. Thus, this adds up to its inefficiency. Nevertheless, it is used as a sub-process in many other quick and fast sorting algorithms. One of them is Insertion Sort which I would be dealing with the next time.

Till then Good Bye!

Tags: , , ,