The algorithm:

In this sorting algorithm we divide adjacent elements into “bubbles” and repeatedly swap them if they are in the wrong order, until there are no more swaps possible.

It starts by comparing the first and the second element. If in the wrong order, it swaps them and then moves onto the second and third element. It repeats this process till the net swaps is zero.

At the beginning of each iteration it initializes the number of swaps to 0. Then with each subsequent swap it adds to the variable. If no swaps occur in that iteration, it remains at 0 and quits the loop, and returns a sorted array.

For example:

Consider the following array:

[7 , 5 , 4 , 8]

We start with swaps = 0 and i = 0.

We compare a[i] and a[i+1] , i.e. , 7 and 5.

We find that 5 < 7 so we swap the elements and add to the swap variable.

Thus swaps = 1 and a = [5 , 7 , 4 , 8]

Then i = 1 and we compare a[i] and a[i+1], i.e., 7 and 4.

We find that 4 < 7, so we swap the two elements and add to the swaps variable.

Thus swaps = 2 and a = [5 , 4 , 7 , 8]

Now, i = 2 so we compare a[i] and a[i+1], i.e., 7 and 8.

They are in the correct order. Thus we don’t change anything

We have now reached the end of the array.

So we check if swaps = 0. However swaps = 2, so we reset i and swaps and begin the process again for the modified array.

We start with swaps = 0 and i = 0.

On comparing a[i] and a[i+1], i.e., 5 and 4, we find that 4 < 5, so we swap the elements and add to the swaps variable.

So swaps = 1 and a = [4 , 5 , 7 , 8]

After passing through the array we find that there are no more elements that are in the wrong order.

But swaps = 1 so we restart the iteration. This time there is nothing to swap so swaps remains 0 and the loop is broken and we are left with a sorted array.

The program:

Following is the program for bubble sort in python:

print("Enter the array that needs to be sorted: ")
a = [int(i) for i in input().split()]
n = len(a)
swaps = 1
while swaps != 0:
   swaps = 0
   for i in range(n):
       if i+1<n :
           if a[i+1] < a[i]:
               swaps+=1
               a[i],a[i+1] = a[i+1],a[i]
print(a)

The output of the above program is:

Time Complexity: O(n2)

Visits: 137

Leave a Reply

Your email address will not be published. Required fields are marked *