Sorting – Java2Blog

Topological Sort in java

Java2blog — Sat, 04 Nov 2017 05:55:37 +0000

In this post, we will see about Topological Sorting in the graph.

Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is possible only for Directed Acyclic Graph(DAG). If there is a cycle in graph, then there won’t be any possibility for Topological Sort.

Topological Sort example

Let’s understand with the help of an example.
You might have used maven as build tool. If you have multiple modules in the maven, maven build projects on the basis of dependencies.
Let’s say you have 4 maven modules.

maven-model
maven-business-logic
mavan-util
maven-ui

Now you need to build maven-model before maven-business-logic because maven-business-logic uses code from maven-model.
Similiarly, maven-model ,maven-business-logic and maven-util should be built before maven-ui as maven-ui depends on all three modules.

So, in this scenario, we can compute Topological sorting , so that maven can build them in the correct order.

Topological Sort Algorithm

Please note that there can be more than one solution for topological sort.

Let’s pick up node 30 here.

Node 30 depends on node 20 and node 10.
Node 10 depends on node 20 and node 40.
Node 20 depends on node 40.

Hence node 10, node 20 and node 40 should come before node 30 in topological sorting.

This algorithm is a variant of Depth-first search. In depth first search, we first print the vertex and then go to its neighbours but in case of topological sort, we don’t print vertex immediately instead we push it to the Stack.

In topological sorting, we will have a temporary stack. We are not going to print the vertex immediately, we first recursively call topological sorting for all its neighbour vertices, then push it to a stack. We will print stack once we are done with recursive topolgical sorting.

Why it works?

It works because when you push any node to stack, you have already pushed its neighbours(and their neighbours and so on),so node which does not have any dependency will be on the top of stack. In our case, we will have 40 on top of the stack.

Java program to implement topological sorting

package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TopologicalSort
{ 
    Stack stack;

    public TopologicalSort() {
        stack=new Stack<>();
    }
    static class Node
    {
        int data;
        boolean visited;
        List neighbours;

        Node(int data)
        {
            this.data=data;
            this.neighbours=new ArrayList<>();

        }
        public void addneighbours(Node neighbourNode)
        {
            this.neighbours.add(neighbourNode);
        }
        public List getNeighbours() {
            return neighbours;
        }
        public void setNeighbours(List neighbours) {
            this.neighbours = neighbours;
        }
        public String toString()
        {
            return ""+data;
        }
    }

    // Recursive toplogical Sort
    public  void toplogicalSort(Node node)
    {
        List neighbours=node.getNeighbours();
        for (int i = 0; i < neighbours.size(); i++) {
            Node n=neighbours.get(i);
            if(n!=null && !n.visited)
            {
                toplogicalSort(n);
                n.visited=true;
            }
        }
        stack.push(node);
    }

    public static void main(String arg[])
    {

        TopologicalSort topological = new TopologicalSort();
        Node node40 =new Node(40);
        Node node10 =new Node(10);
        Node node20 =new Node(20);
        Node node30 =new Node(30);
        Node node60 =new Node(60);
        Node node50 =new Node(50);
        Node node70 =new Node(70);

        node40.addneighbours(node10);
        node40.addneighbours(node20);
        node10.addneighbours(node30);
        node20.addneighbours(node10);
        node20.addneighbours(node30);
        node20.addneighbours(node60);
        node20.addneighbours(node50);
        node30.addneighbours(node60);
        node60.addneighbours(node70);
        node50.addneighbours(node70);

        System.out.println("Topological Sorting Order:");
        topological.toplogicalSort(node40);

        // Print contents of stack
        Stack resultStack=topological.stack;
        while (resultStack.empty()==false)
            System.out.print(resultStack.pop() + " ");
    }

}

When you run above program, you will get below output:

Topological Sorting Order:
40 20 50 10 30 60 70

Time Complexity

It is very much similar to Depth-first search with just an extra stack. So its time complexity is O(V+E)

.That’s all about Topological Sort in java.

Sort array in java

Java2blog — Wed, 23 Aug 2017 18:03:47 +0000

In this post, we will see how to sort an array in java.

There are various ways to sort array in java. You can implement different sorting algorithms to sort an array.

You can use Arrays.sort method to sort array in java. There are various overloaded versions of Arrays.sort method. You can go through it over here.

Java Sort Array

Let’s see some example to sort an array in java.

Sort Array of numbers

Sorting an array of numbers is very easy. You just need to use Array.sort method to sort array of numbers.

package org.arpit.java2blog;

import java.util.Arrays;

public class SortArrayInt {

    public static void main(String[] args) {
        int arr[]={7,33,22,11,20,5,2};
        System.out.println("Before Sorting");
        System.out.println("===============");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }

        Arrays.sort(arr);

        System.out.println();
        System.out.println("===============");
        System.out.println("After Sorting");
        System.out.println("===============");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

When you run above code, you will get below output:

Before Sorting
===============
7 33 22 11 20 5 2
===============
After Sorting
===============
2 5 7 11 20 22 33

Sort Array of Strings

Sorting an array of String is also very easy. You just need to use Array.sort method to sort array of Strings.This will sort array of String in ascending order.

package org.arpit.java2blog;

import java.util.Arrays;

public class SortArrayString {

    public static void main(String[] args) {
        String arr[]={"Martin","Andy","John","Mary"};
        System.out.println("Before Sorting");
        System.out.println("===============");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }

        Arrays.sort(arr);

        System.out.println();
        System.out.println("===============");
        System.out.println("After Sorting");
        System.out.println("===============");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

When you run above code, you will get below output:

Before Sorting
===============
Martin Andy John Mary
===============
After Sorting
===============
Andy John Martin Mary

Sort array of custom objects

For Sorting array of custom objects, Custom object should implement comparable interface and then pass it to Array.sort method.You can also create comparator object and pass it to Array.sort method.

package org.arpit.java2blog;

import java.util.Arrays;

public class Employee implements Comparable{
    String name;
    int age;

    Employee(String name,int age)
    {
        this.name=name;
        this.age=age;
    }

    public static void main(String[] args)
    {
        Employee e1=new Employee("Martin", 20);
        Employee e2=new Employee("Andy", 18);
        Employee e3=new Employee("John", 22);
        Employee e4=new Employee("Mary", 21);
        Employee[] empArray={e1,e2,e3,e4};

        System.out.println("Before Sorting");
        System.out.println("===============");
        for (int i = 0; i < empArray.length; i++) {
            System.out.print(empArray[i]+ " ");
        }

        Arrays.sort(empArray);

        System.out.println();
        System.out.println("===============");
        System.out.println("After Sorting");
        System.out.println("===============");
        for (int i = 0; i < empArray.length; i++) {
            System.out.print(empArray[i]+" ");
        }
    }

    public String toString()
    {
        return "[ name="+name+" age="+age+" ]";
    }

    @Override
    public int compareTo(Employee e) {
        return name.compareTo(e.name);
    }
}

When you run above code, you will get below output:

Before Sorting
===============
[ name=Martin age=20 ] [ name=Andy age=18 ] [ name=John age=22 ] [ name=Mary age=21 ] ===============
After Sorting
===============
[ name=Andy age=18 ] [ name=John age=22 ] [ name=Martin age=20 ] [ name=Mary age=21 ]

That’s all about Sorting an array in java.

Selection sort in java

Java2blog — Wed, 12 Oct 2016 18:47:00 +0000

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs.

Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs.

Selection sort algorithm

Find the minimum element in the list.
Swap minimum element with current element.
Repeat the whole process until array is fully sorted.

Below visualization will make it more clear

Selection sort algorithm

package org.arpit.java2blog;

import java.util.Arrays;

public class SelectionSortMain {

 public static int[] selectionSort(int[] arr){

 for (int i = 0; i < arr.length - 1; i++)
 {
 int index = i;
 for (int j = i + 1; j < arr.length; j++)
 if (arr[j] < arr[index])
 index = j;

 int smallerNumber = arr[index];
 arr[index] = arr[i];
 arr[i] = smallerNumber;
 }
 return arr;
 }

 public static void main(String a[]){

 int[] arr = {40,10,-30,45,39,32};
 System.out.println("Before Sorting : ");
 System.out.println(Arrays.toString(arr));
 arr = selectionSort(arr);
 System.out.println("===================");
 System.out.println("After Sorting : ");
 System.out.println(Arrays.toString(arr));
 }
}

When you run above program, you will get below output:

Before Sorting :
[40, 10, -30, 45, 39, 32]
===================
After Sorting :
[-30, 10, 32, 39, 40, 45]

Time complexity

Best case : O(N^2)
Average case : O(N^2)
Worst case : O(N^2)

To understand more about complexity,please go through complexity of algorithm.

Shell sort in java

Java2blog — Wed, 12 Oct 2016 18:08:00 +0000

Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell.
It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell sort is ultimately insertion sort.
In short, it improves insertion sort by comparison and exchange elements that are far away.
Shell sort uses a sequence that can be referred as increment sequence. Shell sort makes multiple passes over array and sort number of equally sized array using insertion sort.

Java program to implement shell sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class ShellSortMain {
 public static void main(String[] args) {
 int[] array = { 22, 53, 33, 12, 75, 65, 887, 125, 37, 977 };
 System.out.println("Before Sorting : ");
 System.out.println(Arrays.toString(array));
 System.out.println("===================");
 System.out.println("After Sorting : ");
 array = shellsort(array);
 System.out.println(Arrays.toString(array));
 }

 private static int[] shellsort(int[] array) {

 // first part uses the Knuth's interval sequence
 int h = 1;
 while (h <= array.length / 3) {
 h = 3 * h + 1; // h is equal to highest sequence of h<=length/3
 // (1,4,13,40...)
 }

 // next part
 while (h > 0) { // for array of length 10, h=4

 // This step is similar to insertion sort below
 for (int i = 0; i < array.length; i++) {

 int temp = array[i];
 int j;

 for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h) {
 array[j] = array[j - h];
 }
 array[j] = temp;
 }
 h = (h - 1) / 3;
 }
 return array;
 }

}

When you run above program, you will get below output:

Before Sorting : 
[22, 53, 33, 12, 75, 65, 887, 125, 37, 977]
===================
After Sorting : 
[12, 22, 33, 37, 53, 65, 75, 125, 887, 977]

Time complexity:
Best case: O(n)
Average case: Depends on gaps
Worst case : o(nlog2n)

Quick Sort in java

Java2blog — Wed, 12 Oct 2016 15:19:00 +0000

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.
In quick sort, we first choose a pivot and divide into two sublists,one will contain elements lower than pivot and other will have elements greater than pivot.

Quick sort Algorithm

Lets say array is arr[]

Choose a pivot, it is generally mid element of the list.
Initialise two index variable , left=0 and right=arr.length-1
Increment left variable until you get element higher than pivot.
Decrement right variable until you get element lesser than pivot
swap arr[left] and arr[right]
Recursively sort sublists(sublist with less than pivot, sublist greater than pivot) using above algorithm.
In the end , you will get sorted array.

Quick Sort implementation

package org.arpit.java2blog;

import java.util.Arrays;

public class QuickSortMain {

    private static int array[];

    public static void sort(int[] arr) {

        if (arr == null || arr.length == 0) {
            return;
        }
        array = arr;
        quickSort(0, array.length-1);
    }

    private static void quickSort(int left, int right) {

        int i = left;
        int j = right;
        // find pivot number, we will take it as mid
        int pivot = array[left+(right-left)/2];

        while (i <= j) {
            /**
             * In each iteration, we will increment left until we find element greater than pivot
             * We will decrement right until we find element less than pivot
             */
            while (array[i] < pivot) { i++; } while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (left < j)
            quickSort(left, j);
        if (i < right)
            quickSort(i, right);
    }

    private static void exchange(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String a[]){
        int[] input = {33,21,45,64,55,34,11,8,3,5,1};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(input));
        sort(input);
        System.out.println("==================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(array));

    }
}

Output:

Before Sorting :
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1] ==================
After Sorting :
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]

Time complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
To understand more about complexity,please go through complexity of algorithm.

That’s all about quick sort in java.

Counting Sort in java

Java2blog — Wed, 12 Oct 2016 11:08:00 +0000

Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times.
Basic idea of counting sort to find number of elements less than X, so X can be put to its correct position.

Steps for Counting Sort:

Take an array to store count of each elements. Lets say array elements contain 1 to K then initialize count array with K.
Now add elements of count array, so each elements store summation of its previous elements.
Modified count array stores position of elements in actual sorted array.
Iterate over array and put element in correct sequence based on modified count array and reduce the count by 1.

Java program for counting sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class CountingSortMain {

 public static void main(String[] args) {
 System.out.println("Before Sorting : ");
 int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4};
 System.out.println(Arrays.toString(arr));
 arr=countingSort(arr);
 System.out.println("=======================");
 System.out.println("After Sorting : ");
 System.out.println(Arrays.toString(arr));
 }

 static int[] countingSort(int arr[])
 {
 int n = arr.length;

 // The result will store sorted array
 int result[] = new int[n];

 // Initialize count array with 9 as array contains elements from range 1 to 8.
 int count[] = new int[9];
 for (int i=0; i<9; ++i)
 count[i] = 0;

 // store count of each element in count array
 for (int i=0; i
When you run above program, you will get below output:

Before Sorting : 
[1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4]
=======================
After Sorting : 
[1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8]
Time Complexity= O(N)
I would suggest to try to debug the program to understand it better.

Heap sort in java

Java2blog — Wed, 12 Oct 2016 11:08:00 +0000

In this post, we will see how to implement heap sort in java.
I will divide heap sort in multiple parts to make it more understandable.

What is heap?

A heap is a tree with some special properties, so value of node should be greater than or equal to(less than or equal to in case of min heap) children of the node and tree should be complete binary tree.

Binary heaps

Binary heaps are those heaps which can have up to 2 children. We will use binary heaps in our next few sections.

Understanding complete binary tree

Complete binary tree is a binary tree whose leaves are at h or h-1 level where h is height of the tree.
Index of left child= 2*(index of its parent)+1
Index of right child= 2*(index of its parent)+2

Types of heaps

There are two types of heap.

Max heap
Min heap

Max heap : It is binary heap where value of node is greater than left and right child of the node.

Min heap : It is binary heap where value of node is lesser than left and right child of the node.

Heapifying an element:

Once we create a heap , it may not satisfy heap property. In order to make it heap again, we need to adjust locations of the heap and this process is known as heapifying the elements.
In order to create a max heap, we will compare current element with its children and find the maximum, if current element is not maximum then exchange it with maximum of left or right child.

Java code for heapifying element at location i :

public static void heapify(int[] arr, int i, int size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max;
        if (left <= size && arr[left] > arr[i]) {
            max = left;
        } else {
            max = i;
        }

        if (right <= size && arr[right] > arr[max]) {
            max = right;
        }
        // If max is not current node, exchange it with max of left and right child
        if (max != i) {
            exchange(arr, i, max);
            heapify(arr, max, size);
        }
    }

Steps for heap sort

Represent array as complete binary tree.
- Left child will be at 2*i+1 th location
- Right child will be at 2*i+2 th location.
Build a heap.
- All the leaf nodes already satisfy heap property, so we don’t need to heapify them.
- Last leaf node will be present at (n-1)th location, so parent of it will be at (n-1)/2 th location, hence (n-1)/2 will be location of last non leaf node.
- Iterate over non leaf nodes and heapify the elements.
After building a heap, max element will be at root of the heap. We will exchange it with (n-1)th location, so largest element will be at proper place and remove it from the heap by reducing size of n.
When you exchange largest element, it may disturb max heap property, so you need to again heapify it.
Once you do above steps until no elements left in heap, you will get sorted array in the end.

Java code for heap sort

package org.arpit.java2blog;
import java.util.*;

public class HeapSortMain {

   public static void buildheap(int []arr) {

    /*
     * As last non leaf node will be at (arr.length-1)/2
     * so we will start from this location for heapifying the elements
     * */
    for(int i=(arr.length-1)/2; i>=0; i--){
           heapify(arr,i,arr.length-1);
      }
   }

   public static void heapify(int[] arr, int i,int size) {
      int left = 2*i+1;
      int right = 2*i+2;
      int max;
      if(left <= size && arr[left] > arr[i]){
         max=left;
      } else {
         max=i;
      }

      if(right <= size && arr[right] > arr[max]) {
         max=right;
      }
      // If max is not current node, exchange it with max of left and right child
      if(max!=i) {
         exchange(arr,i, max);
         heapify(arr, max,size);
      }
   }

   public static void exchange(int[] arr,int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
   }

   public static int[] heapSort(int[] arr) {

      buildheap(arr);
      int sizeOfHeap=arr.length-1;
      for(int i=sizeOfHeap; i>0; i--) {
         exchange(arr,0, i);
         sizeOfHeap=sizeOfHeap-1;
         heapify(arr, 0,sizeOfHeap);
      }
      return arr;
   }

   public static void main(String[] args) {
      int[] arr={1,10,16,19,3,5};
      System.out.println("Before Heap Sort : ");
      System.out.println(Arrays.toString(arr));
      arr=heapSort(arr);
      System.out.println("=====================");
      System.out.println("After Heap Sort : ");
      System.out.println(Arrays.toString(arr));
   }
}

When you run above program, you will get below output:

Before Heap Sort :
[1, 10, 16, 19, 3, 5] =====================
After Heap Sort :
[1, 3, 5, 10, 16, 19]

Time and space complexity

Time Complexity:
Best case : O(nlogn)
Average case : O(nlogn)
Worst case : O(nlogn)

space complexity:
Since heap sort is inplace sorting algorithm, space complexity is o(1). You don’t need any extra space except swapping variable in heap sort.

insertion sort in java

Java2blog — Wed, 09 Dec 2015 03:47:00 +0000

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs.

In this post, we will see how to implement insertion sort in java. Insertion sort is very much similar to bubble sort.

Insertion sort Algorithm

Insertion sort works by comparing values at index with all its prior elements.We place value at the index where there are no lesser value to the elements. So when you reach last element,we get a sorted array.
Lets see how it works:
Lets say you have array as {100,20,15,30,5,75}

Compare 20 with 100,as 20 is less than 100, our array will become {100,100,15,30,5,75}. We have reached to 0th index, we will place 20 to 0th index {20,100,15,30,5,75}
Compare 15 with 100, as it is less,our array will become {20,100,100,30,5,75}. Now compare 20 with 15, it is again less, our array will become {20,20,100,30,5,75}. As we have reached start of array again. Place 15 at 0th index.our array will become {15,20,100,30,5,75}
Compare 30 with 100, as it is less,our array will become {15,20,100,100,5,75}.Now compare 30 with 20 again, it is more, so we will stop here, As we reached at index where 30 is greater than 15 and 20. so we will put 30 at this index. our array will become {15,20,30,100,5,75}
Compare 5 with 100, as it is less, our array will become {15,20,30,100,100,75}. Now compare 30 with 5 again,it is less,our array will become {15,20,30,30,100,75}. Similarly 20 with 5, it is less,our array will become {15,20,20,30,100,75}.Compare 15 with 5, it is less,our array will become {15,15,20,30,100,75}.As we have reached start of array again. Place 5 at 0th index.our array will become {5,15,20,30,100,75}
Compare 75 with 100, it is less,so our array will become {5,15,20,30,100,100}.Now compare 30 with 75 again, it is more, so we will stop here, As we reached at index where 75 is greater than 5,15,20 and 30. so we will put 75 at this index. our array will become {5,15,20,30,75,100}
Finally we got sorted array.

Insertion sort implementation

I have printed intermediate steps to understand it better:

ublic class InsertionSortMain {
    /*
     * @author: Arpit Mandliya
     */

    public static void main(String args[])
    {
        int  arr[]={100,20,15,30,5,75};
        insertionSort(arr);

    }

    public static int[] insertionSort(int arr[])
    {
        for (int i = 1; i < arr.length; i++) 
        { 
            int valueToSort = arr[i];
            int j; 
            // If we get smaller value than valueToSort then , we stop at that index. 
            for ( j = i; j > 0 && arr[j - 1] > valueToSort; j--) {
                arr[j] = arr[j - 1];
            }

            // We will put valueToSort at that index
            arr[j] = valueToSort;
            System.out.print("Iteration "+(i)+": ");
            printArray(arr);
        }

        return arr;
    }
    public static void printArray(int arr[])
    {
        for (int i = 0; i 
When you run above program, you will get following output:
Iteration 1: 20 100 15 30 5 75 
Iteration 2: 15 20 100 30 5 75 
Iteration 3: 15 20 30 100 5 75 
Iteration 4: 5 15 20 30 100 75 
Iteration 5: 5 15 20 30 75 100

We are iterating from first element to last element.You may notice that each iteration places current element at its right place where all its prior element are less than current element.

Time Complexity
Best case: O(n)
Average case: O(n^2)
Worst case: O(n^2)
To understand more about complexity,please go through complexity of algorithm.

That’s all about insertion sort in java.

Please go through java interview programs for more such programs.

Bubble sort in java

Java2blog — Tue, 08 Dec 2015 17:41:00 +0000

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

In this post, we will see how to implement Bubble sort in java. Bubble sort is also known as sinking sort.Bubble sort is a comparison based sorting algorithm and is very easy to implement.

Bubble sort algorithm

Bubble sort works by iterating first element to last element, comparing two adjacent elements and swapping them if they are not in correct order. Each iteration places next larger value to its correct place.

Why bubble sort is called bubble sort or sinking sort(From wikipedia)

Bubble sort can be done in ascending order or descending order.

Reason for being called Sinking sort

The larger values might be regarded as heavier and therefore be seen to progressively sink to the bottom of the list

Reason for being called Bubble sort

The smaller values might be regarded as lighter and therefore be seen to progressively bubble up to the top of the list

Bubble sort Implementation

I have printed intermediate steps to understand it better:

public class BubbleSortMain {
 /*
  * @author: Arpit Mandliya
 */

 public static void main(String args[])
 {
  int  arr[]={100,20,15,30,5,75,40};
  bubbleSort(arr);

 }

 public static int[] bubbleSort(int arr[])
 {
  for (int i = 0; i < arr.length; i++) {
   for (int j = 0; j < arr.length-1-i; j++) { 
     if(arr[j]>arr[j+1])
     {
       int temp=arr[j];
       arr[j]=arr[j+1];
       arr[j+1]=temp;
     }
   }
   System.out.print("Iteration "+(i+1)+": ");
   printArray(arr);
  }
  return arr;
 }

 public static void printArray(int arr[])
 {
  for (int i = 0; i 
When you run above program, you will get following output:
Iteration 1: 20 15 30 5 75 40 100

Iteration 2: 15 20 5 30 40 75 100

Iteration 3: 15 5 20 30 40 75 100

Iteration 4: 5 15 20 30 40 75 100

Iteration 5: 5 15 20 30 40 75 100

Iteration 6: 5 15 20 30 40 75 100

Iteration 7: 5 15 20 30 40 75 100

You may notice that each iteration places next larger element to its correct place.

Time Complexity:

Best case: O(n)

Average case: O(n^2)

Worst case: O(n^2)

To understand more about complexity,please go through complexity of algorithm.