Insertion sort function acts weird C++
0
I want to make a function to sort random numbers (generated using another function) and I've been trying to do that for some time, but nothing worked. Now I have a problem that sometimes my program compiles without any problems and sometimes it says "vector subscript out of range" and even if it compiles properly it inserts some numbers in the wrong order (especially when the next number to sort is smaller than the previous one). I've tried to use debugger and to figure out what's wrong but for me everything seems fine. Could you be so kind and help me? Thank you very much.
std::vector <int> insertion_sort(std::vector <int> generated)
{
using namespace std;
bool emplaced = false;
vector <int> buffor(1);
buffor[0] = generated[0];
for (int i = 1; i < generated.size(); i++)
{
emplaced = false;
if (generated[i] >= buffor[i-1])
{
buffor.push_back(generated[i]);
}
else
{
int x = 2;
while (((i - x) > -1))
{
if (emplaced == true)
{
break;
}
if ((i - x) == 0)
{
buffor.emplace(buffor.begin(), generated[i]);
emplaced = true;
}
if (generated[i] < bufor[i - x])
{
}
else
{
buffor.emplace(buffor.begin() + (i-x), generated[i]);
emplaced == true;
}
x++;
}
}
}
return buffor;
}
c++ function for-loop vector insertion-sort
asked Nov 13 '18 at 15:26
huehhueh
183
add a comment |
0
I want to make a function to sort random numbers (generated using another function) and I've been trying to do that for some time, but nothing worked. Now I have a problem that sometimes my program compiles without any problems and sometimes it says "vector subscript out of range" and even if it compiles properly it inserts some numbers in the wrong order (especially when the next number to sort is smaller than the previous one). I've tried to use debugger and to figure out what's wrong but for me everything seems fine. Could you be so kind and help me? Thank you very much.
std::vector <int> insertion_sort(std::vector <int> generated)
{
using namespace std;
bool emplaced = false;
vector <int> buffor(1);
buffor[0] = generated[0];
for (int i = 1; i < generated.size(); i++)
{
emplaced = false;
if (generated[i] >= buffor[i-1])
{
buffor.push_back(generated[i]);
}
else
{
int x = 2;
while (((i - x) > -1))
{
if (emplaced == true)
{
break;
}
if ((i - x) == 0)
{
buffor.emplace(buffor.begin(), generated[i]);
emplaced = true;
}
if (generated[i] < bufor[i - x])
{
}
else
{
buffor.emplace(buffor.begin() + (i-x), generated[i]);
emplaced == true;
}
x++;
}
}
}
return buffor;
}
c++ function for-loop vector insertion-sort
asked Nov 13 '18 at 15:26
huehhueh
183
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
BTW, why not usestd::sort?
– Hiroki
Nov 13 '18 at 15:41
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15
add a comment |
0
0
0
I want to make a function to sort random numbers (generated using another function) and I've been trying to do that for some time, but nothing worked. Now I have a problem that sometimes my program compiles without any problems and sometimes it says "vector subscript out of range" and even if it compiles properly it inserts some numbers in the wrong order (especially when the next number to sort is smaller than the previous one). I've tried to use debugger and to figure out what's wrong but for me everything seems fine. Could you be so kind and help me? Thank you very much.
std::vector <int> insertion_sort(std::vector <int> generated)
{
using namespace std;
bool emplaced = false;
vector <int> buffor(1);
buffor[0] = generated[0];
for (int i = 1; i < generated.size(); i++)
{
emplaced = false;
if (generated[i] >= buffor[i-1])
{
buffor.push_back(generated[i]);
}
else
{
int x = 2;
while (((i - x) > -1))
{
if (emplaced == true)
{
break;
}
if ((i - x) == 0)
{
buffor.emplace(buffor.begin(), generated[i]);
emplaced = true;
}
if (generated[i] < bufor[i - x])
{
}
else
{
buffor.emplace(buffor.begin() + (i-x), generated[i]);
emplaced == true;
}
x++;
}
}
}
return buffor;
}
c++ function for-loop vector insertion-sort
asked Nov 13 '18 at 15:26
huehhueh
183
I want to make a function to sort random numbers (generated using another function) and I've been trying to do that for some time, but nothing worked. Now I have a problem that sometimes my program compiles without any problems and sometimes it says "vector subscript out of range" and even if it compiles properly it inserts some numbers in the wrong order (especially when the next number to sort is smaller than the previous one). I've tried to use debugger and to figure out what's wrong but for me everything seems fine. Could you be so kind and help me? Thank you very much.
std::vector <int> insertion_sort(std::vector <int> generated)
{
using namespace std;
bool emplaced = false;
vector <int> buffor(1);
buffor[0] = generated[0];
for (int i = 1; i < generated.size(); i++)
{
emplaced = false;
if (generated[i] >= buffor[i-1])
{
buffor.push_back(generated[i]);
}
else
{
int x = 2;
while (((i - x) > -1))
{
if (emplaced == true)
{
break;
}
if ((i - x) == 0)
{
buffor.emplace(buffor.begin(), generated[i]);
emplaced = true;
}
if (generated[i] < bufor[i - x])
{
}
else
{
buffor.emplace(buffor.begin() + (i-x), generated[i]);
emplaced == true;
}
x++;
}
}
}
return buffor;
}
c++ function for-loop vector insertion-sort
c++ function for-loop vector insertion-sort
asked Nov 13 '18 at 15:26
huehhueh
183
asked Nov 13 '18 at 15:26
huehhueh
183
edited Nov 13 '18 at 16:21
hueh
asked Nov 13 '18 at 15:26
huehhueh
183
asked Nov 13 '18 at 15:26
huehhueh
183
asked Nov 13 '18 at 15:26
huehhueh
183
183
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
BTW, why not usestd::sort?
– Hiroki
Nov 13 '18 at 15:41
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15
add a comment |
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
BTW, why not usestd::sort?
– Hiroki
Nov 13 '18 at 15:41
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
BTW, why not use
std::sort ?– Hiroki
Nov 13 '18 at 15:41
BTW, why not use
std::sort ?– Hiroki
Nov 13 '18 at 15:41
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15
add a comment |
1 Answer
1
active
oldest
votes
0
Insertion sort is a simple sorting algorithm and can be implemented by more compact
and straightforward code like as follows:
DEMO is here.
std::vector<int> insertion_sort(const std::vector<int>& generated)
{
auto shifted(generated);
for (std::size_t j = 1; j < shifted.size(); ++j)
{
const auto temp = shifted[j];
if(shifted[j-1] > temp)
{
int i = j;
do{
shifted[i] = shifted[i-1];
--i;
} while(i > 0 && shifted[i-1] > temp);
shifted[i]=temp;
}
}
return shifted;
}
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
If the goal is to do it in a compact and straightforward way, it would be better to useemplace()with the appropriate iterator for the insertion position and letvectordo the shifting. And you can usestd::find_ifto find the appropriate iterator for the insertion point. Or better yet, use a binary search.
– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms likestd::find_ifor binary search.
– Hiroki
Nov 13 '18 at 17:11
add a comment |
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%2f53284254%2finsertion-sort-function-acts-weird-c%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
0
Insertion sort is a simple sorting algorithm and can be implemented by more compact
and straightforward code like as follows:
DEMO is here.
std::vector<int> insertion_sort(const std::vector<int>& generated)
{
auto shifted(generated);
for (std::size_t j = 1; j < shifted.size(); ++j)
{
const auto temp = shifted[j];
if(shifted[j-1] > temp)
{
int i = j;
do{
shifted[i] = shifted[i-1];
--i;
} while(i > 0 && shifted[i-1] > temp);
shifted[i]=temp;
}
}
return shifted;
}
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
If the goal is to do it in a compact and straightforward way, it would be better to useemplace()with the appropriate iterator for the insertion position and letvectordo the shifting. And you can usestd::find_ifto find the appropriate iterator for the insertion point. Or better yet, use a binary search.
– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms likestd::find_ifor binary search.
– Hiroki
Nov 13 '18 at 17:11
add a comment |
0
Insertion sort is a simple sorting algorithm and can be implemented by more compact
and straightforward code like as follows:
DEMO is here.
std::vector<int> insertion_sort(const std::vector<int>& generated)
{
auto shifted(generated);
for (std::size_t j = 1; j < shifted.size(); ++j)
{
const auto temp = shifted[j];
if(shifted[j-1] > temp)
{
int i = j;
do{
shifted[i] = shifted[i-1];
--i;
} while(i > 0 && shifted[i-1] > temp);
shifted[i]=temp;
}
}
return shifted;
}
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
If the goal is to do it in a compact and straightforward way, it would be better to useemplace()with the appropriate iterator for the insertion position and letvectordo the shifting. And you can usestd::find_ifto find the appropriate iterator for the insertion point. Or better yet, use a binary search.
– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms likestd::find_ifor binary search.
– Hiroki
Nov 13 '18 at 17:11
add a comment |
0
0
0
Insertion sort is a simple sorting algorithm and can be implemented by more compact
and straightforward code like as follows:
DEMO is here.
std::vector<int> insertion_sort(const std::vector<int>& generated)
{
auto shifted(generated);
for (std::size_t j = 1; j < shifted.size(); ++j)
{
const auto temp = shifted[j];
if(shifted[j-1] > temp)
{
int i = j;
do{
shifted[i] = shifted[i-1];
--i;
} while(i > 0 && shifted[i-1] > temp);
shifted[i]=temp;
}
}
return shifted;
}
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
Insertion sort is a simple sorting algorithm and can be implemented by more compact
and straightforward code like as follows:
DEMO is here.
std::vector<int> insertion_sort(const std::vector<int>& generated)
{
auto shifted(generated);
for (std::size_t j = 1; j < shifted.size(); ++j)
{
const auto temp = shifted[j];
if(shifted[j-1] > temp)
{
int i = j;
do{
shifted[i] = shifted[i-1];
--i;
} while(i > 0 && shifted[i-1] > temp);
shifted[i]=temp;
}
}
return shifted;
}
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
answered Nov 13 '18 at 16:45
HirokiHiroki
1,4762314
1,4762314
If the goal is to do it in a compact and straightforward way, it would be better to useemplace()with the appropriate iterator for the insertion position and letvectordo the shifting. And you can usestd::find_ifto find the appropriate iterator for the insertion point. Or better yet, use a binary search.
– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms likestd::find_ifor binary search.
– Hiroki
Nov 13 '18 at 17:11
add a comment |
If the goal is to do it in a compact and straightforward way, it would be better to useemplace()with the appropriate iterator for the insertion position and letvectordo the shifting. And you can usestd::find_ifto find the appropriate iterator for the insertion point. Or better yet, use a binary search.
– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms likestd::find_ifor binary search.
– Hiroki
Nov 13 '18 at 17:11
If the goal is to do it in a compact and straightforward way, it would be better to use
emplace() with the appropriate iterator for the insertion position and let vector do the shifting. And you can use std::find_if to find the appropriate iterator for the insertion point. Or better yet, use a binary search.– TypeIA
Nov 13 '18 at 16:51
If the goal is to do it in a compact and straightforward way, it would be better to use
emplace() with the appropriate iterator for the insertion position and let vector do the shifting. And you can use std::find_if to find the appropriate iterator for the insertion point. Or better yet, use a binary search.– TypeIA
Nov 13 '18 at 16:51
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
Thank you very much :)
– hueh
Nov 13 '18 at 16:52
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms like
std::find_if or binary search.– Hiroki
Nov 13 '18 at 17:11
@TypeIA thx a lot.I think so too. Since this is an IT studies, here I avoid using helper algorithms like
std::find_if or binary search.– Hiroki
Nov 13 '18 at 17:11
add a comment |
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.
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%2f53284254%2finsertion-sort-function-acts-weird-c%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
1) "vector subscript out of range" Is not compilation error. It's, most likely, failed runtime assertion. 2) Please provide Minimal, Complete, and Verifiable example. 3) Did you try stepping through your code with a debugger?
– Algirdas Preidžius
Nov 13 '18 at 15:30
BTW, why not use
std::sort?– Hiroki
Nov 13 '18 at 15:41
I did, but all I've noticed is that the program has problem with sorting numbers smaller than those already sorted (those in buffor vector). I have to create my own function as a exercise for my IT studies. For example if the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 But if the input is : 58 49 82 72 61 87 74 21 then I get "vector subscript out of range"
– hueh
Nov 13 '18 at 15:49
the input (vector of integers) is: 96 99 24 46 58 40 78 24 it shows: 78 78 46 78 46 78 24 78 46 78 24 96 99 58 40 24 : Is this an expected result ??
– Hiroki
Nov 13 '18 at 16:13
The expected result is 24 24 40 46 58 78 96 99
– hueh
Nov 13 '18 at 16:15