Sorting an array of int in lexicographic order

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

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));
}

Leave a Reply

Your email address will not be published. Required fields are marked *