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.

Answer 1

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)

Answer 2

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.

Answer 3

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

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

Answer 5

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

Answer 6

Here is the simple solution :

    public class SortDigits
    {
        public static void main(String[] args)
        {
            sortDigits(3413657);
        }

        public static void sortDigits(int num)
        {
            System.out.println("Number  : " + num);
            String number = Integer.toString(num);
            int len = number.length(); // get length of the number
            int[] digits = new int[len];
            int i = 0;
            while (num != 0)
            {
                int digit = num % 10;
                digits[i++] = digit; // get all the digits
                num = num / 10;
            }
            System.out.println("Digit before sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
            sort(digits);
            System.out.println("\nDigit After sorting: ");
            for (int j : digits)
            {
                System.out.print(j + ",");
            }
        }
        //simple bubble sort 
        public static void sort(int[] arr)
        {
            for (int i = 0; i < arr.length - 1; i++)
                for (int j = i + 1; j < arr.length; j++)
                {
                    if (arr[i] > arr[j])
                    {
                        int tmp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = tmp;
                    }
                }
        }
    }

Answer 7

Since the possible elements (i. e. digits) in a number are known (0 to 9) and few (10 in total), you can do this:

1. Print a 0 for every 0 in the number.
   
2. Print a 1 for every 1 in the number.
   

    int number = 451467;

    // the possible elements are known, 0 to 9
    for (int i = 0; i <= 9; i++) {
        int tempNumber = number;

        while (tempNumber > 0) {
            int digit = tempNumber % 10;
            if (digit == i) {
                IO.print(digit);
            }
            tempNumber = tempNumber / 10;
        }
    }

Answer 8

class SortDigits {
    public static void main(String[] args) {
        int inp=57437821;
        int len=Integer.toString(inp).length();
        int[] arr=new int[len];
        for(int i=0;i<len;i++)
        {
            arr[i]=inp%10;
            inp=inp/10;
        }
        Arrays.sort(arr);
        int num=0;
        for(int i=0;i<len;i++)
        {
            num=(num*10)+arr[i];
        }
        System.out.println(num);
    }    
}

Answer 9

Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
int length = 0;
long tem = 1;
while (tem <= n) {
    length++;
    tem *= 10;
}

int  last=0;
int [] a=new int[length];
int i=0;
StringBuffer ans=new StringBuffer(4);
while(n!=0){
    last=n%10;
    a[i]=last;               
    n=n/10;
    i++;
}

int l=a.length;
 
for(int j=0;j<l;j++){
    for(int k=j;k<l;k++){
        if(a[k]<a[j]){
            int temp=a[k];
            a[k]=a[j];
            a[j]=temp;
        }
    }
}

for (int j :a) {
   ans= ans.append(j);
}
int add=Integer.parseInt(ans.toString());

System.out.println(add);

For the input:

n=762941 ------->integer

We get output:

149267      ------->integer

Answer 10

import java.util.*;
class EZ
{
public static void main (String args [] )
{
    Scanner sc = new Scanner (System.in);
    System.out.println("Enter the number - ");
    int a=sc.nextInt();
    int b=0;
for (int i=9;i>=0;i--)
{
int c=a;
while (c>0)
{
    int d=c%10;             
    if (d==i)
    {
        b=(b*10)+d;
    }
    c/=10;                
}               
}
System.out.println(b);
}
}

Answer 11

import java.util.Scanner;
public class asc_digits
{
    public static void main(String args[]){
    Scanner in= new Scanner(System.in);
    
        System.out.println("number");
        int n=in.nextInt();
        int i, j, p, r;
        for(i=0;i<10;i++)
        {
            p=n;
            while(p!=0)
            {
                r = p%10;
                if(r==i)
                {
                    System.out.print(r);
                }
                p=p/10;
                }
            }
        }
    }

Answer 12

Stream can also be used for this :

public static int sortDesc(final int num) {
    List<Integer> collect = Arrays.stream(valueOf(num).chars()
       .map(Character::getNumericValue).toArray()).boxed()
       .sorted(Comparator.reverseOrder()).collect(Collectors.toList());

    return Integer.valueOf(collect.stream()
        .map(i->Integer.toString(i)).collect(Collectors.joining()));
    
}

Answer 13

class HelloWorld {

public static void main(String[] args) {
   Scanner sc=new Scanner(System.in);
   int num=sc.nextInt();
   
   System.out.println(" rever number is= "+reversernum(num));
   
    System.out.println("\n sorted number is= "+sortedNumdesc(num));
}

 private static int reversernum(int n1)
{
    if(n1<10)
     return n1;
   
    int n_reverse=0;
    int lastDigit=0;
    while(n1>=1)
    {
        lastDigit=n1%10;
        n_reverse=n_reverse*10+lastDigit;
       // System.out.println(" n_reverse "+n_reverse);
        n1=n1/10;
    }

     return n_reverse;
}

 private static int sortedNumdesc(int num)
{
    if(num<10)
     return num;
   
  List<Integer> numbers = new LinkedList<>();
  
  for (int i=num ;i>0;i/=10)
      numbers.add(i%10);
    
 // numbers.stream().sorted().forEach(System.out:: println);
     int  sorted_Num=0;
   List<Integer> sortednum=  numbers.stream().sorted()
   .collect(Collectors.toList());
 
  // System.out.println("sorted list "+sortednum);
   for(Integer x: sortednum)
        sorted_Num=sorted_Num*10+x;
   

    return sorted_Num;
}

}