import java.util.Random;

public class Test
{
    public static void sortLinear(Comparable[] x)
    {
        for(int i=1;i<x.length;i++)
        {
            int pos = linearSearch(x,i);
            Comparable tmp = x[i];
            for(int j=i;j>pos;j--)
                x[j] = x[j-1];
            x[pos] = tmp;
        }
    }

    private static int linearSearch(Comparable[] x, int sorted)
    {
        for(int i=0;i<sorted;i++)
            if(x[i].compareTo(x[sorted])>0)
                return i;
        return sorted;
    }

    public static void main(String[] args)
    {
        Comparable[] x = new Comparable[50];
        Random randomGen = new Random();

        for(int i=0;i<50;i++)
        {
            x[i] = randomGen.nextInt(5000);
            System.out.print(x[i] + " ");
        }
        System.out.println();

        sortLinear(x);

        for(int i=0;i<50;i++)
            System.out.print(x[i] + " ");
        System.out.println();
    }
}