how can I sorting a number without using array?

Question

How can I find the maximum and the minimum number that can be formed using digits of a given number (for example 485735) without using any array at all ?

I was looking at the algorithm of bubble sort (that using array) and I tried to figure out how to write an algorithm without the array but my problem was to counting the indexes of every digit

The only thing that cross my mind was an algorithm to count the number of digits in the input (friend helped me with that) , but so far I'm tried to figure this thing out for a 4 days that's a question with a grade from my homework

the rule is that the smallest number can't start in a zero for example:

Input: 3134059 
The largest number is: 9543310
The smallest number is: 1033459

because we didn't learn about arrays in the Course yet so we are not allowed using that — DanielRiks, Apr 03 '19 at 23:03
@shmosel That won't work if there are 2 or more zeroes in the value. --- Also, I believe that using `Stream::sorted()`, to internally build a list and sort it, is violating the spirit of the "no array" restriction, so I'd have marked it failed, if I was the teacher grading that answer. — Andreas, Apr 03 '19 at 23:03
@shmosel I would say yes, and it can be done using pure integer math operations, i.e. without using strings, arrays, lists, streams, etc. See [my answer](https://stackoverflow.com/a/55505848/5221149) for logic. Actual coding is left to the reader. — Andreas, Apr 03 '19 at 23:46
@Andreas the code is using methods right? Sorry I didn't mention it but we didn't learn methods yet , only a loops,operators and conditions. do you have any advice for me how to Translate the methods only to loops,operators and conditions ? — DanielRiks, Apr 04 '19 at 01:06
1 way is simply using recursion and stringbuilder to build different permutations and see each time if existing greatestFound is smaller then current permutation if so reassign greatestFound variable. — nits.kk, Apr 04 '19 at 04:27

Andreas · Answer 1 · 2019-04-04T00:22:15.953

TL;DR: See demo of below logic at IDEONE.

Pretend the number is an array of digits, e.g. named d[], and pretend that index 0 is the rightmost digit.

A bubblesort will move higher values to higher indexes, so if we keep that logic, sorting d would result in the desired largestNumber, e.g. 1357924 becomes 9754321.

Assume you have a method pow10(n) which calculates 10ⁿ, you can then get digit at any index:

d[i] = number / pow10(i) % 10

Example:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924

d[4] = 1357924 / pow10(4) % 10
     = 1357924 / 10000 % 10
     = 135 % 10
     =   5

In a bubblesort, you swap adjacent elements if lower-indexed element is larger, so first we need the two values. Let's say we're doing it for i = 3:

         6 4 2 0  index
         ↓ ↓ ↓ ↓
number = 1357924
i = 3

a = d[i] = d[3] = 7
b = d[i+1] = d[4] = 5

Since a > b we need to swap the values. We can do that as follows:

 1357924
-   7000   Clear digit at i=3
-  50000   Clear digit at i=4
=1300924   Value with digits cleared
+  70000   Set digit at i=4
+   5000   Set digit at i=3
=1375924   Value with digits at index 3 and 4 swapped

The formula for that is:

number = number - a * pow10(i) - b * pow10(i+1)
                + a * pow10(i+1) + b * pow10(i)

Which can be refactored to:

number += ((a - b) * 10 - (a - b)) * pow10(i)

Now that you know how to get the "array element value", aka d[i], and how to "swap array elements" using the above formula, you write that into a normal bubblesort algorithm, so you can:

largestNumber = sortDigits(number)

You've now calculated the largest value. To calculate the smallest value, you need to simply reverse the digits, but before you do that, you need to ensure that d[0] != 0:

n = largestNumber, i = 0
while (n % 10 == 0) { // locate least non-zero digit
    n /= 10
    i++
}
if (i != 0) {
    // clear least digit and add at index 0
    n = n / 10 * pow10(i + 1) + n % 10
}

Example:

n = 97500
After loop: n = 975, i = 2
n / 10 = 97
            * pow10(i + 1) = 97000
                                   + n % 10 = 97005

Now you can calculate the other value you need:

smallestNumber = reverse(n)

See e.g. Java reverse an int value without using array for how to do that.

score 0 · Accepted Answer · edited Apr 03 '19 at 23:54

public static void main(String[] args) {

    StringBuilder s = new StringBuilder("4857035");
    char aux;

    for (int i = 0; i < s.length() - 1; i++) {
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) > (s.charAt(j))) {
                aux = s.charAt(i);
                s.setCharAt(i, s.charAt(j));
                s.setCharAt(j, aux);
            }
        }
    }
    //output 0345578

    while (s.charAt(0) == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                aux = s.charAt(0);
                s.setCharAt(0, s.charAt(i));
                s.setCharAt(i, aux);
                break;
            }
        }
    }
    //output 3045578
}

This is for the smallest number, for the greatest number change the sign on if statement ( if (s.charAt(i) < (s.charAt(j))) and delete the while statement.

Since `StringBuilder` internally uses a `char[]`, I'd say that this violates the spirit of the "no array" restriction, so I'd have marked it failed, if I was the teacher grading that answer. — Andreas, Apr 03 '19 at 23:47

how can I sorting a number without using array?

2 Answers2