Bubble sort in java

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

Bubble sort in java

Bubble sort in java

Bubble sort java 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

Now let’s understand bubble sort algorithm in java. For example,

Bubble sort in java

Let’s say we have a list of integers in the form of an array by name “Number”. In this array there are six elements with index 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.

We first look at the 0th element, 1st element and so on. When scanning the array and at particular position, we will compare the element at that particular position with the adjacent element at the next position.

So, if we are at 0th index position, we will compare the element at 0th index position with the element at 1st index position.

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 index 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 70 is greater than 50 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 index position at each step.

When we were at index position 4, once again element 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.

So, 70 has kind of bubbled up to the right most position in the array. We are done with first pass. Next second pass, third pass and so on… till elements in array are sorted in ascending order.

Here’s the whole logic of swapping the adjacent elements,

First pass

(20) 70 40 10 50 30 - 20>70? no, don't swap
20 (70) 40 10 50 30 - 70>40? yes, swap.
20 40 (70) 10 50 30 - 70>10? yes, swap.
20 40 10 (70) 50 30 - 70>50? yes, swap.
20 40 10 50 (70) 30 - 70>30? yes, swap.
20 40 10 50 30 (70)

Second pass

(20) 40 10 50 30 70 - 20>40? no, don't swap
20 (40) 10 50 30 70 - 40>10? yes, swap
20 10 (40) 50 30 70 - 40>50? no, don't swap
20 10 40 (50) 30 70 - 50>30? yes, swap
20 10 40 30 (50) 70 - 50>70? no, don't swap

Third pass

(20) 10 40 30 50 70 - 20>10? yes, swap
10 (20) 40 30 50 70 - 20>40? no, don't swap
10 20 (40) 30 50 70 - 40>30? yes, swap
10 20 30 (40) 50 70 - 40>50? no, don't swap
10 20 30 40 (50) 70 - 50>70? no, don't swap
10 20 30 40 50 70 -   sorted array

Final sorted array will be like this,

Bubble sort in java


Java program for bubble sort

Here’s the java program for bubble sort,

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 : 10 20 30 40 50 70


Bubble sort time complexity analysis

Best case time : O(n) when array is sorted.

Worst and average time : O(n * n) when array is in reverse order.

Auxiliary space : O(1)


Optimized bubble sort code

public class BubbleSortDemo
{
   static void sort(int arrNum[], int num) 
   { 
      int a, b, temp; 
      boolean swap; 
      for(a = 0; a < num - 1; a++) 
      { 
         swap = false; 
         for(b = 0; b < num - a - 1; b++) 
         { 
            if(arrNum[b] > arrNum[b + 1]) 
            { 
               temp = arrNum[b]; 
               arrNum[b] = arrNum[b + 1]; 
               arrNum[b + 1] = temp; 
               swap = true; 
            } 
         }
         // if two elements are swapped by inner loop, then break 
         if(swap == false) 
            break; 
      } 
   }

   static void displayArray(int num[], int size) 
   {
      for(int a = 0; a < size; a++) 
         System.out.print(num[a] + " "); 
      System.out.println(); 
   }

   public static void main(String[] args) 
   {
      int arrInput[] = {20, 70, 40, 10, 50, 30}; 
      int number = arrInput.length; 
      sort(arrInput, number); 
      System.out.println("Sorted array : "); 
      displayArray(arrInput, number);
   }
}

Output:

Sorted array : 10 20 30 40 50 70

Related Posts