Bubble Sort

Bubble sort is one of the sorting techniques used to sort the elements.

This is the same process that we have used in our school math to arrange the given numbers in ascending or descending order. One or the other way you must have used this bubble sort.

For example lets consider you have a 100, 50,2000,10,20 rupee notes jumbled. Now knowingly or unknowingly you may have arranged them in high value to low value or in reverse order. This process is called sorting.We are just naming the things that we already known from the beginning.

In this process, if you try to find the higher value note first and then next higher note and so on… it is Bubble sort, or else if you try to find the lowest value note first and then next lower value note and so on… it is Selection sort.

How Bubble Sort works?

Usually Sorting is done in increasing order.

Lets take an array of numbers

Array of elements

Bubble sort compares the adjacent elements and swaps them if they are not in the expected order.

In the first pass, it scans the entire array from index 0 to 6 and at the end of each scan the maximum element is sorted in its place, so in the first scan 80 is sorted as it is the maximum element.

Let n be the size of the array. for the first pass (n-1) comparisons are required and the swaps are in the range(0,n-1).

This is how the first maximum element is sorted (first pass) and same process is done for remaining passes

Comparisions- 5 (n-2); Swaps-2 (0,n-2) {After first pass}

Comparisions- 4 (n-3); Swaps-2 (0,n-3) { After second pass}

Comparisons- 3 (n-4); Swaps-1 (0,n-4) {After third pass}

Comparisons- 2 (n-5); Swaps-0 (0,n-5) {After fourth pass}

Comparisons- 1 (n-6); Swaps-0 (0,n-6) {After fifth pass}

Sorted {After Sixth pass}

After each scan the each element is sorted so the Bubble sort is applied on the remaining elements.

Here in the above example n=7

Therefore, if the size of the array is n,

1. Passes required are n-1
2. Number of comparisons for the entire bubble sort are,

first pass = n-1 comparisons (from above example 6 comparisons)

second pass = n-2 comparisons (5 comparisons)

third pass = n-3 comparisons (4 comparisons)

and final pass= 1 comparison

Total Comparisons=n-1+n-2+n-3+n-4+n-5+n-6+……+1

this is sum of first n-1 Natural numbers

which approximates to n²

In Every case the Total number of Comparisons is n².

3. Total number of swaps are minimum=0, maximum=n² (this can be calculated similar to the calculation of comparisons)

Time Complexity of Bubble sort

Here the Time complexity is calculated based on the number of comparisons and number of swaps

T(Bubble Sort)=Comparisons+Swaps

=n²+[0,n²]

=O(n²) {Every case}

Algorithm

n is the size of the array

Bubble sort algorithm

Improve the Performance with simple trick

In any pass if the number of swaps are 0 then the array is already sorted.Simply maintain a variable to count the swaps in each case and then check for 0 after every pass

Using this the Best Case of the bubble sort becomes O(n)

Points to take away

1. Bubble sort is a simple sorting algorithm
2. After each pass in this algorithm an element is sorted. so one pass of bubble sort can be used to find maximum or minimum element in the array
3. Time complexity of Bubble sort is O(n²) {Every case} and it is because of Total Comparisons
4. Bubble sort is Inplace i.e, sorting is done in the same array (no extra array taken)
5. Bubble sort is Stable Sorting Algorithm i.e, preserves the order of elements with equal value.

Visualization and “audibilization” of the Bubble Sort algorithm.