Sorting an array of int in lexicographic order

Question

I came across a problem such that:

WAP to sort prime numbers smaller than given N by digits. If N is 40, the output should be 11, 13, 17, 19, 2, 23, 29, 3, 31, 37, 39, 5, 7. Note: Limit memory use.

Getting primary number was the easy. But I could not figure out an efficient way of lexicographic sorting of array of integer.

public static void getPrimeNumbers(int limit) {
        for (int i=2; i<=limit; i++) {
            if(isPrime(i)) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int number) {
        for(int j=2; j<number; j++) {
            if(number%j==0) {
                return false;
            }
        }
            return true;
    }

    public static void lexographicSorting() {
        int[] input = {2,3,5,7,11,13,17,19};
        int[] output = {};
        for (int i=0; i<input.length; i++) {
            for(int j=0; j<input.length; j++) {
                ////Stuck at this part.
            }
        }
    }

Answer 1

Just to add to Hunter McMillen answer, Java 8's syntax allows defining a Comnparator in a much cleaner, leaner, way. Since Arrays.sort(int[]) does not have an overloaded variant that takes a Comparator, boxing the array is necessary in order to use a Comparator. E.g.:

int[] output =
    Arrays.stream(input)
          .boxed()
          .sorted(Comparator.comparing(String::valueOf))
          .mapToInt(Integer::intValue)
          .toArray();

Answer 2

Given the constraints on the problem, the more efficient way to solve this problem is to not use String and Integer instances at all. One of the directives of the problem is to limit memory usage. In each of the answers so far, there has been a significant impact on memory (converting to and from Integer and String).

Here is a solution that is likely to be faster, and allocates no heap memory at all (although it has recursion so it may have some stack-effect - about the same as Arrays.sort()). This solves the problem from first-principles, it does not allocate a separate array for the results, and thus, it is relatively long compared to other solutions, but, those other solutions hide a mass of complexity that this solution does not have...

// this compare works by converting both values to be in the same 'power of 10',
// for example, comparing 5 and 20, it will convert 5 to 50, then compare 50 and 20
// numerically.
public static final int compareLexographicallyToLimit(final int limit, int a, int b) {
    if (a == b) {
        return 0;
    }
    if (a > limit || b > limit || a < 0 || b < 0) {
        return a > b ? 1 : -1;
    }

    int max = Math.max(a, b);
    int nextp10 = 1;
    while (max > 10) {
        max /= 10;
        nextp10 *= 10;
    }
    while (a < nextp10) {
        a *= 10;
    }
    while (b < nextp10) {
        b *= 10;
    }
    return a > b ? 1 : -1;
}

private static void sortByRules(final int[] input, final int limit, final int from, final int to) {
    if (from >= to) {
        return;
    }
    int pivot = from;
    int left = from + 1;
    int right = to;
    while (left <= right) {
        while (left <= right && compareLexographicallyToLimit(limit, input[left], input[pivot]) <= 0) {
            left++;
        }
        while (left <= right && compareLexographicallyToLimit(limit, input[pivot], input[right]) <= 0) {
            right--;
        }
        if (left < right) {
            int tmp = input[left];
            input[left] = input[right];
            input[right] = tmp;
            left++;
            right--;
        }
    }
    int tmp = input[pivot];
    input[pivot] = input[right];
    input[right] = tmp;
    sortByRules(input, limit, from, right-1);
    sortByRules(input, limit, right+1, to);

}

public static void main(String[] args) {
    int[] input = {2,3,5,7,11,13,17,19,31,37,41, 43, 100};
    sortByRules(input, 40, 0, input.length - 1);
    System.out.println(Arrays.toString(input));
    sortByRules(input, 15, 0, input.length - 1);
    System.out.println(Arrays.toString(input));
}

Answer 3

If you don't want to convert your integer values to strings (which can be wasteful), you can do something like this.

You can sort the numbers based on the most significant digits. See this post for computing the most significant digit of a number: Getting a values most significant digit in Objective C (it should be easy to port to Java).

Essentially you can use that function as part of your Comparator. You'll need a way to break ties (e.g., numbers with the same most significant digit(s)). If two numbers have the same most significant digits you can pluck them off and re-call this function over and over again as many times as necessary (until you can deem one number greater than the other, or until you run out of digits, indicating that they're equal).

Answer 4

Java String#compareTo already implements this functionality, you can access it pretty easily by converting your Integer objects to String objects and calling compareTo

Arrays.sort(input, new Comparator<Integer>() {
   @Override
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

I can say exactly how memory efficient this would be, you have to create 1 Integer object for each primitive int in your array, then you have to create 1 String object for each Integer object you have. So there is probably a good deal of overhead in object creation.

Answer 5

The only possible way is to implement your own Comparator where you will convert each of two comparable Integer-s to String objects and do comparison on them.

UPD: Here is an example, how to implement it:

    Integer[] input = {2,3,5,7,11,13,17,19};

    Arrays.sort(input, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.toString().compareTo(o2.toString());
        }
    });