Bubble sort in java

Let’s learn bubble sort in java.

Bubble sort in java

Bubble sort is considered as simplest sorting algorithm for the fact that given array is traversed from first to last element.

And while traversing, current element is compared with adjacent element and if current element is greater than the adjacent element, it is swapped.

Now let’s understand bubble sort in java with explanation.

Bubble sort in java

Here we have an array of integers by name “Number”. In this array there are six elements with index starting from 0 to 5.

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

While scanning above array we will compare each element at particular position with the adjacent element.

Also read – selection sort in java

So, first at 0th index position compare with the element at 1st index position.

If the element at the current position is greater than the element at the next position, swap those two elements.

In our case, 20 is not greater than 70, so, we will not swap those two elements. We will move to next index position 1.

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 greater than 10, so we will swap. Next moving on to index 3.

Also read – insertion sort in java

At this stage number at index 3 is 70. Now compare it with 50. Here 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 number in the array towards higher index position at each step.

At index position 4, once again element 70 is greater than 30, so we will swap.

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 number 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

Here’s the java program for bubble sort.

Java program

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[] arrNum)
   {
      int number = arrNum.length;
      for(int a = 0; a < number; ++a)
      {
         System.out.print(arrNum[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


bubble sort time complexity

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)


Improved bubble sort java

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


bubble sort in java using scanner

Let’s learn java program for bubble sort in ascending order. Here’s bubble sort in java using scanner.

import java.util.Scanner;
public class BubbleSortAscending 
{
   public static void main(String[] args) 
   {
      int number, a, b, temp;
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter number of integers: ");
      number = sc.nextInt();
      int[] arrInput = new int[number];
      System.out.println("Enter " + number + " integers: ");
      for(a = 0; a < number; a++) 
         arrInput[a] = sc.nextInt();
      for(a = 0; a < (number - 1); a++)
      {
         for(b = 0; b < number - a - 1; b++)
         {
            // logic to sort in ascending order
            if(arrInput[b] > arrInput[b + 1]) 
            {
               temp = arrInput[b];
               arrInput[b] = arrInput[b + 1];
               arrInput[b + 1] = temp;
            }
         }
      }
      sc.close();
      System.out.println("Sorted integers: ");
      for(a = 0; a < number; a++) 
         System.out.println(arrInput[a]);
   }
}


Output:

Please enter number of integers: 7
Enter 7 integers: 12 26 15 39 58 48 59
Sorted integers: 12 15 26 39 48 58 59


bubble sort in java descending order

Similarly above bubble sort program can be sorted in descending order.

Here’s the java program for bubble sort in descending order.

import java.util.Scanner;
public class BubbleSortDescending 
{
   public static void main(String[] args) 
   {
      int number, a, b, temp;
      Scanner sc = new Scanner(System.in);
      System.out.println("Please enter number of integers: ");
      number = sc.nextInt();
      int[] arrInput = new int[number];
      System.out.println("Enter " + number + " integers: ");
      for(a = 0; a < number; a++) 
         arrInput[a] = sc.nextInt();
      for(a = 0; a < (number - 1); a++) 
      {
         for(b = 0; b < number - a - 1; b++) 
         {
            // logic to sort in descending order
            if(arrInput[b] < arrInput[b + 1]) 
            {
               temp = arrInput[b];
               arrInput[b] = arrInput[b + 1];
               arrInput[b + 1] = temp;
            }
         }
      }
      sc.close();
      System.out.println("Sorted integers: ");
      for(a = 0; a < number; a++) 
         System.out.println(arrInput[a]);
   }
}


Output:

Please enter number of integers: 7
Enter 7 integers: 12 26 15 39 58 48 59
Sorted integers: 59 58 48 39 26 15 12