I am working on this challenge:

Write a function sort in C that takes one integer (int) as argument. It should return the integer with its digits rearranged in descending order.

The algorithm must use recursion.

Example

Input: 26354

Expected output: 65432

This is what I tried:

int sort(int n){
    if(n/10 == 0)
        return n;
    if(n%10 <= sort(n/10)%10)
        return n;
    int d1=n%10*10;
    int d2=n/10%10;
    return sort(n-(n%100)+d1+d2);
}

But when I run it, it says "segmentation fault" which I guess means it's calling itself too many times or something like that.

What is my mistake and how can I fix it?

I am working on this challenge:

Write a function sort in C that takes one integer (int) as argument. It should return the integer with its digits rearranged in descending order.

The algorithm must use recursion.

Example

Input: 26354

Expected output: 65432

This is what I tried:

int sort(int n){
    if(n/10 == 0)
        return n;
    if(n%10 <= sort(n/10)%10)
        return n;
    int d1=n%10*10;
    int d2=n/10%10;
    return sort(n-(n%100)+d1+d2);
}

But when I run it, it says "segmentation fault" which I guess means it's calling itself too many times or something like that.

What is my mistake and how can I fix it?

• c
• sorting
• recursion

Share Improve this question Follow edited Mar 21 at 10:34 trincot 353k3737 gold badges273273 silver badges328328 bronze badges asked Mar 21 at 0:15 Daniel LeviDaniel Levi 4355 bronze badges 9

• 2 Don't use math for the digits. Convert number to a string. Sort the digits in the string. Print the string. – Thomas Matthews Commented Mar 21 at 0:21
• 2 When you used a debugger, which statement or line is causing the issue? What are the expected values of variables? What are the actual values of variables? – Thomas Matthews Commented Mar 21 at 0:24
• 2 Recursion doesn't seem well suited to this problem, at least using integers. Recursion usually has a reductive stage that solves a smaller problem, and a final (simplest) stage that terminates the recursion. Even using a string I can't think of a good recursive method, but it's easily solved iteratively. – pmacfarlane Commented Mar 21 at 0:29
• Get rid of the n%10 if statement. It does a recursive loop. You can always restore it later as necessary. – Thomas Matthews Commented Mar 21 at 0:36
• Segmentation fault in a recursive function like this usually means you ran out of stack space, which implies the recursion never stopped. So the problem is probably that you're not getting closer to the base case when you recurse. – Barmar Commented Mar 21 at 2:41

 |  Show 4 more comments

3 Answers 3

Sorted by: Reset to default 5

The main issue is that after the comparison with the outcome of the recursive sort call, you throw away that result from recursion:

• With the second return n; in your code you just return the original n, not taking into account the work that was done to sort all-but-the-last digits.

• With sort(n-(n%100)+d1+d2) you swapped the rightmost two digits of the original n, but that could lead to infinite recursion, overflowing the call stack. You need to perform this swap into the sorted partition that you got back from recursion.

Here is the corrected code:

int sort(int n) {
    if (n/10 == 0)
        return n;
    int sorted = sort(n/10); // Don't lose the result from the recursive call
    n = sorted * 10 + n%10; // Apply the result of the recursive call to n
    if (n%10 <= sorted%10)
        return n;
    int d1=n%10*10;
    int d2=n/10%10;
    return sort(n-(n%100)+d1+d2);
}

Note that the recursive call in the final statement could suffice to leave the digit d2 out, and append it after the call, since it is certain that d2 is the least of all digits involved.

Applying that observation and rearranging the code a bit leads to this version:

int sort(int n) {
    if (n < 10)
        return n;
    int d1 = n % 10;
    n = sort(n / 10);
    int d2 = n % 10;
    return d1 <= d2 ? n * 10 + d1 : sort(n - d2 + d1) * 10 + d2;
}

A test harness anyone's use.

#include <stdio.h>
#include <limits.h>

int sort(int n) {
   // Your code here
}

int main() {
  static const int test[] = {1, 123, 321, 1234, 4321, 0, 1010101010, INT_MAX/10};
  int n = sizeof test / sizeof test[0];
  for (int i = 0; i < n; i++) {
    printf("%d: %d\n", test[i], sort(test[i]));
  }
  return 0;

Expected output

1: 1
123: 321
321: 321
1234: 4321
4321: 4321
0: 0
1010101010: 1111100000
214748364: 876444321

@trincot has explained well why OP code was experiencing runtime failures.

There is some ambiguity in OP stated requirements, most notably there is no mention of the possibility of negative input values. This answer addresses issues of input so that sort can handle any int value it is given.

A Simple Recursive Solution

The point of using recursion to solve a problem is to make the problem easier to think about by breaking the problem into smaller pieces. Try to identify a base case for which the answer can be immediately found and returned for the input. When this input is encountered the problem is now solved. Next, try to find a way to reduce the input so that subsequent recursive calls converge on the base case. Typically this involves breaking the input into smaller parts, calling the recursive function on some or all of those parts, and combining the results to form a return value.

In the present case the goal is to sort an integer input. A simple way to think about this recursively arises by noticing that when the input is a single digit it is already sorted, so the input can simply be returned. This is the base case.

Otherwise the input contains multiple digits. The input can be broken up into a low-order digit component (which is a single digit), and a high-order digits component (which may or may not contain multiple digits). The high-order digits can be sorted and combined with the low-order digit to obtain the result.

This process of combination must combine the sorted higher-order digits with the low-order digit. If the low-order digit is smaller than the smallest high-order digit (which is now in the lowest position) the low-order digit can just be appended to the high-order digits using addition. Otherwise the smallest high-order digit is also the smallest of all digits: swap the smallest high-order digit with the low-order digit, sort the high-order digits again and combine the result using addition to obtain the final result.

It can be helpful when designing recursive functions to store the results of intermediate calculations in descriptively-named variables. This often makes the resulting code easier to read and understand than numerous chained operations on magic numbers.

int sort_1(int n) {
  int hi_digits = n / 10;
  if (hi_digits == 0) {  // base case: a single digit is already sorted
    return n;
  }

  int lo_digit = n % 10;
  int sorted_hi_digits = sort_1(hi_digits);
  int sorted_hi_lo = sorted_hi_digits % 10;  // low digit of sorted high digits
  if (sorted_hi_lo > lo_digit) {
    return 10 * hi_digits + lo_digit;
  }
  int sorted_hi_hi = sorted_hi_digits / 10;  // high digit of sorted high digits
  return 10 * sort_1(10 * sorted_hi_hi + lo_digit) + sorted_hi_lo;
}

Handling Troublesome Inputs

OP has not stipulated whether input may include negative integers, nor how negative inputs should be handled. One sensible interpretation is that an input like -1234 should sort to -4321, and -102 should sort to -210. Note that the solutions shown by @trincot don't handle negative numbers consistently, but again OP has not provided any requirements for this.

One simple solution is to check whether the input is negative in the combination step and compare the low-order digits accordingly:

int sort_2(int n) {
  int hi_digits = n / 10;
  if (hi_digits == 0) {  // base case: a single digit is already sorted
    return n;
  }

  int is_negative = n < 0;
  int lo_digit = n % 10;
  int sorted_hi_digits = sort_2(hi_digits);
  int sorted_hi_lo = sorted_hi_digits % 10;  // low digit of sorted high digits
  if ((is_negative && sorted_hi_lo < lo_digit) ||  // ordering wrt sign of `n`
      (!is_negative && sorted_hi_lo > lo_digit)) {
    return 10 * hi_digits + lo_digit;
  }
  int sorted_hi_hi = sorted_hi_digits / 10;  // high digit of sorted high digits
  return 10 * sort_2(10 * sorted_hi_hi + lo_digit) + sorted_hi_lo;
}

This provides a sensible resolution to the handling of negative numbers, but a further issue is that some int values may lead to sorted values which cannot be represented by an int. For example, a typical value for INT_MAX is 2147483647 (32 bit int); the sorted value of 8776444321 cannot be represented in a 32 bit int. OP has not stipulated a return type for sort; it would be better to return long long int so that any int value may be sorted and its value returned:

long long sort(int n) {
  int hi_digits = n / 10;
  if (hi_digits == 0) {  // base case: a single digit is already sorted
    return n;
  }

  int is_negative = n < 0;
  int lo_digit = n % 10;
  int sorted_hi_digits = sort(hi_digits);
  int sorted_hi_lo = sorted_hi_digits % 10;  // low digit of sorted high digits
  if ((is_negative && sorted_hi_lo < lo_digit) ||  // ordering wrt sign of `n`
      (!is_negative && sorted_hi_lo > lo_digit)) {
    return 10LL * hi_digits + lo_digit;
  }
  int sorted_hi_hi = sorted_hi_digits / 10;  // high digit of sorted high digits
  return 10LL * sort(10 * sorted_hi_hi + lo_digit) + sorted_hi_lo;
}

Test Program

Here is some testing code based on the test harness suggested by @chux:

#include <stdio.h>
#include <limits.h>

int main() {
  static const int test[] = {1, 123, 321, 1234, 4321, 0, 1010101010, INT_MAX/10,
      -123, -321, -1234, -4321, -102340, -43201, -1010101010};
  int n = sizeof test / sizeof test[0];

  puts("Testing sort_1:");
  for (int i = 0; i < n; i++) {
    printf("%d: %d\n", test[i], sort_1(test[i]));
  }

  puts("\nTesting sort_2:");
  for (int i = 0; i < n; i++) {
    printf("%d: %d\n", test[i], sort_2(test[i]));
  }

  puts("\nTesting sort:");
  for (int i = 0; i < n; i++) {
    printf("%d: %lld\n", test[i], sort(test[i]));
  }
  printf("%d: %lld\n", INT_MAX, sort(INT_MAX));
  printf("%d: %lld\n", INT_MIN, sort(INT_MIN));

  return 0;
}

Test program output:

Testing sort_1:
1: 1
123: 321
321: 321
1234: 4321
4321: 4321
0: 0
1010101010: 1111100000
214748364: 876444321
-123: -123
-321: -123
-1234: -1234
-4321: -1234
-102340: -1234
-43201: -1234
-1010101010: -11111

Testing sort_2:
1: 1
123: 321
321: 321
1234: 4321
4321: 4321
0: 0
1010101010: 1111100000
214748364: 876444321
-123: -321
-321: -321
-1234: -4321
-4321: -4321
-102340: -432100
-43201: -43210
-1010101010: -1111100000

Testing sort:
1: 1
123: 321
321: 321
1234: 4321
4321: 4321
0: 0
1010101010: 1111100000
214748364: 876444321
-123: -321
-321: -321
-1234: -4321
-4321: -4321
-102340: -432100
-43201: -43210
-1010101010: -1111100000
2147483647: 8776444321
-2147483648: -8876444321