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