C++ Sorting Algorithm Returns in the Quintillions When Given 0

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

Answer

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:

  1. convert an integer into an array of digits
  2. sort the array of digits
  3. 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.