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

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 class; it's a custom class our professor gave us.

Solution 1

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.

Solution 2

It's 4 lines, based on a for loop variant of your while loop with a little java 8 spice:

int number = 4214;

List<Integer> numbers = new LinkedList<>(); // a LinkedList is not backed by an array
for (int i = number; i > 0; i /= 10)
    numbers.add(i % 10);
numbers.stream().sorted().forEach(System.out::println); // or for you forEach(IO::println)

Solution 3

My algorithm of doing it:

int ascending(int a)
{
    int b = a;
    int i = 1;
    int length = (int)Math.log10(a) + 1;   // getting the number of digits
    for (int j = 0; j < length - 1; j++)
    {
        b = a;
        i = 1;
        while (b > 9)
        { 
            int s = b % 10;                // getting the last digit
            int r = (b % 100) / 10;        // getting the second last digit
            if (s < r)
            {
                a = a + s * i * 10 - s * i - r * i * 10 + r * i; // switching the digits
            }
            b = a;
            i = i * 10;
            b = b / i;                     // removing the last digit from the number
        }
    }
    return a;
}

Solution 4

I assume you're allowed to use hashing.

public static void sortDigits(int x) {
    Map<Integer, Integer> digitCounts = new HashMap<>();

    while (x > 0) {
        int digit = x % 10;
        Integer currentCount = digitCounts.get(digit);
        if (currentCount == null) {
            currentCount = 0;
        }
        digitCounts.put(x % 10, currentCount + 1);
        x = x / 10;
    }

    for (int i = 0; i < 10; i++) {
        Integer count = digitCounts.get(i);
        if (count == null) {
            continue;
        }
        for (int j = 0; j < digitCounts.get(i); j++) {
            System.out.print(i);
        }
    }
}

Solution 5

How to sort a number without use of array, string or sorting api? Well, you can sort a number with following simple steps (if too much to read then see the debugging output below to get an idea of how the sorting is done):

1. Get the last digit of the number using (digit = number % 10)
2. Divide number so last digit is gone (number /= 10)
3. Loop through digits of number (that does not have digit) and check if digit is smallest
4. If new smaller digit found then replace the digit = smallest digit and keep looking until end
5. At the end of the loop you have found the smallest digit, store it (store = (store * 10) + digit
6. Now that you know this is smallest digit, remove this digit from number and keep applying the above steps to remainder number and every time a smaller digit is found then add it to the store and remove digit from number (if digit is repeated in number, then remove them all and add them to store)

I provided a code with two while loops in the main method and one function. The function does nothing but, builds a new integer excluding the digit that is passed to for example I pass the function 451567 and 1 and the function returns me 45567 (in any order, doesn't matter). If this function is passed 451567 and 5 then, it finds both 5 digits in number and add them to store and return number without 5 digits (this avoid extra processing).

Debugging, to know how it sorts the integer:

Last digit is : 7 of number : 451567
Subchunk is 45156
Subchunk is 4515
Subchunk is 451
Subchunk is 45
Subchunk is 4
Smalled digit in 451567 is 1
Store is : 1
Remove 1 from 451567
Reduced number is : 76554
Last digit is : 4 of number : 76554
Subchunk is 7655
Subchunk is 765
Subchunk is 76
Subchunk is 7
Smalled digit in 76554 is 4
Store is : 14
Remove 4 from 76554
Reduced number is : 5567
Last digit is : 7 of number : 5567
Subchunk is 556
Subchunk is 55
Subchunk is 5
Smalled digit in 5567 is 5
Store is : 145
Remove 5 from 5567
Repeated min digit 5 found. Store is : 145
Repeated min digit 5 added to store. Updated store is : 1455
Reduced number is : 76
Last digit is : 6 of number : 76
Subchunk is 7
Smalled digit in 76 is 6
Store is : 14556
Remove 6 from 76
Reduced number is : 7
Last digit is : 7 of number : 7
Smalled digit in 7 is 7
Store is : 145567
Remove 7 from 7
Reduced number is : 0
Ascending order of 451567 is 145567

The sample code is as follow:

//stores our sorted number
     static int store = 0; 

     public static void main(String []args){
        int number = 451567; 
        int original = number; 

        while (number > 0) {
            //digit by digit - get last most digit
            int digit = number % 10;

            System.out.println("Last digit is : " + digit + " of number : " + number); 

            //get the whole number minus the last most digit 
            int temp = number / 10; 

            //loop through number minus the last digit to compare
            while(temp > 0) {
                System.out.println("Subchunk is " + temp); 
                //get the last digit of this sub-number
                int t = temp % 10; 

                //compare and find the lowest
                //for sorting descending change condition to t > digit
                if(t < digit)   
                    digit = t; 

                //divide the number and keep loop until the smallest is found
                temp = temp / 10;
            }
            System.out.println("Smalled digit in " + number  + " is " + digit); 

            //add the smallest digit to store 
            store = (store * 10) + digit; 

            System.out.println("Store is : " + store); 

            //we found the smallest digit, we will remove that from number and find the 
            //next smallest digit and keep doing this until we find all the smallest 
            //digit in sub chunks of number, and keep adding the smallest digits to 
            //store
            number = getReducedNumber(number, digit); 
        }
        System.out.println("Ascending order of " + original + " is " + store); 
     }


     /*
     * A simple method that constructs a new number, excluding the digit that was found
     * to b e smallest and added to the store. The new number gets returned so that 
     * smallest digit in the returned new number be found.
     */
     public static int getReducedNumber(int number, int digit) {
        System.out.println("Remove " + digit + " from " + number); 
        int newNumber = 0; 

        //flag to make sure we do not exclude repeated digits, in case there is 44
        boolean repeatFlag = false; 
        while(number > 0) {
            int t = number % 10; 
            //assume in loop one we found 1 as smallest, then we will not add one to the new number at all
            if(t != digit) {
                newNumber = (newNumber * 10) + t; 
            } else if(t == digit) {
                if(repeatFlag) {
                    System.out.println("Repeated min digit " + t + "found. Store is : " + store);
                    store = (store * 10) + t; 
                    System.out.println("Repeated min digit " + t + "added to store. Updated store is : " + store);
                    //we found another value that is equal to digit, add it straight to store, it is 
                    //guaranteed to be minimum
                } else {
                    //skip the digit because its added to the store, in main method, set flag so 
                    // if there is repeated digit then this method add them directly to store
                    repeatFlag = true; 
                }
            }
            number /= 10; 
        }
        System.out.println("Reduced number is : " + newNumber); 
        return newNumber; 
     }
}

View more solutions

Comments

[Aamir]

the questions says in ascending order

[Aamir]

maybe @klayveR if u want the answer in descending order then u should try this link stackoverflow.com/questions/22720895/…

[Timofey]

I edited the condition, so now it sorts in ascending. In fact, my algorithm can sort in both orders.

[Timofey]

I am really curious where's hashing in your solution?

[Timofey]

If you're using HashMap you're basically using an array, but OP wants a solution without arrays. So TreeMap solution was more right :)

[tharindu_DG]

@Timofey: Hash bucket is quite different from an array and TreeMap internally uses compareTo and it is more likely to use an array structure I think.

[Timofey]

Just looked as TreeMap sources, it uses Node objects that are linked to each other. You are right about HashMap — it uses something like "dynamic size" array. But I think this is a question to OP: is it prohibited to use java Array or Lists and Sets at all?

[Timofey]

I assumed that author meant he doesn't want to use any type of "list-like" structures. Also it's not clear what's the point of the task: if he wants to learn algorithms, then my assuming is right, because what's the point of the task when Java has implementation for sorting whole lot of lists and sets. If the point of the task is to learn Java, then restricting yourself makes no sence at all.

[Bohemian]

@tagir - claim deleted!

[Lily]

What if I need to sort in descending order?

[Pushparaj Dhole]

@Lily change this bubble sort condition as below if (arr[i] < arr[j]) { int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; }

[Tomer Shetah]

That does not answer the question. The output should be: 124679

[Admin]

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.