klayveR klayveR - 1 month ago 7
Java Question

How to sort Integer digits in ascending order without Strings or Arrays?

I'm trying to sort the digits of an integer of any length in ascending order without using Strings, arrays or recursion.

Example:

Input: 451467
Output: 144567


I have already figured out how to get each digit of the integer with modulus division:

int number = 4214;

while (number > 0) {
IO.println(number % 10);
number = number / 10;
}


but I don't know how to order the digits without an array.

Don't worry about the
IO
class; it's a custom class our professor gave us.

Answer

There's actually a very simple algorithm, that uses only integers:

int number = 4214173;
int sorted = 0;
int digits = 10;
int sortedDigits = 1;
boolean first = true;

while (number > 0) {
    int digit = number % 10;

    if (!first) {

        int tmp = sorted;
        int toDivide = 1;
        for (int i = 0; i < sortedDigits; i++) {
            int tmpDigit = tmp % 10;
            if (digit >= tmpDigit) {
                sorted = sorted/toDivide*toDivide*10 + digit*toDivide + sorted % toDivide;
                break;
            } else if (i == sortedDigits-1) {
                sorted = digit * digits + sorted;
            }
            tmp /= 10;
            toDivide *= 10;
        }
        digits *= 10;
        sortedDigits += 1;
    } else {
        sorted = digit;
    }

    first = false;
    number = number / 10;
}
System.out.println(sorted);

it will print out 1123447. The idea is simple:

  1. you take the current digit of the number you want to sort(let's call it N)
  2. you go through all digits in already sorted number(let's call it S)
  3. if current digit in S is less than current digit in N, you just insert the digit in the current position in S. Otherwise, you just go to the next digit in S.

That version of the algorithm can sort in both asc in desc orders, you just have to change the condition.

Also, I suggest you to take a look at so-called Radix Sort, the solution here takes some ideas from radix sort, and I think the radix sort is the general case for that solution.