Sorting digits of an integer

Question

You are given an integer 51234 (say) we need to sort the digits of a number the output will be 12345.

How to do it without using array ?

Answer 1

Divide by 10 given integer in loop. Print the reminder in each iteration.

Or "sort" means what here? For real sorting you will need two loops. One of them will be from 0 to 9. Another one will be that was described early.

int main()
{
    int x = 0;
    cin >> x;

    for ( int l = 0; l < 10; ++l )
    {
        int rem = x % 10;
        int tx = x / 10;
        while ( rem || tx )
        {
            if ( rem == l ) cout << rem;
            rem = tx % 10;
            tx = tx / 10;
        }
    }
    cout << endl;
}

Answer 2

You can use a loop and % 10 to extract each digit. An outer loop from 0 to 9 could be used to test if the digit exists. If it exists, print it.

In pseudo code:

n = integer // 51234
FOR digit = 0 TO 9
  temp = n
  REPEAT
    IF temp % 10 = digit THEN PRINT digit
    temp /= 10
  UNTIL temp = 0

Edit: This test in gcc shows that it handles zeros and repeated digits:

$ cat sortdigits.c
#include <stdio.h>
main () {
 int n,digit,temp;
 n = 43042025;
 for (digit=0;digit<9;digit++)
   for (temp=n;temp>0;temp/=10)
     if (temp%10==digit) printf("%d",digit);
 printf("\n");
}
$ ./sortdigits
00223445

Answer 3

General overview:

• loop for i = 0 to 9
• in each loop iteration, walk through the digits in the number (using another loop that does a "mod 10" operation to peel off the digits until the number reduces to zero) - if it matches the digit you're currently working on, print it

The only potentially tricky bit might be properly handling zeros - you don't want too many, and you'll want to handle the edge case where the input is zero properly.

Actual implementation is left as an exercise...

Answer 4

Easy:

#include <stdio.h>
#include <stdlib.h>

static void pput(int n, int c)
{
    int i;
    for (i=0; i < n; ++i) putchar(c);
}

int main(int argc, char *argv[])
{
    int zeros = 0;
    int ones = 0;
    int twos = 0;
    int threes = 0;
    int fours = 0;
    int fives = 0;
    int sixes = 0;
    int sevens = 0;
    int eights = 0;
    int nines = 0;
    long num = 0;

    if (argc > 1) {
        char *eptr;
        num = strtol(argv[1], &eptr, 0);
        if (*eptr) {
            fprintf(stderr, "Invalid number: '%s', using 0.\n", argv[1]);
            num = 0;
        }
    }
    do {
        switch (num % 10) {
            case 0: ++zeros;
                    break;
            case 1: ++ones;
                    break;
            case 2: ++twos;
                    break;
            case 3: ++threes;
                    break;
            case 4: ++fours;
                    break;
            case 5: ++fives;
                    break;
            case 6: ++sixes;
                    break;
            case 7: ++sevens;
                    break;
            case 8: ++eights;
                    break;
            case 9: ++nines;
                    break;
            default:
                    break;
        }
    } while ((num /= 10));
    pput(zeros, '0');
    pput(ones, '1');
    pput(twos, '2');
    pput(threes, '3');
    pput(fours, '4');
    pput(fives, '5');
    pput(sixes, '6');
    pput(sevens, '7');
    pput(eights, '8');
    pput(nines, '9');
    putchar('\n');
    return 0;
}

Compiling and running:

$ gcc -Wextra -Wall -ansi -pedantic -Wfloat-equal -Wundef -Wshadow \
  -Wpointer-arith -Wcast-qual -Wcast-align -Wstrict-prototypes \
  -Wswitch-default -Wswitch-enum -Wstrict-overflow=5 \
  -Wdeclaration-after-statement -Wwrite-strings -Wconversion \
  -Waggregate-return -Wunreachable-code a.c
$ ./a.out
0
$ ./a.out 54321
12345
$ ./a.out 9834346
3344689
$ ./a.out hello
Invalid number: 'hello', using 0.
0

:-)

Another solution, not using arrays, and pretty short on line-count:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

int main(int argc, char *argv[])
{
    long num = 0;
    int i;
    size_t *freq;

    if (argc > 1) {
        char *eptr;
        num = strtol(argv[1], &eptr, 0);
        if (*eptr || errno == ERANGE) {
            fprintf(stderr, "Invalid number: '%s', using 0.\n", argv[1]);
            num = 0;
        }
    }

    if ((freq = calloc(10, sizeof *freq)) == NULL) {
        perror("malloc failure");
        return EXIT_FAILURE;
    }

    do
        ++freq[num % 10];
    while ((num /= 10));

    for (i=0; i < 10; ++i) {
        size_t j;
        for (j=0; j < freq[i]; ++j)
            putchar(i + '0');
    }
    putchar('\n');
    free(freq);

    return EXIT_SUCCESS;
}

Yes, I am aware of the "correct" solution. But why would one not use arrays for this problem? As one of the commentators said, I wouldn't want to work for a company that wouldn't let me use arrays in C.

Answer 5

// Bubblesort
long sortNum(long n) {
  while (true) {
    long a = n % 10, p = 9;
    bool s = false;
    for (long r = n / 10; r; r/= 10) {
      long b = r % 10;
      if (a < b) {
        n -= p * (b - a);
        s = true;
      } else a = b;
      p *= 10;
    }
    if (!s) return n;
  }
}

#include <iostream>

int main(int argc, char **argv) {
  if (argc > 1) {
    long n = strtol(argv[1], 0, 0);
    std::cout << "Unsorted: " << n << std::endl;
    n = sortNum(n);
    std::cout << "Sorted:   " << n << std::endl;
  }
  return 0;
}

$ g++ -Wall -Wextra bubble-int.cpp && ./a.exe 183974425
Unsorted: 183974425
Sorted:   123445789

Answer 6

One could try something like an insertion sort. Essentially create a new number from taking one digit of the old one at a time and putting it in the correct place.something like this.

while(num!=0){

dig = num%10; // get the last digit 
if(newNum=0 ) newNum+=dig;
else{
    newNumTemp = 0; flag =1;i =1;
    while (newNum != 0){
    Newdig = newNum%10;
   if(flag){
      if (Newdig >= dig )
         {NewNumTemp = Newdig*(10^i)+ NewNumTemp; }
      else { flag=0; NewNumTemp = dig*(10^i) +NewNumTemp; i++;NewNumTemp = Newdig*   (10^i)+    NewNumTemp;}

     } // end of outer if 
     i++;
     newNum/=10;

   } // end of while
   newNum= newNumTemp;
}// end of else 

num/=10;

}// end of outer while

Answer 7

You don't need to write a program at all, just do it with shell commands:

echo "51234" | sed 's+\(.\)+\1\n+g' | sort | tr -d '\n'

Answer 8

Create a container interface over the int (something like vector), where operator references the i'th decimal digit. You would have to define iterators and other things too. Then call std::sort on it. ;)

Answer 9

Sure arrays are out, but we've got a better container anyway:

void foo(unsigned i) {
  std::set<char> digits;
  do {
    digits.insert(`0` + i % 10);
    i /= 10;
  while(i!=0);
}

Use multiset if your input includes numbers like 887 that should be printed as 788