Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.

If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on.

If we have total n elements, then we need to repeat this process for n-1 times.

It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.

Implementing Bubble Sort Algorithm

Following are the steps involved in bubble sort(for sorting a given array in ascending order):

  1. Starting with the first element(index = 0), compare the current element with the next element of the array.
  2. If the current element is greater than the next element of the array, swap them.
  3. If the current element is less than the next element, move to the next element. Repeat Step 1.

Let's consider an array with values {5, 1, 6, 2, 4, 3}

 Below, we have a pictorial representation of how bubble sort will sort the given array.

         

So as we can see in the representation above, after the first iteration, 6 is placed at the last index, which is the correct position for it.

Similarly after the second iteration, 5 will be at the second last index, and so on.

Another Example of Bubble Sort

 We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it short and precise.

               

Bubble sort starts with very first two elements, comparing them to check which one is greater.

             

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

           

We find that 27 is smaller than 33 and these two values must be swapped.

           

The new array should look like this −

                 

Next we compare 33 and 35. We find that both are in already sorted positions.

               

Then we move to the next two values, 35 and 10.

               

We know then that 10 is smaller 35. Hence they are not sorted.

           

We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −

       

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this

       

Notice that after each iteration, at least one value moves at the end.

         

And when there's no swap required, bubble sorts learns that an array is completely sorted.

           

Now we should look into some practical aspects of bubble sort.