CareerCup

Counting Sort would fit perfectly here.

Steps:
1) Create an array 'result[]' of size 10. So now, our index will range from 0-9.
2) Simply iterate over the given array of 10000 elements and maintain a count in the result[] array for each element.
3) Once step 2 is complete, iterate over the result[] array and enter the encountered values in the given array.
ex- If res[0] = 78 then enter 78 1s in the given array.
If res[9] = 345 then enter 345 10s into the given array
4) After step 3 we have our sorted array.

The time complexity here would O(n) and space complexity is O(1) as an extra array of 10 elements is used.

Code would be as follows:

public int[] sortGivenArrayOf1To10Range(int[] givenArray)
	{
		if(givenArray==null || givenArray.length==0)
			return null;
		
		int[] res = new int[10];
		
		for(int individualElement:givenArray)
		{
			res[individualElement-1]+=1;
		}
		
		int count=0;
		int j=0;
		
		for(int i=0;i<res.length;i++)
		{
			count=res[i];
			
			while(count>0)
			{
				givenArray[j++]=i+1;
				count--;
			}
				
		}
		
		return givenArray;
	}

Bucket sort. Set a hashtable of length 10.

Scan the array and increment the numbers in the array when that number is found in the array.Finally, overwrite the array with the information from the hashtable.

Count sort!!!

Total iterations around the loop twice.
First just get the count of how many times each number is repeated. Save it in array of size ten where the index represents the number(0-10) and the value stores the count. Then refill the array with the corresponding count.
Hope this helps. Done with O(N) Complexity

counting sort

What if I want to find a program (FAP) first?

public class CountingSort {
    public static void main(String[] args){
        int[] arr = {1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,5,1,1,1,1,1,1,2,2,2,3,3,3,9,9,9,9,9,9,9,9,6,7,8,9,0,4,4,4,4,4,4,4,4,4,4,4,4};
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for(int i=0;i<arr.length;i++) {
            if(hm.containsKey(arr[i])) {
                hm.put(arr[i], (hm.get(arr[i]))+1);
            }else{
                hm.put(arr[i], 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : hm.entrySet()) {
        //    System.out.println(entry.getKey() +" - "+ entry.getValue());
            int key = entry.getKey();
            int value = entry.getValue();
            while(value!=0) {
                System.out.print(key);
                value--;
            }
        }
    }