@@ -0,0 +1,2366 @@
+/*%0A * To change this license header, choose License Headers in Project Properties.%0A * To change this template file, choose Tools %7C Templates%0A * and open the template in the editor.%0A */%0Apackage countingsort;%0A%0Aimport java.util.Arrays;%0Aimport java.util.Random;%0A%0A/**%0A *%0A * @author Dante%0A */%0Apublic class CountingSort %7B%0A %0A%0A    /**%0A     * @param args the command line arguments%0A     */%0A    //Time complexity Big Theta(n+k)%0A    static int%5B%5D countingSort(int in%5B%5D) %7B%0A        int leng = in.length; %0A        int max = getMax(in);%0A        //the size of the array is +1 from the max value since it start from 0%0A        int count%5B%5D = new int%5Bmax+1%5D;%0A        int out%5B%5D = new int%5Bleng%5D;  %0A        %0A        //max = k%0A        //leng = n%0A        %0A        //O(k)%0A        for(int i = 0; i %3C max; i++)%7B%0A            count%5Bi%5D = 0; %0A        %7D %0A        %0A        System.out.println(%22-----------%22); %0A        //O(n)%0A        for(int j = 0; j %3C leng; j++)%7B%0A            count%5Bin%5Bj%5D%5D = count%5Bin%5Bj%5D%5D+1;   %0A        %7D %0A        %0A        System.out.println(%222 : %22+Arrays.toString(count));%0A        //O(k)%0A        for(int i = 1 ; i %3C= max; i++)%7B %0A            count%5Bi%5D =count%5Bi%5D+ count%5Bi-1%5D; %0A            %0A        %7D%0A        %0A        System.out.println(%22///////////%22);%0A        //O(n)%0A        for(int j = 0; j %3C leng; j++)%7B%0A            out%5Bcount%5Bin%5Bj%5D%5D-1%5D = in%5Bj%5D;%0A            count%5Bin%5Bj%5D%5D = count%5Bin%5Bj%5D%5D-1;%0A        %7D%0A         %0A        checkSort(in);%0A        return out;%0A       %0A    %7D%0A%0A     static void checkSort(int%5B%5D arr)%7B%0A        boolean test =true;%0A        for(int i = 1; i %3Carr.length; i++ )%7B%0A            if(arr%5Bi%5D%3Carr%5Bi-1%5D)%0A                test = false;%0A        %7D%0A        %0A        if(test) System.out.print(%22Ordinato%22);%0A        else System.out.print(%22Non Ordinato%22);%0A    %7D%0A    %0A    public static void main(String args%5B%5D) %7B%0A        int leng = 15; %0A        int arr%5B%5D = populateArr(leng);%0A        System.out.println(Arrays.toString(countingSort(arr)));%0A    %7D%0A    %0A    static int getMax(int arr%5B%5D )%0A    %7B%0A        int l = arr.length;%0A        int mx = arr%5B0%5D;%0A        for (int i = 1; i %3C l ; i++)%0A            if (arr%5Bi%5D %3E mx)%0A                mx = arr%5Bi%5D;%0A        return mx;%0A    %7D%0A%0A    private static int%5B%5D populateArr(int n)%7B%0A%09%09%0A%09    int%5B%5D sort = new int%5Bn%5D;%0A%09    Random random = new Random();%0A%09    for (int i = 0; i %3C sort.length; i++) %7B%0A%09%09    sort%5Bi%5D = random.nextInt(10);%0A%09    %7D%0A%09%0A%09    return sort;%0A%09%7D%0A%0A%7D%0A

Create CountingSort.java