every time I run this program I get a segmentation fault error and I can't figure out why. The function is to sort an array and this code does that but every time I try to run it I get an error that says segmentation fault core dumped.

#include <iostream>

void counting_sort(int *array, unsigned array_len) {
  int output[array_len];
  int max;
  for (int i = 0; i < array_len; i  ) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  int count[max   1];
  for (int i = 1; i <= max; i  ) {
    count[i] = 0;
  }
  for (int i = 0; i < array_len; i  ) {
    count[array[i]]  ;
  }
  for (int i = 1; i <= max; i  ) {
    count[i]  = count[i - 1];
  }
  for (int i = array_len - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }
  for (int i = 0; i < array_len; i  ) {
    array[i] = output[i];
  }
  std::cout << array[1];
}

} // namespace cs19
int main() {
  int num = 3;
  int arr[num];
  arr[0] = 4;
  arr[1] = 2;
  arr[2] = 7;
  counting_sort(arr, num);
  return 0;
}

Can anybody tell me why this is happening and how to fix it? I am somewhat new to coding so I am struggling to figure out what is causing this.

CodePudding user response：

According to the C Standard the size of a C array must be compile time constant.

So you cannot have

int num = 5;
int MyArray[num]; // incorrect

The correct way to do this is:

const int num = 5;
int MyArray[num]; // correct

This is only one of the problem in your example code. You have done this twice in the code. First for the array named arr inside main and then for the array named output inside the called function. Similarly for the array named count.

The problem is that you have max as a built-in local variable and you haven't initialized it explicitly. So it will have a garbage value.

You can use std::vector for the purpose where the size is determined at runtime. The below working example shows your implementation using std::vector instead of built in array.

#include <iostream>
#include <vector>
void counting_sort(std::vector<int> &vec) {
    std::vector<int> output(vec.size());
    int max = 0;
    for (int i = 0; i < vec.size(); i  ) {
        if (vec[i] > max) {
            max = vec[i];
        }
    }
    std::vector<int> count(max  1);
    for (int i = 1; i <= max; i  ) {
        count[i] = 0;
    }
    for (int i = 0; i < vec.size(); i  ) {
        count[vec[i]]  ;
    }
    for (int i = 1; i <= max; i  ) {
        count[i]  = count[i - 1];
    }
    for (int i = vec.size() - 1; i >= 0; i--) {
        output[count[vec[i]] - 1] = vec[i];
        count[vec[i]]--;
    }
    for (int i = 0; i < vec.size(); i  ) {
        vec[i] = output[i];
    }
    //std::cout << vec[1];
}


int main() {
    int num = 3;
    std::vector<int> myvec(num);
    myvec[0] = 4;
    myvec[1] = 2;
    myvec[2] = 7;
    
    std::cout<<"before sorting: "<<std::endl;
    for(const int &i: myvec)
    {
        std::cout<<i<<std::endl;
    }
    //sort the vector by calling the counting_sort function
    counting_sort(myvec);
    
    std::cout<<"after sorting: "<<std::endl;
    for(const int &i: myvec)
    {
        std::cout<<i<<std::endl;
    }
    return 0;
}

CodePudding user response：

max variable is not initialized. Initialize it to 0 and should work as expected. This works different in release and no-opt (debug) mode.

change

int max;

to

int max=0;

If max variable is not initialized, value will be undefined. That means count array will be created with 2342525 or some similar range and cause problems.