Java - Bubble Sort Algorithm

We have studied about searching algorithms Linear Search and Binary Search in previous post. Now I am starting a series of sorting algorithms. Sorting algorithm are used to sort a given array or collection in ascending or descending order according to the required order.

We will start with the simplest sorting algorithm - Bubble Sort. Bubble sort is good for very small size collections only. For bigger collections we have many other better algorithms available like Quick Sort and Merge Sort etc. I will write separate articles for all sorting algorithms.  

Bubble Sort -

Bubble sort is the simplest sorting algorithm. Bubble sort simply start a loop for all elements in the array and compare the adjacent pairs, If elements are in wrong order it just swap the elements and continue till the all elements comes in sorted order. 

Simple steps to perform bubble sort - 

• Given : An array of n elements in unsorted order.
• Required : An array of n elements in ascending order. 
• Start a loop from i= 0 to n-1.
• Start an inner loop from j=1 to n-i, compare each adjacent elements. If elements are not in ascending order swap them. On complete iteration last element in the array will be the biggest element.
• Get the sorted array.

Pseudo code (Ascending order)- 

# Input: Array elements of length n in unsorted order
# Output: Array elements of length n in ascending order

    n = length(elements)

    for i=0 to n-1 

       for j = 1 to n-i

          if elements[j-1] > elements[j] then

             swap(elements[j-1], elements[j])

          end if

       End for loop.

    End while loop.

Asymptotic Analysis of Bubble Sort Algorithm -

Best Case Scenario - If the given array or collection is already in sorted order. Best case time complexity for bubble sort is O(n).

Worst Case Scenario - If the given array or collection in reversed sorted order.  Worst case time complexity for bubble sort is О(n²).

Complexity - Complexity of bubble sort algorithm is О(n²). 

Bubble Sort Implementation in Java  -

package javaprinciples.dsa;

public class BubbleSort {

public static void main(String[] args) {

int elements[] = { 4, 12, 56, 2, 7, 123, 6, 78 };

System.out.print("Input unsorted array -");

for (int element : elements) {

System.out.print(element + " ");

}

bubbleSort(elements);

System.out.print("\nOutput sorted array -");

for (int element : elements) {

System.out.print(element + " ");

}

}

static void bubbleSort(int[] elements) {

int n = elements.length;

int temp = 0;

for (int i = 0; i < n; i++) {

for (int j = 1; j < (n - i); j++) {

if (elements[j - 1] > elements[j]) {

temp = elements[j - 1];

elements[j - 1] = elements[j];

elements[j] = temp;

}

}

}

}

}

Output -

Input unsorted array -4 12 56 2 7 123 6 78 

Output sorted array -2 4 6 7 12 56 78 123 

Note - This is the simplest implementation of bubble sort algorithm. Above implementation will always sort the collection with О(n²) complexity. This can be optimized to make it more faster by breaking the loop if array is sorted before completing all the loops. Try to optimize above program by yourself.

Check below links also-
Linear Search Algorithm analysis and implementation in Java
Binary Search Algorithm analysis and implementation in Java
Java8 - Lambda Expressions in Java
Java8 - Default and static methods in Interface
How to create Immutable classes in JAVA
Method overloading versus method overriding in Java
Difference between Interface and Abstract class
Difference between Abstraction and Encapsulation

Difference between Comparable and Comparator in Java