开发者

Sorting digits of an integer

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 ?


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


// 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


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'


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...


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.


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


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


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


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜