AppDividend
Latest Code Tutorials

Bubble Sort In Java Example | Java Bubble Sort Program

0

Bubble Sort In Java Example | Java Bubble Sort Program is today’s topic. Bubble sort is the simplest method to sort an array or list of integers. This sorting method is also known as Sinking Sort. Bubble Sort is the most straightforward sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. I have already covered the Sorting In Java like MergeSort, QuickSort, InsertionSort, and Selection Sort.

Bubble Sort in Java

We can create the java program to sort array elements using bubble sort. Bubble sort algorithm is known as the most straightforward sorting algorithm.

In the bubble sort algorithm, an array is traversed from the first element to the last item. Here, the current item is compared with the next item of the array. If the current element is greater than the next element, it is swapped.

#How it works:

In bubble sort, we first take two loops, one loop is for making one by one value of the array, and the other is to traverse the array. The second loop is the nested loop of the first one.

That nested loop does all work, it compares its current value with the next neighbor value, and if it finds the smaller one, swap it with the current one.

We will understand this with one example.

#Algorithm

Step1: Take the input of N numbers as an array arr

Step2: Repeat step 2 to 5 For(i=0;i<n;i++)

Step3: For(j=0;j<n-i-1;j++)

Step4: if(arr[j]>arr[j+1]

Step5: swap(arr[j],arr[j+1])

Step6: End

#Example with explanation

Let’s take one array:

{45,24,64,2,10}

We will apply bubble sort in it… We will only see where the swapping are performed.

#First Pass

 {45,24,64,2,10} —-> {24,45,64,2,10}

 {24,45,64,2,10} —-> {24,45,2,64,10}

 {24,45,2,64,10} —-> {24,45,2,10,64}

#Second Pass

{24,45,2,10,64} —-> {24,2,45,10,64}

{24,2,45,10,64} —-> {24,2,10,45,64}

#Third Pass

{24,2,10,45,64} —-> {2,24,10,45,64}

{2,24,10,45,64} —-> {2,10,24,45,64}

Like this, the fourth pass will also be performed but no swapping will be performed as the final sorted array we got in the third pass only.

The final sorted array is: {2,10,24,45,64}

Now we will see the program of bubble sort.

import java.util.*;

class Bubble {
  public static void main(String args[]) {
    Scanner s = new Scanner(System.in);
    System.out.println("\nEnter the length of the array:");
    int len = s.nextInt();
    int[] arr = new int[len];
    System.out.println("Enter the elements of the array:\n");
    for (int i = 0; i < len; i++) {
      arr[i] = s.nextInt();
    }
    // Performing Bubble Sort Now

    for (int i = 0; i < len - 1; i++) {
      for (int j = 0; j < len - i - 1; j++) {
        // checking if previous value is
        // grater than next one or not
        if (arr[j] > arr[j + 1]) {
          // temp will temporarly store
          // the value of arr[j]
          // then we will swap the values
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }

    System.out.println("Array after sorting is:\n");
    for (int i = 0; i < len; i++)
      System.out.print(arr[i] + " ");
    System.out.println("\n");
  }
}

See the following output.

 

Bubble Sort In Java Example

#Complexity analysis:

In general, as we have N numbers, so we have to do,

(N-1)+(N-2)+(N-3)+…+2+1 = ((N-1)*N)/2 comparisons.

So, the complexity of the algorithm is O(n^2)

This is for the worst-case and average-case

The complexity for Best Case is O(n)

#Optimized solution of bubble sort

As we have seen above that the program keeps running even after getting the final sorted array in any previous pass. But the program will run until it complete n-1 pass. So we will make one program where the program will be stopped when we will get our final sorted array. See the program below of optimized solution.

See the following program.

import java.util.*;

class Bubble {
  public static void main(String args[]) {
    Scanner s = new Scanner(System.in);
    System.out.println("\nEnter the length of the array:");
    int len = s.nextInt();
    int[] arr = new int[len];
    System.out.println("Enter the elements of the array:\n");
    for (int i = 0; i < len; i++) {
      arr[i] = s.nextInt();
    }
    // Performing Bubble Sort Now
    int flag = 1;
    // using flag variable to check if there is any swap inside the nested loop
    // if not, then the outer loop will stop executing
    // and that time we will get our final sorted value too
    for (int i = 0; i < len - 1 && flag == 1; i++) {
      flag = 0;
      for (int j = 0; j < len - i - 1; j++) {
        // checking if previous value is
        // grater than next one or not
        if (arr[j] > arr[j + 1]) {
          // temp will temporarly store
          // the value of arr[j]
          // then we will swap the values
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          // changing flag variable to 1
          flag = 1;
        }
      }
    }

    System.out.println("Array after sorting is:\n");
    for (int i = 0; i < len; i++)
      System.out.print(arr[i] + " ");
    System.out.println("\n");
  }
}

See the following output.

 

Java Bubble Sort Tutorial

Finally, Bubble Sort In Java Example | Java Bubble Sort Program is over.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.