C Sorting Algorithm Returns in the Quintillions When Given 0-CodePudding

I'm trying to write my first sorting algorithm in C , I'm relatively new to it so this might be an endeavor beyond me but I thought I could handle it. When given the input 0 this code returns numbers such as 701635989630, 6560204700, and 1.8*10^19. This doesn't make sense to me at all, nor the people I have asked IRL.

Edit - @Slava had the best suggestion and with his help I was able to get it to work 4 out of 5 times now, but it still fails on the 5th

#include <cinttypes>

uint64_t descendingOrder(uint64_t a)
{
  std::vector<int> digits;
  for( auto tmp = a; tmp; tmp /= 10 ){
    digits.push_back( tmp % 10 );
  }
  
  bool run = true;
  
  //sort the array
  while (run) {
    bool change = false;
    for (unsigned long z = 1; z < std::size(digits);   z){
      if (digits[z]>digits[z-1]){
        unsigned long temp = digits[z];
        digits[z] = digits[z-1];
        digits[z-1] = temp;
        change = true;
      };
    };
    if (change == false){
      run = false;
    };
  };
  
  int finSort = 0;
  for (unsigned long i = 0; i < std::size(digits); i  ) {
    finSort *= 10;
    finSort  = digits[i];
  }

  return finSort;
}

CodePudding user response：

int arrayLength = sizeof(array); is not what you think. It does not return the size of array, but rather how much bytes that array comsume.

Also, int array[n] is not valid C , because arrays' sizes in C has to be known in compile time. If you want to create an array which sizes are known at runtime, consider using std::vector. You just need to change int array[n] to:

std::vector<int> array;
array.resize(n);

CodePudding user response：

I'd make the following two changes to the code:

int array[20]; // a 64 bit integer won't have more than 20 digits
int arrayLength = n; // we just calculated this

CodePudding user response：

If you use proper tool - std::vector in this case, your code would be simplified and easier to write and read, as std::vector can grow dynamically:

uint64_t descendingOrder(uint64_t a)
{
     std::vector<int> digits;
     for( auto tmp = a; tmp; tmp /= 10 )
          digits.push_back( tmp % 10 );
     // your sorting code is here
}

Now you have your number digits in vector digits, your array size in digits.size() and you do not need 2 loops. Though digits in vector would be in reverse order but it does not matter in your case as you need to sort it.

CodePudding user response：

There are two mistakes that i can spot just by first looking at your code snippet:

Mistake 1

In C , the size of an array must be a compile time constant. So you cannot write code like:

int n = 10;
int arr[n];    //incorrect

Correct way to write this would be:

const int n = 10;
int arr[n];    //correct

For the same reason the following code is incorrect in your code as well:

int array[n]; //incorrect because n is not a constant expression

Mistake 2

You're calculating the size of the array incorrectly. The correct would be to use std::size with C 17 or use the formula

int arrayLength = sizeof(array)/sizeof(int);//will work with all C   versions

or with C 17:

int arrayLength = std::size(array); //works in C  17 and higher

You can/should instead use a variable size container like std::vector.

CodePudding user response：

C Sorting Algorithm Returns in the Quintillions When Given 0

Sorting algorithms sort things. They don't, as a rule, return integers.

uint64_t descendingOrder(uint64_t a)

This is a function that does three things:

convert an integer into an array of digits
sort the array of digits
convert the sorted array of digits back into an integer

That's two things too many, and only one of them is really relevant to the question. It's clearly not a minimal reproducible example because the bug is in your sorting code, not in your integer-digit-array-conversion code.

Let's rewrite the function so it isn't trying to do too many things:

uint64_t descendingOrder(uint64_t a)
{
    auto digits = integer_to_digits(a);
    bubble_sort(digits);
    return digits_to_integer(digits);
}

You already have working code for integer_to_digits and digits_to_integer so I'm not going to write them out - and anyway, they don't belong in your question in the first place.

Now, we can write the minimal code needed to demonstrate the problem, starting with your existing sorting code:

void bubble_sort(std::vector<int> &digits)
{
  bool run = true;
  
  while (run) {
    bool change = false;
    for (unsigned long z = 1; z < digits.size();   z){
      if (digits[z]>digits[z-1]){
        unsigned long temp = digits[z];
        digits[z] = digits[z-1];
        digits[z-1] = temp;
        change = true;
      }
    }
    if (change == false){
      run = false;
    }
  }
}

and a trivial test harness so we can see it working:

void test_bubble_sort(std::vector<int> &digits)
{
    std::cout << "{";
    std::copy(digits.begin(), digits.end(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << "} -> {";
    bubble_sort(digits);
    std::copy(digits.begin(), digits.end(), std::ostream_iterator<int>(std::cout, ","));
    std::cout << "}\n";
}

int main() {
    std::vector<int> empty;
    test_bubble_sort(empty);
    
    std::vector<int> zero{0};
    test_bubble_sort(zero);
    
    std::vector<int> one{1};
    test_bubble_sort(one);
    
    std::vector<int> inc{1, 2, 3};
    test_bubble_sort(inc);
    
    std::vector<int> dec{3, 2, 1};
    test_bubble_sort(dec);
}

... and the sort itself seems to be fine.

If you have a problem in reality with the integer_to_digits or digits_to_integer, write another test for those, and if necessary ask a question specific to them. Neither the test harness nor the question will have any bubble sorting in them, because these problems are completely unrelated.

When you have a working, tested bubble sort and working, tested integer-digit-array conversion, then you can combine them into a program that does two things.