Make a bucket sort
up vote
0
down vote
favorite
I'm trying to make a bucket sort but my program causes segmentation fault and i can't find out why. I use two extra functions which help me sort out the buckets i am using which are a swap function that changes two elements in a vector and then a bubble sort which uses the swap function. The vector given will always have 10 numbers and be between 0 and 99.
template <class T>
void Sorts<T>::swap(std::vector<T> &v, int i, int j) {
T aux = v[i];
v[i] = v[j];
v[j] = aux;
}
template <class T>
std::vector<T> Sorts<T>::bubbleSort(const std::vector<T> &source) {
std::vector<T> v(source);
for(int i = v.size() -1; i > 0; i--){
for(int j = 0; j<i; j++){
if(v[j] > v[j+1]){
swap(v, j, j+1);
}
}
}
return v;
}
template <class T>
std::vector<T> Sorts<T>::bucketSort(const std::vector<T> &source) {
std::vector<T> v = source;
std::vector<T> b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
for(int i = 0; i < v.size()-1; i++){
if(v[i] >= 0 && v[i] <= 9){
b0.push_back(v[i]);
} else if(v[i] >= 10 && v[i] <= 19){
b1.push_back(v[i]);
} else if(v[i] >= 20 && v[i] <= 29){
b2.push_back(v[i]);
} else if(v[i] >= 30 && v[i] <= 39){
b3.push_back(v[i]);
} else if(v[i] >= 40 && v[i] <= 49){
b4.push_back(v[i]);
} else if(v[i] >= 50 && v[i] <= 59){
b5.push_back(v[i]);
} else if(v[i] >= 60 && v[i] <= 69){
b6.push_back(v[i]);
} else if(v[i] >= 70 && v[i] <= 79){
b7.push_back(v[i]);
} else if(v[i] >= 80 && v[i] <= 89){
b8.push_back(v[i]);
} else if(v[i] >= 90 && v[i] <= 99){
b9.push_back(v[i]);
}
}
if(!b0.empty()){
b0 = bubbleSort(b0);
}
if(!b1.empty()){
b1 = bubbleSort(b1);
}
if(!b2.empty()){
b2 = bubbleSort(b2);
}
if(!b3.empty()){
b3 = bubbleSort(b3);
}
if(!b4.empty()){
b4 = bubbleSort(b4);
}
if(!b5.empty()){
b5 = bubbleSort(b5);
}
if(!b6.empty()){
b6 = bubbleSort(b6);
}
if(!b7.empty()){
b7 = bubbleSort(b7);
}
if(!b8.empty()){
b8 = bubbleSort(b8);
}
if(!b9.empty()){
b9 = bubbleSort(b9);
}
v.clear();
for(int i = 0; i < b0.size()-1; i++){
v.push_back(b0[i]);
}
for(int i = 0; i < b1.size()-1; i++){
v.push_back(b1[i]);
}
for(int i = 0; i < b2.size()-1; i++){
v.push_back(b2[i]);
}
for(int i = 0; i < b3.size()-1; i++){
v.push_back(b3[i]);
}
for(int i = 0; i < b4.size()-1; i++){
v.push_back(b4[i]);
}
for(int i = 0; i < b5.size()-1; i++){
v.push_back(b5[i]);
}
for(int i = 0; i < b6.size()-1; i++){
v.push_back(b6[i]);
}
for(int i = 0; i < b7.size()-1; i++){
v.push_back(b7[i]);
}
for(int i = 0; i < b8.size()-1; i++){
v.push_back(b8[i]);
}
for(int i = 0; i < b9.size()-1; i++){
v.push_back(b9[i]);
}
return v;
}
c++ sorting bucket-sort
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
add a comment |
up vote
0
down vote
favorite
I'm trying to make a bucket sort but my program causes segmentation fault and i can't find out why. I use two extra functions which help me sort out the buckets i am using which are a swap function that changes two elements in a vector and then a bubble sort which uses the swap function. The vector given will always have 10 numbers and be between 0 and 99.
template <class T>
void Sorts<T>::swap(std::vector<T> &v, int i, int j) {
T aux = v[i];
v[i] = v[j];
v[j] = aux;
}
template <class T>
std::vector<T> Sorts<T>::bubbleSort(const std::vector<T> &source) {
std::vector<T> v(source);
for(int i = v.size() -1; i > 0; i--){
for(int j = 0; j<i; j++){
if(v[j] > v[j+1]){
swap(v, j, j+1);
}
}
}
return v;
}
template <class T>
std::vector<T> Sorts<T>::bucketSort(const std::vector<T> &source) {
std::vector<T> v = source;
std::vector<T> b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
for(int i = 0; i < v.size()-1; i++){
if(v[i] >= 0 && v[i] <= 9){
b0.push_back(v[i]);
} else if(v[i] >= 10 && v[i] <= 19){
b1.push_back(v[i]);
} else if(v[i] >= 20 && v[i] <= 29){
b2.push_back(v[i]);
} else if(v[i] >= 30 && v[i] <= 39){
b3.push_back(v[i]);
} else if(v[i] >= 40 && v[i] <= 49){
b4.push_back(v[i]);
} else if(v[i] >= 50 && v[i] <= 59){
b5.push_back(v[i]);
} else if(v[i] >= 60 && v[i] <= 69){
b6.push_back(v[i]);
} else if(v[i] >= 70 && v[i] <= 79){
b7.push_back(v[i]);
} else if(v[i] >= 80 && v[i] <= 89){
b8.push_back(v[i]);
} else if(v[i] >= 90 && v[i] <= 99){
b9.push_back(v[i]);
}
}
if(!b0.empty()){
b0 = bubbleSort(b0);
}
if(!b1.empty()){
b1 = bubbleSort(b1);
}
if(!b2.empty()){
b2 = bubbleSort(b2);
}
if(!b3.empty()){
b3 = bubbleSort(b3);
}
if(!b4.empty()){
b4 = bubbleSort(b4);
}
if(!b5.empty()){
b5 = bubbleSort(b5);
}
if(!b6.empty()){
b6 = bubbleSort(b6);
}
if(!b7.empty()){
b7 = bubbleSort(b7);
}
if(!b8.empty()){
b8 = bubbleSort(b8);
}
if(!b9.empty()){
b9 = bubbleSort(b9);
}
v.clear();
for(int i = 0; i < b0.size()-1; i++){
v.push_back(b0[i]);
}
for(int i = 0; i < b1.size()-1; i++){
v.push_back(b1[i]);
}
for(int i = 0; i < b2.size()-1; i++){
v.push_back(b2[i]);
}
for(int i = 0; i < b3.size()-1; i++){
v.push_back(b3[i]);
}
for(int i = 0; i < b4.size()-1; i++){
v.push_back(b4[i]);
}
for(int i = 0; i < b5.size()-1; i++){
v.push_back(b5[i]);
}
for(int i = 0; i < b6.size()-1; i++){
v.push_back(b6[i]);
}
for(int i = 0; i < b7.size()-1; i++){
v.push_back(b7[i]);
}
for(int i = 0; i < b8.size()-1; i++){
v.push_back(b8[i]);
}
for(int i = 0; i < b9.size()-1; i++){
v.push_back(b9[i]);
}
return v;
}
c++ sorting bucket-sort
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
Try removing the template, I doubt you need it, you just need to specialize the vector to int like sostd::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.
– Chris Mc
Nov 20 at 4:50
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.
– PaulMcKenzie
Nov 20 at 5:12
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm trying to make a bucket sort but my program causes segmentation fault and i can't find out why. I use two extra functions which help me sort out the buckets i am using which are a swap function that changes two elements in a vector and then a bubble sort which uses the swap function. The vector given will always have 10 numbers and be between 0 and 99.
template <class T>
void Sorts<T>::swap(std::vector<T> &v, int i, int j) {
T aux = v[i];
v[i] = v[j];
v[j] = aux;
}
template <class T>
std::vector<T> Sorts<T>::bubbleSort(const std::vector<T> &source) {
std::vector<T> v(source);
for(int i = v.size() -1; i > 0; i--){
for(int j = 0; j<i; j++){
if(v[j] > v[j+1]){
swap(v, j, j+1);
}
}
}
return v;
}
template <class T>
std::vector<T> Sorts<T>::bucketSort(const std::vector<T> &source) {
std::vector<T> v = source;
std::vector<T> b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
for(int i = 0; i < v.size()-1; i++){
if(v[i] >= 0 && v[i] <= 9){
b0.push_back(v[i]);
} else if(v[i] >= 10 && v[i] <= 19){
b1.push_back(v[i]);
} else if(v[i] >= 20 && v[i] <= 29){
b2.push_back(v[i]);
} else if(v[i] >= 30 && v[i] <= 39){
b3.push_back(v[i]);
} else if(v[i] >= 40 && v[i] <= 49){
b4.push_back(v[i]);
} else if(v[i] >= 50 && v[i] <= 59){
b5.push_back(v[i]);
} else if(v[i] >= 60 && v[i] <= 69){
b6.push_back(v[i]);
} else if(v[i] >= 70 && v[i] <= 79){
b7.push_back(v[i]);
} else if(v[i] >= 80 && v[i] <= 89){
b8.push_back(v[i]);
} else if(v[i] >= 90 && v[i] <= 99){
b9.push_back(v[i]);
}
}
if(!b0.empty()){
b0 = bubbleSort(b0);
}
if(!b1.empty()){
b1 = bubbleSort(b1);
}
if(!b2.empty()){
b2 = bubbleSort(b2);
}
if(!b3.empty()){
b3 = bubbleSort(b3);
}
if(!b4.empty()){
b4 = bubbleSort(b4);
}
if(!b5.empty()){
b5 = bubbleSort(b5);
}
if(!b6.empty()){
b6 = bubbleSort(b6);
}
if(!b7.empty()){
b7 = bubbleSort(b7);
}
if(!b8.empty()){
b8 = bubbleSort(b8);
}
if(!b9.empty()){
b9 = bubbleSort(b9);
}
v.clear();
for(int i = 0; i < b0.size()-1; i++){
v.push_back(b0[i]);
}
for(int i = 0; i < b1.size()-1; i++){
v.push_back(b1[i]);
}
for(int i = 0; i < b2.size()-1; i++){
v.push_back(b2[i]);
}
for(int i = 0; i < b3.size()-1; i++){
v.push_back(b3[i]);
}
for(int i = 0; i < b4.size()-1; i++){
v.push_back(b4[i]);
}
for(int i = 0; i < b5.size()-1; i++){
v.push_back(b5[i]);
}
for(int i = 0; i < b6.size()-1; i++){
v.push_back(b6[i]);
}
for(int i = 0; i < b7.size()-1; i++){
v.push_back(b7[i]);
}
for(int i = 0; i < b8.size()-1; i++){
v.push_back(b8[i]);
}
for(int i = 0; i < b9.size()-1; i++){
v.push_back(b9[i]);
}
return v;
}
c++ sorting bucket-sort
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
I'm trying to make a bucket sort but my program causes segmentation fault and i can't find out why. I use two extra functions which help me sort out the buckets i am using which are a swap function that changes two elements in a vector and then a bubble sort which uses the swap function. The vector given will always have 10 numbers and be between 0 and 99.
template <class T>
void Sorts<T>::swap(std::vector<T> &v, int i, int j) {
T aux = v[i];
v[i] = v[j];
v[j] = aux;
}
template <class T>
std::vector<T> Sorts<T>::bubbleSort(const std::vector<T> &source) {
std::vector<T> v(source);
for(int i = v.size() -1; i > 0; i--){
for(int j = 0; j<i; j++){
if(v[j] > v[j+1]){
swap(v, j, j+1);
}
}
}
return v;
}
template <class T>
std::vector<T> Sorts<T>::bucketSort(const std::vector<T> &source) {
std::vector<T> v = source;
std::vector<T> b0, b1, b2, b3, b4, b5, b6, b7, b8, b9;
for(int i = 0; i < v.size()-1; i++){
if(v[i] >= 0 && v[i] <= 9){
b0.push_back(v[i]);
} else if(v[i] >= 10 && v[i] <= 19){
b1.push_back(v[i]);
} else if(v[i] >= 20 && v[i] <= 29){
b2.push_back(v[i]);
} else if(v[i] >= 30 && v[i] <= 39){
b3.push_back(v[i]);
} else if(v[i] >= 40 && v[i] <= 49){
b4.push_back(v[i]);
} else if(v[i] >= 50 && v[i] <= 59){
b5.push_back(v[i]);
} else if(v[i] >= 60 && v[i] <= 69){
b6.push_back(v[i]);
} else if(v[i] >= 70 && v[i] <= 79){
b7.push_back(v[i]);
} else if(v[i] >= 80 && v[i] <= 89){
b8.push_back(v[i]);
} else if(v[i] >= 90 && v[i] <= 99){
b9.push_back(v[i]);
}
}
if(!b0.empty()){
b0 = bubbleSort(b0);
}
if(!b1.empty()){
b1 = bubbleSort(b1);
}
if(!b2.empty()){
b2 = bubbleSort(b2);
}
if(!b3.empty()){
b3 = bubbleSort(b3);
}
if(!b4.empty()){
b4 = bubbleSort(b4);
}
if(!b5.empty()){
b5 = bubbleSort(b5);
}
if(!b6.empty()){
b6 = bubbleSort(b6);
}
if(!b7.empty()){
b7 = bubbleSort(b7);
}
if(!b8.empty()){
b8 = bubbleSort(b8);
}
if(!b9.empty()){
b9 = bubbleSort(b9);
}
v.clear();
for(int i = 0; i < b0.size()-1; i++){
v.push_back(b0[i]);
}
for(int i = 0; i < b1.size()-1; i++){
v.push_back(b1[i]);
}
for(int i = 0; i < b2.size()-1; i++){
v.push_back(b2[i]);
}
for(int i = 0; i < b3.size()-1; i++){
v.push_back(b3[i]);
}
for(int i = 0; i < b4.size()-1; i++){
v.push_back(b4[i]);
}
for(int i = 0; i < b5.size()-1; i++){
v.push_back(b5[i]);
}
for(int i = 0; i < b6.size()-1; i++){
v.push_back(b6[i]);
}
for(int i = 0; i < b7.size()-1; i++){
v.push_back(b7[i]);
}
for(int i = 0; i < b8.size()-1; i++){
v.push_back(b8[i]);
}
for(int i = 0; i < b9.size()-1; i++){
v.push_back(b9[i]);
}
return v;
}
c++ sorting bucket-sort
c++ sorting bucket-sort
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
asked Nov 20 at 4:27
Luis Carlos Santillán Chowell
1
1
Try removing the template, I doubt you need it, you just need to specialize the vector to int like sostd::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.
– Chris Mc
Nov 20 at 4:50
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.
– PaulMcKenzie
Nov 20 at 5:12
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09
add a comment |
Try removing the template, I doubt you need it, you just need to specialize the vector to int like sostd::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.
– Chris Mc
Nov 20 at 4:50
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.
– PaulMcKenzie
Nov 20 at 5:12
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09
Try removing the template, I doubt you need it, you just need to specialize the vector to int like so
std::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.– Chris Mc
Nov 20 at 4:50
Try removing the template, I doubt you need it, you just need to specialize the vector to int like so
std::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.– Chris Mc
Nov 20 at 4:50
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (
std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.– PaulMcKenzie
Nov 20 at 5:12
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (
std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.– PaulMcKenzie
Nov 20 at 5:12
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53386232%2fmake-a-bucket-sort%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53386232%2fmake-a-bucket-sort%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Try removing the template, I doubt you need it, you just need to specialize the vector to int like so
std::vector<int>. Maybe add where the fault occurs, it might help isolate the problem.– Chris Mc
Nov 20 at 4:50
Advice -- You can reduce a lot of that redundant code. You want to find the value that is within the range, so all you really need is to put the range limits in a sorted container, and use a binary search (
std::lower_bound) to pinpoint which range to choose. The code now becomes more scalable -- imagine if it were 20 or 30 ranges.– PaulMcKenzie
Nov 20 at 5:12
You forgot to add the calling code (main function...). Your current implementation will probably discard most of your input elements, which would explain a wrong result but not a segfault.
– grek40
Nov 20 at 7:29
Your loops are too short. I suspect that the calling code is assuming that the result is the same size as the input,
– molbdnilo
Nov 20 at 8:09