Counting number of swaps and comparisons in selection sort
I am trying to count the number of swaps and comparisons in selection sort.
Array = [7, -9, -2, 17, 19, 12, 8, 1, -20, 15, 3, 5].
void main()
{
int size = 12, arr = { 7, - 9, - 2, 17, 19, 12, 8, 1, - 20, 15, 3, 5 };
int i, j, temp;
int comparison = 0;
int swaps = 0;
std::cout << "Unsorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "n";
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
comparison = comparison + 1;
if (arr[i] > arr[j])
{
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
std::cout << "nComparisons: " << comparison;
std::cout << "nSwap: " << swaps;
std::cout << "nnSorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
This returns 66 comparisons and 34 swaps. How do you count and output the number of comparisons and swaps correctly?
c++ sorting
asked Nov 21 '18 at 14:12
CrDSCrDS
234
add a comment |
I am trying to count the number of swaps and comparisons in selection sort.
Array = [7, -9, -2, 17, 19, 12, 8, 1, -20, 15, 3, 5].
void main()
{
int size = 12, arr = { 7, - 9, - 2, 17, 19, 12, 8, 1, - 20, 15, 3, 5 };
int i, j, temp;
int comparison = 0;
int swaps = 0;
std::cout << "Unsorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "n";
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
comparison = comparison + 1;
if (arr[i] > arr[j])
{
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
std::cout << "nComparisons: " << comparison;
std::cout << "nSwap: " << swaps;
std::cout << "nnSorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
This returns 66 comparisons and 34 swaps. How do you count and output the number of comparisons and swaps correctly?
c++ sorting
asked Nov 21 '18 at 14:12
CrDSCrDS
234
6
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
6
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
5
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27
add a comment |
I am trying to count the number of swaps and comparisons in selection sort.
Array = [7, -9, -2, 17, 19, 12, 8, 1, -20, 15, 3, 5].
void main()
{
int size = 12, arr = { 7, - 9, - 2, 17, 19, 12, 8, 1, - 20, 15, 3, 5 };
int i, j, temp;
int comparison = 0;
int swaps = 0;
std::cout << "Unsorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "n";
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
comparison = comparison + 1;
if (arr[i] > arr[j])
{
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
std::cout << "nComparisons: " << comparison;
std::cout << "nSwap: " << swaps;
std::cout << "nnSorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
This returns 66 comparisons and 34 swaps. How do you count and output the number of comparisons and swaps correctly?
c++ sorting
asked Nov 21 '18 at 14:12
CrDSCrDS
234
I am trying to count the number of swaps and comparisons in selection sort.
Array = [7, -9, -2, 17, 19, 12, 8, 1, -20, 15, 3, 5].
void main()
{
int size = 12, arr = { 7, - 9, - 2, 17, 19, 12, 8, 1, - 20, 15, 3, 5 };
int i, j, temp;
int comparison = 0;
int swaps = 0;
std::cout << "Unsorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "n";
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
comparison = comparison + 1;
if (arr[i] > arr[j])
{
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
std::cout << "nComparisons: " << comparison;
std::cout << "nSwap: " << swaps;
std::cout << "nnSorted: ";
for (i = 0; i < size; i++)
{
std::cout << arr[i] << " ";
}
This returns 66 comparisons and 34 swaps. How do you count and output the number of comparisons and swaps correctly?
c++ sorting
c++ sorting
asked Nov 21 '18 at 14:12
CrDSCrDS
234
asked Nov 21 '18 at 14:12
CrDSCrDS
234
edited Nov 21 '18 at 14:14
CrDS
asked Nov 21 '18 at 14:12
CrDSCrDS
234
asked Nov 21 '18 at 14:12
CrDSCrDS
234
asked Nov 21 '18 at 14:12
CrDSCrDS
234
234
6
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
6
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
5
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27
add a comment |
6
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
6
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
5
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27
6
6
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
6
6
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
5
5
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27
add a comment |
1 Answer
1
active
oldest
votes
On this awesome website http://bigocheatsheet.com/ you can find the Order for all different sorting algorithms. It says that selection sort should have a worst case of O(n^2). You've got 12 variables; 12^2 = 144, which is way larger than the number of swaps and comparisons you've got -- so you're well within the worst case range.
However, if you're saying you want to output the swaps that are made, and not the actual number of swaps, you can write something like:
if (arr[i] > arr[j])
{
std::cout << "Swapping " << arr[i] << " with " << arr[j] << ".n";
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
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
});
}
});
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%2f53413988%2fcounting-number-of-swaps-and-comparisons-in-selection-sort%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
On this awesome website http://bigocheatsheet.com/ you can find the Order for all different sorting algorithms. It says that selection sort should have a worst case of O(n^2). You've got 12 variables; 12^2 = 144, which is way larger than the number of swaps and comparisons you've got -- so you're well within the worst case range.
However, if you're saying you want to output the swaps that are made, and not the actual number of swaps, you can write something like:
if (arr[i] > arr[j])
{
std::cout << "Swapping " << arr[i] << " with " << arr[j] << ".n";
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
add a comment |
On this awesome website http://bigocheatsheet.com/ you can find the Order for all different sorting algorithms. It says that selection sort should have a worst case of O(n^2). You've got 12 variables; 12^2 = 144, which is way larger than the number of swaps and comparisons you've got -- so you're well within the worst case range.
However, if you're saying you want to output the swaps that are made, and not the actual number of swaps, you can write something like:
if (arr[i] > arr[j])
{
std::cout << "Swapping " << arr[i] << " with " << arr[j] << ".n";
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
add a comment |
On this awesome website http://bigocheatsheet.com/ you can find the Order for all different sorting algorithms. It says that selection sort should have a worst case of O(n^2). You've got 12 variables; 12^2 = 144, which is way larger than the number of swaps and comparisons you've got -- so you're well within the worst case range.
However, if you're saying you want to output the swaps that are made, and not the actual number of swaps, you can write something like:
if (arr[i] > arr[j])
{
std::cout << "Swapping " << arr[i] << " with " << arr[j] << ".n";
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
On this awesome website http://bigocheatsheet.com/ you can find the Order for all different sorting algorithms. It says that selection sort should have a worst case of O(n^2). You've got 12 variables; 12^2 = 144, which is way larger than the number of swaps and comparisons you've got -- so you're well within the worst case range.
However, if you're saying you want to output the swaps that are made, and not the actual number of swaps, you can write something like:
if (arr[i] > arr[j])
{
std::cout << "Swapping " << arr[i] << " with " << arr[j] << ".n";
swaps = swaps + 1;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
edited Nov 21 '18 at 18:21
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
answered Nov 21 '18 at 18:08
Little Boy BlueLittle Boy Blue
336215
336215
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
add a comment |
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
2
2
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
This is not the way big O notation works. You can get a number that's larger than n^2 for a specific value of n and still be O(n^2) worst case.
– interjay
Nov 21 '18 at 18:22
add a comment |
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.
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%2f53413988%2fcounting-number-of-swaps-and-comparisons-in-selection-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
6
Is there a problem with the numbers you get? What did you expect them to be?
– Some programmer dude
Nov 21 '18 at 14:14
6
Your shown code seems show that already. What is your issue ?
– darune
Nov 21 '18 at 14:14
5
How do you count and output the number of comparisons and swaps correctly I also think you are already doing that. If you don't trust the result try a few sorts of 3 numbers on paper and see if you get the same results.
– drescherjm
Nov 21 '18 at 14:27