import java.util.Scanner;
public class SortingAlgorithms{
    public static void insertionSort (int a[]){
        int count1 =0, count2 = 0;
        for (int i = 1; i < a.length; i++){
            int j = i;
            count1++; // number of passes/outer loop count
            while (j > 0 && a[j] < a[j-1]){
                count2++; // inner loop count
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
                j--;
            }
            System.out.println ("After Pass#" + count1 + " : ");    
            print(a);
        }
        System.out.println ("Total Number of Passes/Outer Loops = " + count1); 
        System.out.println ("Total Number of Inner Loops = " + count2);
        System.out.println ("Total Number of Loops = " + (count1 + count2));
    }

    public static void selectionSort (int a[]){
        int count1 =0, count2 = 0;
        for (int i = 0; i < a.length-1; i++){
            int smallest = a[i];
            int smallestCell = i;
            count1++; // number of passes/outer loop count
            for (int j = i+1 ; j < a.length; j++){
                count2++; // inner loop count
                if (a[j] < smallest){
                    smallest = a[j];
                    smallestCell = j;
                }
            }
            if (smallest != a[i]){
                int temp = a[i];
                a[i] = a[smallestCell];
                a[smallestCell] = temp;
            }
            System.out.println ("After Pass#" + count1 + " : ");    
            print(a);
        }
        System.out.println ("Total Number of Passes/Outer Loops = " + count1); 
        System.out.println ("Total Number of Inner Loops = " + count2);
        System.out.println ("Total Number of Loops = " + (count1 + count2));
    }

    public static void bubbleSort (int a[]) {
        boolean flag = true;
        int n = a.length;
        int count1 = 0, count2 = 0;
        while (count1 < n-1 && flag) { //number of passes
            count1++; // Start a new pass/outer loop count
            flag = false;
            for (int i = 0; i < (n- count1); i++) {// Each pass
                count2++; // inner loop count
                if (a[i] > a[i+1]){ // swap
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    flag = true;
                }
            }
            System.out.println ("After Pass#" + count1 + " : ");    
            print(a);
        }
        System.out.println ("Total Number of Passes/Outer Loops = " + count1); 
        System.out.println ("Total Number of Inner Loops = " + count2);
        System.out.println ("Total Number of Loops = " + (count1 + count2));
    }

    public static void print(int a[]){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + "  " );
        }
        System.out.println("\n");

    }

    public static void main (String args[])  {
        // worst case
        // int a[] = {5,4,3,2,1}; 
        // int b[] = {5,4,3,2,1}; 
        // int c[] = {5,4,3,2,1}; 
        //best case
        // int a[] = {1,2,3,4,5}; 
        // int b[] = {1,2,3,4,5}; 
        // int c[] = {1,2,3,4,5}; 
        // average case
        int a[] = {1,2,5,3,4};
        int b[] = {1,2,5,3,4};
        int c[] =  {1,2,5,3,4};

        System.out.println ("Array before sorting");
        print(a);
        System.out.println ("Sorting using Insertion Sort");
        insertionSort(a);
        System.out.println("\n");
        System.out.println ("Sorting using Bubble Sort");
        bubbleSort(b);
        System.out.println("\n");
        System.out.println ("Sorting using Selection Sort");
        selectionSort(c);
    }
}