package datastructure;

import java.util.Random;

public class Sort {

    private static int count=1;

    

    public static void main(String[] args) {

        int[] a=new int[100];

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

            a[i]=new Random().nextInt(100);

        }

        System.out.print("0:");

        for (int i : a) {

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

        }

        System.out.println();

        System.out.println("=============");

        sort2(a);

    }

    static void sort(int[] a){

        

        for(int i=a.length-1;i>1;i--){

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

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

                    int tmp=a[j];

                    a[j]=a[j+1];

                    a[j+1]=tmp;

                }

            }

            System.out.print(count+":");

            for(int ii=0;ii<a.length;ii++){

                System.out.print(a[ii]+" ");

            }

            System.out.println();

            count++;

        }

        

    }

    static void sort1(int[] a){

        

        for(int i=0;i<a.length;i++){

            for(int j=i+1;j<a.length;j++){

                if(a[i]>a[j]){

                    int tmp=a[i];

                    a[i]=a[j];

                    a[j]=tmp;

                }

            }

            System.out.print(count+":");

            for(int ii=0;ii<a.length;ii++){

                System.out.print(a[ii]+" ");

            }

            System.out.println();

            count++;

        }

        

    }

    static void sort2(int[] a){

        

        for(int i=1;i<a.length;i++){

            int tmp=a[i];

            int j=i;

            while(j>0&&a[j-1]>tmp){

                a[j]=a[j-1];

                j--;

            }

            a[j]=tmp;

            System.out.print(count+":");

            for(int ii=0;ii<a.length;ii++){

                System.out.print(a[ii]+" ");

            }

            System.out.println();

            count++;

        }

        

    }

}