Monday, December 3, 2018

Bubble Sort Program in Java

In this post we’ll see how to write Bubble sort program in Java. Out of the three simpler sorting algorithms bubble sort, insertion sort and selection sort, bubble sort is considered the simplest sorting algorithm and the slowest too because of a proportionally large number of swaps along with the comparisons.

How Bubble sort works

In bubble sort you start by comparing the first two elements (index 0 and index 1). If element at index 0 is greater than the element at index 1 then those two elements are swapped, if it is not then you do nothing. Then the next 2 elements are compared (index 1 and index 2) and elements are swapped based on the same logic.

So the steps for bubble sort are as follows-

  1. Compare the adjacent elements.
  2. If element at the left is greater than the element at the right then swap the elements.
  3. Move one position right.

You continue doing that until you reach the last element, by then you have the greatest element at the right. Since the biggest elements bubble up to the top end thus the name “Bubble sort”.

This is the first pass, in the next iteration again you start from the two leftmost elements and compare the elements and swap if required. Since the rightmost element is already in its sorted position so this iteration runs till (N-1) elements.

For example if you have an array [5, 2, 6, 1] then in the first iteration-

  1. Initially 5 is compared with 2, since 5 (element at left) is greater than 2 (element at right), elements are swapped making the array [2, 5, 6, 1].
  2. Move over one position and compare 5 and 6, since 5 is not greater than 6 so nothing is done and array remains [2, 5, 6, 1].
  3. Again move over one position and compare 6 and 1, since 6 is greater than 1 elements are swapped giving us the array as [2, 5, 1, 6].

In the next iteration last element is not included in the comparison as it is already at its final position.

Bubble Sort Java program

public class BubbleSort {

  public static void main(String[] args) {
    int[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
    int[] sortedArray = bubbleSort(intArr);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }
    
  private static int[] bubbleSort(int[] intArr){
    // right to left 
    for(int i = intArr.length; i > 1; i--){
      for(int j = 0; j < i - 1; j++){
        //if greater swap elements
        if(intArr[j] > intArr[j+1]){
          swapElements(j, intArr);
        }
      }            
    }
    return intArr;
  }
    
  private static void swapElements(int index, int[] intArr){
    int temp = intArr[index];
    intArr[index] = intArr[index+1];
    intArr[index+1] = temp;        
  }
}

Output

Sorted array is- 
2 7 10 34 47 54 62 85 92 106 

Time and Space complexity of Bubble sort

For bubble sort there are two loops that go through the elements that makes it a complexity of N*N i.e. O(N2). In bubble sort the number of swaps is also high which makes it slow.

Bubble sort is an in place sorting algorithm so there is no auxiliary space requirement. Thus the space complexity of Bubble sort is O(1).

That's all for this topic Bubble Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Shell Sort Program in Java
  2. Tree Sort in Java Using Binary Search Tree
  3. Reverse Each Word of The String - Java Program
  4. Find Duplicate Characters in a String With Repetition Count - Java Program
  5. Factorial Program in Java

You may also like-

  1. Producer-Consumer Java Program Using ArrayBlockingQueue
  2. Converting String to Enum Type - Java Program
  3. How to Read File From The Last Line in Java
  4. Difference Between Two Dates - Java Program
  5. How LinkedList Class Works Internally in Java
  6. Difference Between ArrayList And CopyOnWriteArrayList in Java
  7. strictfp in Java
  8. Transaction Management in Spring

No comments:

Post a Comment