Bubble Sort


In bubble sorting the smaller elements of the array are brought upward step by step by comparing with other elements of the array and as a result the larger elements of the array go downward. Suppose we have a vertical array then the smaller elements will go upward and the larger elements will do downwards in the array. This basically seems to a phenomenon called bubbling.

Because of this bubbling nature this sorting is called bubble sort. The basic idea behind this is that lighter bubbles (smaller elements) will rise to the top. This sorting is done in ascending order; we can reverse the process to sort the data in descending order.

The steps in bubble sorting can be described as:

  • Exchange the neighboring items or elements of array until the largest item or element of the array reaches to the end of the array.
  • Repeat the above step for the rest of the elements of the array.

In the bubble sorting pair swapping is done instead of searching for the smaller element in the array or inserting elements by shifting other elements in the array. In bubble sorting first we will take the first two elements of the array and will swap the smaller with the larger number. Then swapping is done with the next pair. This process is repeated until the largest number reaches the end of the array and smallest number comes to the start of the array.

Suppose we have an array that has elements 19, 12, 5, and 7. Consider the following figure to understand bubble sorting:

19 5 12 7

 In the above figure we have an array of four elements. First of all the pair 19 and 5 will be compared as 5 is smaller than 19 therefore these elements will be swapped. Now the new array looks like the following:

5 19 12 7

Then we take the next pair that is 19 and 12. These two elements will be compared and as 12 is smaller than 19 these elements will be swapped and the new array will look like the following:

5 12 19 7

Now the next pair is 19 and 7 both elements will be compared and are swapped, the new array will be:

5 12 7 19

In the above array it can be seen that 19 is the largest number or element of the array and it is in its final position now but the array is not sorted yet we have 12 in between the smaller elements of the array. The sorting will again start and we have the pair 5 and 12 as 5 is smaller than 12 therefore, it will not be disturbed. The next pair is 12 and 7. 7 is smaller than 12 therefore, we will swap both these elements. Now new array will look like the following:

5 7 12 19

It can be seen now that the above array is sorted in ascending order by using bubble sorting.


Sorting using bubble sort Algorithm:

The following is the algorithm to sort an array of elements by using bubble sorting:

Algorithm:

int arr [5] = {4, 7, 8, 9, 1};

int x, y, temp;

for (x = 0; x < 5; x + +)

{

for (y = 0; y < 5 – x – 1; y + +)

{

if (arr [y] > arr [y + 1])

{

temp = arr [y];

arr [y] = arr [y + 1];

arr [y + 1] = temp;

}

}

}

In the above algorithm we used nested for loop to perform bubble sorting. In the loop swapping is being done. But the above algorithm is not efficient as when our array is sorted before the five iterations let’s say array is sorted in the second iteration even then the loop will complete its five iterations.

To overcome this problem we are introducing a flag variable whose value will be changed if any swapping is done and if no swapping is done it will mean that the array is already sorted hence our loop will break. In this way no time will be wasted in the execution of for loop. Consider the following algorithm:

Algorithm:

int arr [5] = {4, 7, 2, 9, 1};

int x, y, temp;

for (x = 0; x < 5; x + +)

{

int flag = 0;

for (y = 0; y < 5 – x – 1; y + +)

{

if (arr [y] > arr [y + 1])

{

temp = arr [y];

arr [y] = arr [y + 1];

arr [y + 1] = temp;

flag = 1;

}

}

if (! flag)

{

break;

}

}


Complexity of Analysis of Bubble Sorting:

In the bubble sorting algorithm we have two loops an outer loop and the inner loop. The outer loop of the algorithm is executed n times where n is the n of elements present in the array which is going to be sorted. The inner loop executes n-1 time first then n-2 times and then n-3 times and so on until the array is sorted. The total number of comparisons done by the loop is given by:

1 + 2 + 3 + 4 + …………… + (n – 1)

In other words it can be expressed as:

n (n – 1) / 2

This summation is equal to O (n^2). This is considered as the complexity of the bubble sort algorithm. The algorithm of bubble sort is the most simplest of all other sorting techniques. The space complexity of bubble sorting is O (1). This is because only a single space is enough for the temporary variable which was used at the time of swapping elements of the array.