Bubble Sort

The third sorting algorithm is bubble sort. The basic idea of this algorithm is that we bring the smaller elements upward in the array step by step and as a result, the larger elements go downward. If we think about array as a vertical one, we do bubble sort. The smaller elements come upward and the larger elements go downward in the array. Thus it seems a bubbling phenomenon. Due to this bubbling nature, this is called the bubble sort. Thus the basic idea is that the lighter bubbles (smaller numbers) rise to the top. This is for the sorting in ascending order. We can do this in the reverse order for the descending order.

The steps in the bubble sort can be described as below

• Exchange neighboring items until the largest item reaches the end of the array

• Repeat the above step for the rest of the array

In this sort algorithm, we do not search the array for the smallest number like in the other two algorithms. Also we do not insert the element by shifting the other elements. In this algorithm, we do pair-wise swapping. We will take first the elements and swap the smaller with the larger number. Then we do the swap between the next pair. By repeating this process, the larger number will be going to the end of the array and smaller elements come to the start of the array.

Let’s try to understand this phenomenon with the help of figures how bubble sort works. Consider the same previous array that has elements 19, 12, 5 and 7.

First of all, we compare the first pair i.e. 19 and 5. As 5 is less than 19, we swap these elements. Now 5 is at its place and we take the next pair. This pair is 19, 12 and not 12, 7. In this pair 12 is less than 19, we swap 12 and 19. After this, the next pair is 19, 7. Here 7 is less than 19 so we swap it. Now 7 is at its place as compared to 19 but it is not at its final position. The element 19 is at its final position. Now we repeat the pair wise swapping on the array from index 0 to 2 as the value at index 3 is at its position. So we compare 5 and 12. As 5 is less than 12 so it is at its place (that is before 12) and we need not to swap them. Now we take the next pair that is 12 and 7. In this pair, 7 is less than 12 so we swap these elements. Now 7 is at its position with respect to the pair 12 and 7. Thus we have sorted the array up to index 2 as 12 is now at its final position. The element 19 is already at its final position. Note that here in the bubble sort, we are not using additional storage (array). Rather, we are replacing the elements in the same array. Thus bubble sort is also an in place algorithm. Now as index 2 and 3 have their final values, we do the swap process up to the index 1. Here, the first pair is 5 and 7 and in this pair, we need no swapping as 5 is less than 7 and is at its position (i.e. before 7). Thus 7 is also at its final position and the array is sorted.

Following is the code of bubble sort algorithm in C++.

void bubbleSort(int *arr, int N) { int i, temp, bound = N-1; int swapped = 1; while (swapped > 0 ) { swapped = 0; for(i=0; i < bound; i++) if ( arr[i] > arr[i+1] ) { temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; swapped = i; } bound = swapped; } }

In line with the previous two sort methods, the bubbleSort method also takes an array and size of the array as arguments. There is i, temp, bound and swapped variables declared in the function. We initialize the variable bound with N–1. This N-1 is our upper limit for the swapping process. The outer loop that is the while loop executes as long as swapping is being done. In the loop, we initialize the swapped variable with zero. When it is not changed in the for loop, it means that the array is now in sorted form and we exit the loop. The inner for loop executes from zero to bound-1. In this loop, the if statement compares the value at index i and i+1. If I (element on left side in the array) is greater than the element at i+1 (element on right side in the array) then we swap these elements. We assign the value of i to the swapped variable that being greater than zero indicates that swapping has been done. Then after the for loop, we put the value of swapped variable in the bound to know that up to this index, swapping has taken place. After the for loop, if the value of swapped is not zero, the while loop will continue execution. Thus the while loop will continue till the time, the swapping is taking place.

Now let’s see the time complexity of bubble sort algorithm.

Bubble Sort Analysis

In this algorithm, we see that there is an outer loop and an inner loop in the code. The outer loop executes N times, as it has to pass through the whole array. Then the inner loop executes for N times at first, then for N-1 and for N-2 times. Thus its range decreases with each of the iteration of the outer loop. In the first iteration, we do the swapping up to N elements. And as a result the largest elements come at the last position. The next iteration passes through the N-1 elements. Thus the part of the array in which swapping is being done decreases after iteration. At the end, there remains only one element where no swapping is required. Now if we sum up these iterations i.e. 1 + 2 + 3 + ……… + N-1 + N. Then this summation becomes N (1 + N) / 2 = O (N²). Thus in this equation, the term N² dominates as the value of N increases. It becomes ignorable as compared to N^2. Thus when the value of N increases, the time complexity of this algorithm increases proportional to N².

Technorati Tags: bubble sort,bubble sort algorithm,bubble sort algo,data structure and algorithm tutorial,ds tutotrial