So in our previous article, Understanding The Sorting Algorithms we read about different sorting algorithms and how differently they can be categorized. Now let's dive into one of those to understand it's working. 

In this article, we would be looking at how Bubble Sort algorithm works. Bubble sort on its own is one of the simple algorithm if not the simplest. It works by continuously comparing and swapping adjacent or neighboring values until we have a sorted dataset.

So let's say we have 4 elements in our dataset. 

It will start comparing 

1^st element with 2^nd 

2^nd element with 3^rd

3^rd element with 4^th

It will then again start from the 1^st element. On each compare it will check if the left is greater than right and if yes then it will swap the numbers present in the same position.  This process will continue until we have a sorted data set.

After each pass which happens, the largest or the smallest number (based on comparison) would bubble up to the last.

Let's take some proper valid example and see how the sorting process will take place

Input dataset : [10, 4, 1, 2]

Process : 

1st pass for [10, 4, 1, 2]

1^st element with 2^nd  : 10 is compared with 4, since 10 is greater than 4 we would swap the two values

Resulting dataset : [4, 10, 1, 2]

2^nd element with 3^{rd :} Now 10 will be compared with 1, and since the 10 is greater than 1 we would swap those values.

Resulting dataset : [4, 1, 10, 2]

3^rd element with 4^th : Now 10 will be compared with 2, and similarly we would swap those.

Resulting dataset : [4, 1, 2, 10]

So after 1st pass we have our dataset as  [4, 1, 2, 10]

2nd pass for [4, 1, 2, 10]

1^st element with 2^nd  : 4 is compared with 1, since 4 is greater than 1 we would swap the two values

Resulting dataset : [1, 4, 2, 10]

2^nd element with 3^{rd :} Now 4 will be compared with 2, and since 4 is greater than 2 we would swap those values.

Resulting dataset : [1, 2, 4, 10]

3^rd element with 4^th : Now 4 will be compared with 10, now since there is no comparison difference, we would not swap here.

Resulting dataset : [ 1, 2, 4, 10]

Now if we see our dataset has been sorted. So we would stop here, however if that had not been the case we would have to continue in the similar fashion until we have the sorted data.

By analysis, we can see that the maximum passes one needs to have for sorting the data is same as the size of the dataset. Here 4. 

So the algorithm would be,

Step 1 : Starting at the first index, compare the adjacent two elements

Step 2 : If the neighboring element is greater or smaller than the previous as per requirement, swap them.

Step 3 : Continue with the next index i.e. the next element.

Step 4 : Once we complete all the elements, check if the data is sorted.

Step 5 :  If the data is sorted stop or else repeat from Step 1

Let's see how the code for the same would look.

//input arr

int[] dataset = [10, 4, 2, 1]

//loop through the dataset

for(int index:0; index<dataset.length; index++){

  // 1st loop for the no of passes we need

  boolean isValueSwapped=false;

    for(int complementIndex=0; complementIndex<dataset.length-1; complementIndex++){

       // 2nd loop for the comparison to be made

        if(dataset[complementIndex] < dataset[complementIndex+1]){

           //swap the two values

           isValueSwapped = true;

        }

      //If isValueSwapped is false, that would mean we have the dataset sorted.

       if(isValueSwapped==false){

           break;

       }

    }

}

Now if we see, the most iterations that would happen will be square of the dataset size. So if n is the dataset size then the most times an iteration would happen would be equal to n² . So from this example, we can say the worst case complexity for this sorting algorithm would be O(n²). 

So what would be the best time complexity? We can see that the above sorting algorithm would have to traverse or iterate the whole array atleast once even if we have provided a full sorted dataset as input. 
Right??

So, the best case complexity would be just n. The average case would thus be O(n²).

And since we are talking about time complexity, let's talk about space complexity which will be O(1) since we are working directly on the input dataset itself. 

The advantage bubble sort algorithm has is,

1. It's easier to understand and implement

2. It is stable algorithm which means the elements relative order does not change

The disadvantage would be,

Since the worst case or average case complexity of this algorithm is O(n²), this will prove very complex and costly when it comes to processing large amount of data.

Also from usage and real application perspective it is seldom used now because of the long processing it takes. 

However if you want to imagine bubble sort algorithm applied in real life, just think about how in school the teachers used to align the students based on their heights. How they used to go back and forth until the students are sorted as per height!! Makes sense right!!

That's about it from bubble sort algorithm. Next time we will look at another sorting algorithm. Feel free to check those out!! Also if you want to learn different ways to swap data. Have a look at below article.

Swapping The Swap

Powered by Froala Editor