Bubble Sort Java

Hi guys!! Welcome to flower brackets blog. In this post we will learn bubble sort java.

bubble sort java

What is bubble sort in java?

Bubble sort is a algorithm. This sorting algorithm is considered as simplest sorting algorithm for the fact that each combination of adjacent elements are compared and swapped if they are not in correct order.

Also Read – Insertion sort in java

Here’s the java program for bubble sort,

Example:

public class DemoBubbleSort 
{ 
   void bubbleSort(int arrNum[])
   {
      int num = arrNum.length;
      for(int a = 0; a < num - 1; a++)
      {
         for(int b = 0; b < num - a - 1; b++)
         {
            if(arrNum[b] > arrNum[b + 1])
            { 
               int temp = arrNum[b];
               arrNum[b] = arrNum[b + 1];
               arrNum[b + 1] = temp;
            }
         }
      }
   }

   void printingArray(int printArr[])
   {
      int number = printArr.length;
      for(int a = 0; a < number; ++a)
         System.out.print(printArr[a] + " ");
      System.out.println();
   }

   public static void main(String[] args) 
   { 
      DemoBubbleSort bs = new DemoBubbleSort();
      int arrSort[] = {65, 35, 25, 15, 23, 14, 95};
      bs.bubbleSort(arrSort);
      System.out.println("After sorting array : ");
      bs.printingArray(arrSort);
   }
}

Output:

After sorting array : 14 15 23 25 35 65 95


Now let’s understand what is bubble sort algorithm in java?

For example,

Bubble Sort Java

Let’s say we have a list of integers in the form of an array, named Number. In this array there are six elements. We have indices starting from 0 to 5.

Now to sort above array we need to rearrange the elements in the array in increasing order. To do that we are going to scan the array from left to right multiple times.

It’s like we first look at the 0th element and then look at the 1th element and so on. When scanning the array and when we are at particular position, we will compare the element at that particular position with the adjacent element at the next position.

So, if we at 0th position, we will compare the element at 0th position with the element at 1th position, and if the element at the current position is greater than the element at the next position, we will swap the two elements.

In our case, 20 is not greater than 70, so, we will not swap the two elements. We will move to next position 1. Once again we will compare the element with its next element and if it is greater we will swap the two elements.

In this case 70 is greater than 40, so, we will swap the position of these two elements. So, 70 will move to index 2 and 40 will move to index 1.

Now we will move to index 2, the number at index 2 at this stage will be 70. Again we will look at the next element, it’s 10. 70 is again greater than 10, so we will swap and now, we will move to index 3.

Once again, at this stage the number at index 3 is 70, we will compare it with 50 and we need to swap again. So, 70 will go to index 4 and 50 will move to index 3 and now we will go to index 4.

As you can see, this whole process is pushing number 70, which is the largest in the array towards higher indices at each step.

When we were at position 4, once again 70 is greater than 30, so we will swap. There is no next element for index 5 and at this stage we are done with one pass on the array and what has happened after this one pass is that 70 which is the largest in the array is at its appropriate position.

It deserves to be at index 5 in the sorted array and that’s where it is. So, 70 has kind of bubbled up to the right most position in the array, with this whole logic of swapping the adjacent elements.

Final sorted array will be like this,

Bubble Sort Java

The pseudo code for bubble sort algorithm would be something like this,

for i ← 0 to n - 1
{
   if(number[i] > number[i + 1])
   {
      swap(number[i],number[i + 1])
   }
}

We will run a for loop from 0 to n – 1. Here “n” is the number of elements in an array and if number[i], the element at position “i”, is greater than element at position i + 1, we will swap the two elements.

There is one bug here, if i = n – 1, it will be the last index, so there will be no element after that. So, we will not be able to access number[i + 1], so we will run this loop only till n – 2.

We don’t want to access an index that will be out of the range of the array. For i = n – 1, number[i + 1] would have been out of range.

So this is the state of one pass. What if we perform another pass and once again keep comparing the adjacent elements and performing swaps.

If we will do so, the second largest element in this example will land up at index 4. The second largest in the array is number 50.

So, after 2nd pass our array will be in a state like this.

Bubble Sort Java

With every pass on the array, the array will be divided into two parts, one part will be the sorted part and another part will be unsorted part.

After two passes, the part of the array from index 4 till 5 is sorted and the part of the array from index 0 till 3 is unsorted.

With each pass, the largest element in the unsorted half will bubble up to the highest index in the unsorted half. So, in 3rd pass, number 40 should bubble up to position 3, at index 3.

And while scanning, once we reach to the part where we are sorted, there will be no swapping. We can actually avoid going to the sorted part.

It will only improve our algorithm. After pass 3, our array will be looking like this,

Bubble Sort Java

Infact, we are already sorted. In general, if we will conduct n – 1 such passes, for an array of size n. We can say something like

BubbleSort(number, n)
{
   for k ← 1 to n - 1
   {
      for i ← 0 to n - 2
      {
         if(number[i] > number[i + 1])
         {
            swap(number[i],number[i + 1])
         }
      }
   }
}

So, this is our pseudo code for bubble sort algorithm. Given an array and the number of elements in the array, this function bubble sort will sort the elements in the array in increasing order.


Bubble sort time complexity analysis in java

Let’s now try to analyze the time complexity of this algorithm. The running time of this algorithm will be the running time of these statements inside the nested loop.(if block statements)

BubbleSort(number, n)
{
   for k ← 1 to n - 1
   {
      for i ← 0 to n - 2
      {
         if(number[i] > number[i + 1])
         {
            swap(number[i],number[i + 1])
         }
      }
   }
}

Let us assume that these statements will take constant time “c” in the worst case. These statements will execute in constant time.

Now, the first loop will run exactly n – 1 times, and the second loop will also run exactly n – 1 times, so the total time taken as a function of “n” will be,

T(n) = (n – 1) * (n – 1) * c

which will evaluate to

cn² – 2cn + 1

Whenever we have a polynomial expression for time, then we say that the time complexity is big-O of the highest order term in the polynomial.

O(n²)

The highest order term here is n², we just remove the constants. And, we say that this running time will fall into the class big-O of highest order term.

In this case it will be n². Big-O of n² is not the best running time for a sorting algorithm. In fact this running time is bad.

Bubble sort is a slow sorting algorithm, it’s as good as selection sort but both bubble sort and selection sort are slow sorting algorithms.

We can do couple of things in this algorithm to improve the time complexity, at least for some scenarios. The first thing that we can do is, we need not run second loop till n – 2, all the time.

As we discussed earlier, at any stage during the sorting, the array will have some part as sorted and some part as unsorted.

There is no point passing through the sorted part because there will be no swapping in that part. For first pass we can run inner loop till n – 2, for the second pass we can run inner loop till n – 3 and we will be good.

For the third pass, we can only run till n – 4 and so on. So, in general we can run the loop till n – k – 1, so when k is 1, we can run till n – 2, when k is 2, we will run till n – 3 and so on.

This is some improvement, but in this case also, if you calculate the time expression, it will be some polynomial of the form an² + bn + c, so complexity will still be big-O of n².

We can do something else to improve this algorithm further. If you remember the previous example that we had picked up, it was sorted after 3 passes only and 4th and 5th pass was only redundant.

If the list is already sorted, there would be no swaps. So, if we go through a pass without swapping anything, then definitely at that stage the list is already sorted.

So, I will do something like this in this algorithm, I will take a variable and name it flag and set it to 0, before making a pass and once this condition number[i] > number[i + 1] is true for any “i”, then we will have to swap and we will set this flag as 1.

And now, when we will come out of “if” loop after a pass, if flag is 0, then there has been not even one swap, so we do not need to conduct any more passes, so we can break out of this loop, the outer loop and this way we will be able to avoid making redundant passes once the array is sorted.

BubbleSort(number, n)
{
   for k ← 1 to n - 1
   {
      flag ← 0
      for i ← 0 to n - k - 1
      {
         if(number[i] > number[i + 1])
         {
            swap(number[i],number[i + 1])
            flag ← 0
         }
      }
      if(flag == 0)
      break
   }
}

Now, with this modification, if we input an already sorted array, to the function bubble sort then this particular loop will execute only once to figure out that it’s already sorted.

So, the time taken if we were considering this as taking some constant time c, in the worst case, the time taken will be c * (n – 1) only.

So, this will be the best case for our algorithm. Our algorithm will be O(n) in the best case. In the average case, somewhere mid-way, after making let’s say n/2 passes, we will exit the inner loop.

If we deduce the time complexity expression, it will still be like an² + bn + c kind of expression, so in average case also, this will be big-O(n²).

And in worst case, the inner loop will also run n – 1 times, and we will be big-O(n²). Bubble sort is in place and stable algorithm and we just deduced it’s time complexity which is big-O(n²) in the worst case.


Conclusion

That’s it guys. So this is all about java bubble sort example. I hope you have understood the concept.

You can subscribe to my blog flower brackets if you haven’t already.

Do share this post if you like.

Related Posts