klayveR - 1 year ago 75

Java Question

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`

Answer Source

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:

- you take the current digit of the number you want to sort(let's call it N)
- you go through all digits in already sorted number(let's call it S)
- 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.