Sorting a number's digits without using an array

Question

What I need to do for my homework is to sort the digits of a positive number from low to high.

I can use

• operators
• integers/doubles/floats/chars
• if/switch and loops

I cannot use

• char array()
• string

Answer 1

This will do it!

int number = 52146729;
int sortedNumber = 0;
for (int i = 9; i >= 0; i--)
{
    int tmpNumber = number;
    while (tmpNumber > 0)
    {
        int digit = tmpNumber % 10;             
        if (digit == i)
        {
            sortedNumber *= 10;
            sortedNumber += digit;
        }
        tmpNumber /= 10;                
    }               
}
System.out.println(sortedNumber);

This is java btw. Given the constraints this is pretty efficient, O(n).

Answer 2

Given the total lack of requirements, not sure this will help, but I would use a list and the LINQ OrderBy method if I was doing this in production code:

List<int> testList = new List<int> { 1, 5, 10, 4, 2 };
IEnumerable<int> orderedList = testList.OrderByDescending(x => x);

For sorting the digits, you have be very clear about what an "array" is. You'll need some sort of collection for this to ever work. I would use a list again:

List<int> digits = new List<int>();
int remainingNumber = 52146729;
while (remainingNumber > 0)
{
   digits.Add(remainingNumber % 10);
   remainingNumber /= 10;
}

IEnumerable<int> orderedDigits = testList.OrderByDescending(x => x);

This works because a x mod y returns the remainder of x/y. So 9 % 10 returns nine, so does 19 % 10, etc. Then you divide by 10 to get rid of one digit, and repeat until you run out. Then I use the same order function as before. This approach definitely doesn't use strings, or any explicit arrays (List is an array under the hood). Like I said, accomplishing this without any sort of collection is going to be really ugly.

Printing out that list would be easy (if you just need to print for your output):

foreach (int i in orderedDigits)
   Console.Write(i);

If you need an actual number back, thats going to be a bit harder, so I'll leave it off for now.

Answer 3

Why don't you try to use a tree?

Build a tree with two children: left and right. Left children store lower numbers and right children store higher numbers. Thus, you need to consider a Node having two possible choices. The first number would be the root of the tree. Next number can be stored in left or right.

Once the tree is full, you can access each number by using an in-order approach: 1- Read left; 2- Read parent; 3- Read rigth.

Check this out: http://en.wikipedia.org/wiki/Tree_traversal

Answer 4

Do it radix style:

int count9
int count8
int count7
int count6
int count5
int count4
int count3
int count2
int count1
int count0

// loop over the number and fill in the counts. (either with characters or by using %10)

for (int i = 0; i < count9; i++)
    print "9"

// more for loops, etc, downto 8.

Definitely not production code, but that is pretty much ruled out by the constraints of the assignment.

Hope this helps!