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.

Are you allowed to use lists? If so, you could put the digits into a list, sort it using Collections.sort(list) and print the output. — moonlight
– moonlight, Commented Nov 28, 2015 at 12:28
Sorry, this is not enough. When you post a homework question, you have to show your own attempt to solve the question, and explain what problem you have encountered. Please read the help center. — RealSkeptic
– RealSkeptic, Commented Nov 28, 2015 at 12:29
Sadly, I'm not allowed to use that either :/ By the way, this is not a homework. It's one of thousands of tasks our prof gave us to help understand stuff. I'm just curious. — What
– What, Commented Nov 28, 2015 at 12:30
@klayveR "A task our prof gave us to help understanding" = "Homework". Also, question asked in text books, courses, even job interviews - are all considered homework. The point is that you need to tackle the problem first. — RealSkeptic
– RealSkeptic, Commented Nov 28, 2015 at 12:39
Based on my understanding of question, the asker is after a solution purely based on character manipulation using loops. These kind of problems are given to students to improve their understanding of loops and related topics. For example my first C programming assignment was to evaluate x rise to power of n using only addition (+) operation. We were not allowed to use multiplication or division or any built-in functions. I guess I am with @Timofey on this, a solution that does not use arrays, or collections, or recursion or any other built-in support. — Raf
– Raf, Commented Nov 28, 2015 at 20:04

Bohemian · Accepted Answer · 2015-11-28 18:04:08Z

9

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)

edited Nov 28, 2015 at 18:04

answered Nov 28, 2015 at 14:57

Bohemian♦

427k103 gold badges604 silver badges750 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Timofey Over a year ago

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 Over a year ago

@tagir - claim deleted!

Community · Accepted Answer · 2017-05-23 11:47:19Z

8

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.

edited May 23, 2017 at 11:47

CommunityBot

11 silver badge

answered Nov 28, 2015 at 12:57

Timofey

8391 gold badge8 silver badges26 bronze badges

3 Comments

Aamir Over a year ago

the questions says in ascending order

Aamir Over a year ago

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

Timofey Over a year ago

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

tharindu_DG · Accepted Answer · 2015-11-28 13:49:42Z

3

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

edited Nov 28, 2015 at 13:49

answered Nov 28, 2015 at 13:26

tharindu_DG

9,2997 gold badges55 silver badges69 bronze badges

4 Comments

Timofey Over a year ago

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

Timofey Over a year ago

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 Over a year ago

@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 Over a year ago

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?

Raf · Accepted Answer · 2015-11-28 15:01:18Z

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):

Get the last digit of the number using (digit = number % 10)
Divide number so last digit is gone (number /= 10)
Loop through digits of number (that does not have digit) and check if digit is smallest
If new smaller digit found then replace the digit = smallest digit and keep looking until end
At the end of the loop you have found the smallest digit, store it (store = (store * 10) + digit
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; 
     }
}

Abbas · Accepted Answer · 2016-10-29 14:35:01Z

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

edited Oct 29, 2016 at 14:35

answered Oct 25, 2016 at 13:33

Abbas

313 bronze badges

Comments

Pushparaj Dhole · Accepted Answer · 2017-01-30 08:41:23Z

1

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

answered Jan 30, 2017 at 8:41

Pushparaj Dhole

632 silver badges13 bronze badges

2 Comments

Lily Over a year ago

What if I need to sort in descending order?

Pushparaj Dhole Over a year ago

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

Stephen Rauch · Accepted Answer · 2018-09-16 05:30:57Z

1

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

edited Sep 16, 2018 at 5:30

Stephen Rauch♦

50.1k32 gold badges118 silver badges143 bronze badges

answered Sep 16, 2018 at 4:56

Arun Singh

111 bronze badge

Comments

Raimund Krämer · Accepted Answer · 2020-09-24 07:38:08Z

1

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

Print a 0 for every 0 in the number.
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;
        }
    }

edited Sep 24, 2020 at 7:38

answered Nov 14, 2017 at 10:19

Raimund Krämer

1,3101 gold badge12 silver badges30 bronze badges

Comments

Tomer Shetah · Accepted Answer · 2021-01-26 09:57:05Z

0

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

edited Jan 26, 2021 at 9:57

Tomer Shetah

8,5797 gold badges31 silver badges40 bronze badges

answered Jan 26, 2021 at 9:33

yash sawant

1

1 Comment

Tomer Shetah Over a year ago

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

Dharman · Accepted Answer · 2021-06-25 05:04:43Z

0

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

edited Jun 25, 2021 at 5:04

Dharman♦

34k27 gold badges106 silver badges158 bronze badges

answered Jun 25, 2021 at 4:59

Apoorv Singh

1

Comments

StackpackedKar · Accepted Answer · 2021-12-13 06:03:11Z

0

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

answered Dec 13, 2021 at 6:03

StackpackedKar

1012 bronze badges

1 Comment

Community Over a year ago

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.

Christophe Bédanne · Accepted Answer · 2022-05-19 20:51:05Z

0

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

edited May 19, 2022 at 20:51

answered May 19, 2022 at 20:47

Christophe Bédanne

11 bronze badge

Comments

kpgan8204 · Accepted Answer · 2022-09-19 16:26:54Z

0

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

}

edited Sep 19, 2022 at 16:26

answered Sep 14, 2022 at 2:43

kpgan8204

3112 silver badges4 bronze badges

1 Comment

Community Over a year ago

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.

Collectives™ on Stack Overflow

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

13 Answers 13

2 Comments

3 Comments

4 Comments

Comments

Comments

2 Comments

Comments

Comments

1 Comment

Comments

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

13 Answers 13

2 Comments

3 Comments

4 Comments

Comments

Comments

2 Comments

Comments

Comments

1 Comment

Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related