Bubble Sort

Steps:

Code:

import java.util.Arrays;

class BubbleSort {

        static public void bubbleSort(int[] in) {

                int len = in.length;

                for(int i=len; i>1; i--) {

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

                                if(in[j] > in[j+1]) {

                                        //swap

                                        int temp = in[j];

                                        in[j] = in[j+1];

                                        in[j+1] = temp;

                                }

                        }

                }

        }

        static public void optimizedBubbleSort(int[] in) {

                int len = in.length;

                for(int i=len; i>1; i--) {

                        boolean swapped = false;

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

                                if(in[j] > in[j+1]) {

                                        swapped = true;

                                        int temp = in[j];

                                        in[j] = in[j+1];

                                        in[j+1] = temp;

                                }

                        }

                        if(!swapped)

                                return;

                }

        }

        static public void main(String[] args) {

                int in[] = {6, 5, 3, 1, 8, 7, 2, 4};

                System.out.println(Arrays.toString(in));

                optimizedBubbleSort(in);

                System.out.println(Arrays.toString(in));

        }

}

eg:

Complexity Analysis: