dimanche 4 juillet 2021

Segmentation Fault: Radix Sort problem with vector

I am trying to build a RadixSort program, but I've got stuck in segmentation fault. I think the problem is stackoverflow or 2d vector that I used. Can anyone help me pls :(((((((. Here are my script:

  • I tried to delete the vector after call append_to_the vector() by function empty_swap(). But I still got segmentation fault.
  • RadixSort() is the function to recurse after I have rearranged the elements according to the positions of the digits.
  • append_to_the_vector() is a function to rearrange the elements in an array starting from the units digit and then moving forward.
  • exp is the variation that represents the digit that the program is processing (Example: abc: exp=10 -> c, exp=100 -> b, exp=1000 -> a).
  • max is number of times to be recursive, corresponding to the number of digits of the element with the largest number of digits.
#include<iostream>
#include<vector>
using namespace std;
void RadixSort(long long a[], long long n);
void append_to_the_vector(long long a[],long long n,long long exp, int& max);
void empty_swap(std::vector<long long>& vec) {
   std::vector<long long>().swap(vec);
}
int main (){
    long long n;
    cin>>n;
    long long a[n+1];
    for (int i=0;i<n;i++) cin>>a[i];
    RadixSort(a,n);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    return 0;
}
void RadixSort(long long a[], long long n){
    int max=0; 
    long long exp=10;
    while (max!=1){
        append_to_the_vector(a,n,exp,max);
        exp*=10;
    }
}
void append_to_the_vector(long long a[],long long n,long long exp, int& max){
    vector<long long> temp[11];
    long long x;
    for(long long i=0;i<n;i++){
        if (exp==10) x=a[i]%exp;
        else x=a[i]%exp-a[i]%(exp/10);
        temp[x].push_back(a[i]);
    }
    long long y=-1;
    for(long long i=0;i<10;i++){
        for(long long j=0;j<temp[i].size();j++){
            y++;
            a[y]=temp[i][j];
            if(exp==10){
                int count=1;
                for (long long k=10;;k*=10){
                    if (k>a[y]) break;
                    count++;
                }   
                if (max<count) max=count;
            }
        }
    }
    for(long long i=0;i<10;i++) empty_swap(temp[i]);
}

Aucun commentaire:

Enregistrer un commentaire