Mixing
Sorting an array of numbers by descending frequency
$begingroup$
Somebody asked me to create a code that orders unique numbers of an array according to their frequency, ie:
{1,3,3,4,4,4,4,4,2,2,5,5,5,5}
to
{4,5,3,2,1}
I'm a beginner and only started learning C last week so my code probably isn't optimal. I managed to get it in just over 100 lines without worrying too much about space. I haven't messed with memory allocation yet but I should start looking into it.
Any tips or feedback?
#include <stdio.h>
#include <string.h>
void CalculateFrequency(int numbers, int frequency) //Populates an array with the frequency of numbers in another
{
int hasSorted = 0;
do
{
hasSorted = 0;
for(int currentInt=0; currentInt<10; currentInt++)
{
for(int i=0; i<10; i++)
{
if(numbers[i] == currentInt)
{
frequency[currentInt]++;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
void SortByFrequency(int numbers, int frequency) //Sorts an array according to the frequency of the numbers
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i=0; i<10; i++)
{
for(int i=0; i<10; i++)
{
if(frequency[numbers[i]] < frequency[numbers[i+1]])
{
temp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = temp;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
int CountUniqueNumbers(int array, int arrayLength) //Counts unique numbers in an array
{
int count = 1; //At least 1 number
for(int i=0; i<arrayLength-1; i++)
{
if(array[i] != array[i+1])
{
count++;
}
}
return count;
}
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 0;
sortedByFrequency[0] = numbers[0];
for(int i=0; i<10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
return k;
}
int counter;
int main(void)
{
int numbers[10] = {1,2,2,2,5,7,8,8,8,8};
int frequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequencyTrueLength = 0;
int differentNumbers = 1; /*The array must have at least 1 number*/
int sizeofNumbersArray = 10;
int uniqueNumbersInArray = 0;
int i = 0;
/*print the numbers*/
printf("Numbers:t");
for(int i=0; i<10; i++)
{
printf("%d ", numbers[i]);
}
puts("");
/*Perform functions*/
CalculateFrequency(numbers, frequency);
SortByFrequency(numbers, frequency);
/*Get amount of unique numbers in the array*/
uniqueNumbersInArray = CountUniqueNumbers(numbers, sizeofNumbersArray);
/*Poupulate the unique number frequency array and get the true length*/
sortedByFrequencyTrueLength = PopulateArrayByFrequencyAndReturnLength(numbers, sortedByFrequency);
//Print unique number frequency array
printf("Numbers sorted by frequency:t");
for(i=0; i<sortedByFrequencyTrueLength; i++)
{
printf("%d ", sortedByFrequency[i]);
}
puts("");
return 0;
}
beginner c array sorting
edited Jan 17 at 23:37
200_success
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
$endgroup$
add a comment |
$begingroup$
Somebody asked me to create a code that orders unique numbers of an array according to their frequency, ie:
{1,3,3,4,4,4,4,4,2,2,5,5,5,5}
to
{4,5,3,2,1}
I'm a beginner and only started learning C last week so my code probably isn't optimal. I managed to get it in just over 100 lines without worrying too much about space. I haven't messed with memory allocation yet but I should start looking into it.
Any tips or feedback?
#include <stdio.h>
#include <string.h>
void CalculateFrequency(int numbers, int frequency) //Populates an array with the frequency of numbers in another
{
int hasSorted = 0;
do
{
hasSorted = 0;
for(int currentInt=0; currentInt<10; currentInt++)
{
for(int i=0; i<10; i++)
{
if(numbers[i] == currentInt)
{
frequency[currentInt]++;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
void SortByFrequency(int numbers, int frequency) //Sorts an array according to the frequency of the numbers
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i=0; i<10; i++)
{
for(int i=0; i<10; i++)
{
if(frequency[numbers[i]] < frequency[numbers[i+1]])
{
temp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = temp;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
int CountUniqueNumbers(int array, int arrayLength) //Counts unique numbers in an array
{
int count = 1; //At least 1 number
for(int i=0; i<arrayLength-1; i++)
{
if(array[i] != array[i+1])
{
count++;
}
}
return count;
}
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 0;
sortedByFrequency[0] = numbers[0];
for(int i=0; i<10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
return k;
}
int counter;
int main(void)
{
int numbers[10] = {1,2,2,2,5,7,8,8,8,8};
int frequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequencyTrueLength = 0;
int differentNumbers = 1; /*The array must have at least 1 number*/
int sizeofNumbersArray = 10;
int uniqueNumbersInArray = 0;
int i = 0;
/*print the numbers*/
printf("Numbers:t");
for(int i=0; i<10; i++)
{
printf("%d ", numbers[i]);
}
puts("");
/*Perform functions*/
CalculateFrequency(numbers, frequency);
SortByFrequency(numbers, frequency);
/*Get amount of unique numbers in the array*/
uniqueNumbersInArray = CountUniqueNumbers(numbers, sizeofNumbersArray);
/*Poupulate the unique number frequency array and get the true length*/
sortedByFrequencyTrueLength = PopulateArrayByFrequencyAndReturnLength(numbers, sortedByFrequency);
//Print unique number frequency array
printf("Numbers sorted by frequency:t");
for(i=0; i<sortedByFrequencyTrueLength; i++)
{
printf("%d ", sortedByFrequency[i]);
}
puts("");
return 0;
}
beginner c array sorting
edited Jan 17 at 23:37
200_success
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
$endgroup$
2
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44
add a comment |
$begingroup$
Somebody asked me to create a code that orders unique numbers of an array according to their frequency, ie:
{1,3,3,4,4,4,4,4,2,2,5,5,5,5}
to
{4,5,3,2,1}
I'm a beginner and only started learning C last week so my code probably isn't optimal. I managed to get it in just over 100 lines without worrying too much about space. I haven't messed with memory allocation yet but I should start looking into it.
Any tips or feedback?
#include <stdio.h>
#include <string.h>
void CalculateFrequency(int numbers, int frequency) //Populates an array with the frequency of numbers in another
{
int hasSorted = 0;
do
{
hasSorted = 0;
for(int currentInt=0; currentInt<10; currentInt++)
{
for(int i=0; i<10; i++)
{
if(numbers[i] == currentInt)
{
frequency[currentInt]++;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
void SortByFrequency(int numbers, int frequency) //Sorts an array according to the frequency of the numbers
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i=0; i<10; i++)
{
for(int i=0; i<10; i++)
{
if(frequency[numbers[i]] < frequency[numbers[i+1]])
{
temp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = temp;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
int CountUniqueNumbers(int array, int arrayLength) //Counts unique numbers in an array
{
int count = 1; //At least 1 number
for(int i=0; i<arrayLength-1; i++)
{
if(array[i] != array[i+1])
{
count++;
}
}
return count;
}
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 0;
sortedByFrequency[0] = numbers[0];
for(int i=0; i<10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
return k;
}
int counter;
int main(void)
{
int numbers[10] = {1,2,2,2,5,7,8,8,8,8};
int frequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequencyTrueLength = 0;
int differentNumbers = 1; /*The array must have at least 1 number*/
int sizeofNumbersArray = 10;
int uniqueNumbersInArray = 0;
int i = 0;
/*print the numbers*/
printf("Numbers:t");
for(int i=0; i<10; i++)
{
printf("%d ", numbers[i]);
}
puts("");
/*Perform functions*/
CalculateFrequency(numbers, frequency);
SortByFrequency(numbers, frequency);
/*Get amount of unique numbers in the array*/
uniqueNumbersInArray = CountUniqueNumbers(numbers, sizeofNumbersArray);
/*Poupulate the unique number frequency array and get the true length*/
sortedByFrequencyTrueLength = PopulateArrayByFrequencyAndReturnLength(numbers, sortedByFrequency);
//Print unique number frequency array
printf("Numbers sorted by frequency:t");
for(i=0; i<sortedByFrequencyTrueLength; i++)
{
printf("%d ", sortedByFrequency[i]);
}
puts("");
return 0;
}
beginner c array sorting
edited Jan 17 at 23:37
200_success
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
$endgroup$
Somebody asked me to create a code that orders unique numbers of an array according to their frequency, ie:
{1,3,3,4,4,4,4,4,2,2,5,5,5,5}
to
{4,5,3,2,1}
I'm a beginner and only started learning C last week so my code probably isn't optimal. I managed to get it in just over 100 lines without worrying too much about space. I haven't messed with memory allocation yet but I should start looking into it.
Any tips or feedback?
#include <stdio.h>
#include <string.h>
void CalculateFrequency(int numbers, int frequency) //Populates an array with the frequency of numbers in another
{
int hasSorted = 0;
do
{
hasSorted = 0;
for(int currentInt=0; currentInt<10; currentInt++)
{
for(int i=0; i<10; i++)
{
if(numbers[i] == currentInt)
{
frequency[currentInt]++;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
void SortByFrequency(int numbers, int frequency) //Sorts an array according to the frequency of the numbers
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i=0; i<10; i++)
{
for(int i=0; i<10; i++)
{
if(frequency[numbers[i]] < frequency[numbers[i+1]])
{
temp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = temp;
hasSorted = 1;
}
}
}
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
}
int CountUniqueNumbers(int array, int arrayLength) //Counts unique numbers in an array
{
int count = 1; //At least 1 number
for(int i=0; i<arrayLength-1; i++)
{
if(array[i] != array[i+1])
{
count++;
}
}
return count;
}
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 0;
sortedByFrequency[0] = numbers[0];
for(int i=0; i<10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
return k;
}
int counter;
int main(void)
{
int numbers[10] = {1,2,2,2,5,7,8,8,8,8};
int frequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequency[10] = {0,0,0,0,0,0,0,0,0,0};
int sortedByFrequencyTrueLength = 0;
int differentNumbers = 1; /*The array must have at least 1 number*/
int sizeofNumbersArray = 10;
int uniqueNumbersInArray = 0;
int i = 0;
/*print the numbers*/
printf("Numbers:t");
for(int i=0; i<10; i++)
{
printf("%d ", numbers[i]);
}
puts("");
/*Perform functions*/
CalculateFrequency(numbers, frequency);
SortByFrequency(numbers, frequency);
/*Get amount of unique numbers in the array*/
uniqueNumbersInArray = CountUniqueNumbers(numbers, sizeofNumbersArray);
/*Poupulate the unique number frequency array and get the true length*/
sortedByFrequencyTrueLength = PopulateArrayByFrequencyAndReturnLength(numbers, sortedByFrequency);
//Print unique number frequency array
printf("Numbers sorted by frequency:t");
for(i=0; i<sortedByFrequencyTrueLength; i++)
{
printf("%d ", sortedByFrequency[i]);
}
puts("");
return 0;
}
beginner c array sorting
beginner c array sorting
edited Jan 17 at 23:37
200_success
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
edited Jan 17 at 23:37
200_success
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
edited Jan 17 at 23:37
200_success
129k15153417
edited Jan 17 at 23:37
200_success
129k15153417
edited Jan 17 at 23:37
200_success
129k15153417
129k15153417
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
asked Jan 17 at 16:16
Steffan Clent DaviesSteffan Clent Davies
1213
1213
2
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44
add a comment |
2
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44
2
2
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I see a couple occurrences of:
do
{
hasSorted = 0;
...other things...
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).
Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.
answered Jan 17 at 16:50
snetchsnetch
24617
$endgroup$
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
add a comment |
$begingroup$
A few things I noticed:
Unused variables
The variables
differentNumberssizeofNumbersArrayuniqueNumbersInArray
are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!
Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.
for(int i = 0; i < 10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.
The same thing (for the same reasons) happens in SortByFrequency.
Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.
You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 1;
sortedByFrequency[0] = numbers[0];
for(int i = 1; i < 10; i++)
{
if(numbers[i-1] != numbers[i])
{
sortedByFrequency[k++] = numbers[i];
}
}
return k;
}
Reducing Iterations
1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:
void CalculateFrequency(int numbers, int frequency)
{
for(int i = 0; i < 10; i++)
frequency[numbers[i]]++;
}
2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:
void SortByFrequency(int numbers, int frequency)
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9-i; j++)
{
if(frequency[numbers[j]] < frequency[numbers[j+1]])
{
temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
hasSorted = 1;
}
}
}
} while (hasSorted);
}
Miscellaneous
- As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
- The length of the array, hard coded inside your functions, should really be an additional parameter.
- Array initialisation can be done shorter:
This sets all entries to zero:
int frequency[10] = {0};
int sortedByFrequency[10] = {0};
Or you could opt to use static arrays, they are initialised to zero:
static int frequency[10];
static int sortedByFrequency[10];
answered Jan 17 at 20:51
jgbjgb
11514
$endgroup$
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcodereview.stackexchange.com%2fquestions%2f211702%2fsorting-an-array-of-numbers-by-descending-frequency%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I see a couple occurrences of:
do
{
hasSorted = 0;
...other things...
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).
Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.
answered Jan 17 at 16:50
snetchsnetch
24617
$endgroup$
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
add a comment |
$begingroup$
I see a couple occurrences of:
do
{
hasSorted = 0;
...other things...
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).
Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.
answered Jan 17 at 16:50
snetchsnetch
24617
$endgroup$
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
add a comment |
$begingroup$
I see a couple occurrences of:
do
{
hasSorted = 0;
...other things...
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).
Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.
answered Jan 17 at 16:50
snetchsnetch
24617
$endgroup$
I see a couple occurrences of:
do
{
hasSorted = 0;
...other things...
if(hasSorted == 0)
{
break;
}
}while(hasSorted == 0);
Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).
Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.
answered Jan 17 at 16:50
snetchsnetch
24617
answered Jan 17 at 16:50
snetchsnetch
24617
answered Jan 17 at 16:50
snetchsnetch
24617
answered Jan 17 at 16:50
snetchsnetch
24617
24617
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
add a comment |
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
$begingroup$
Yes the break was redundant! Thanks for pointing that out!
$endgroup$
– Steffan Clent Davies
Jan 17 at 17:17
add a comment |
$begingroup$
A few things I noticed:
Unused variables
The variables
differentNumberssizeofNumbersArrayuniqueNumbersInArray
are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!
Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.
for(int i = 0; i < 10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.
The same thing (for the same reasons) happens in SortByFrequency.
Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.
You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 1;
sortedByFrequency[0] = numbers[0];
for(int i = 1; i < 10; i++)
{
if(numbers[i-1] != numbers[i])
{
sortedByFrequency[k++] = numbers[i];
}
}
return k;
}
Reducing Iterations
1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:
void CalculateFrequency(int numbers, int frequency)
{
for(int i = 0; i < 10; i++)
frequency[numbers[i]]++;
}
2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:
void SortByFrequency(int numbers, int frequency)
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9-i; j++)
{
if(frequency[numbers[j]] < frequency[numbers[j+1]])
{
temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
hasSorted = 1;
}
}
}
} while (hasSorted);
}
Miscellaneous
- As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
- The length of the array, hard coded inside your functions, should really be an additional parameter.
- Array initialisation can be done shorter:
This sets all entries to zero:
int frequency[10] = {0};
int sortedByFrequency[10] = {0};
Or you could opt to use static arrays, they are initialised to zero:
static int frequency[10];
static int sortedByFrequency[10];
answered Jan 17 at 20:51
jgbjgb
11514
$endgroup$
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
add a comment |
$begingroup$
A few things I noticed:
Unused variables
The variables
differentNumberssizeofNumbersArrayuniqueNumbersInArray
are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!
Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.
for(int i = 0; i < 10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.
The same thing (for the same reasons) happens in SortByFrequency.
Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.
You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 1;
sortedByFrequency[0] = numbers[0];
for(int i = 1; i < 10; i++)
{
if(numbers[i-1] != numbers[i])
{
sortedByFrequency[k++] = numbers[i];
}
}
return k;
}
Reducing Iterations
1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:
void CalculateFrequency(int numbers, int frequency)
{
for(int i = 0; i < 10; i++)
frequency[numbers[i]]++;
}
2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:
void SortByFrequency(int numbers, int frequency)
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9-i; j++)
{
if(frequency[numbers[j]] < frequency[numbers[j+1]])
{
temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
hasSorted = 1;
}
}
}
} while (hasSorted);
}
Miscellaneous
- As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
- The length of the array, hard coded inside your functions, should really be an additional parameter.
- Array initialisation can be done shorter:
This sets all entries to zero:
int frequency[10] = {0};
int sortedByFrequency[10] = {0};
Or you could opt to use static arrays, they are initialised to zero:
static int frequency[10];
static int sortedByFrequency[10];
answered Jan 17 at 20:51
jgbjgb
11514
$endgroup$
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
add a comment |
$begingroup$
A few things I noticed:
Unused variables
The variables
differentNumberssizeofNumbersArrayuniqueNumbersInArray
are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!
Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.
for(int i = 0; i < 10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.
The same thing (for the same reasons) happens in SortByFrequency.
Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.
You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 1;
sortedByFrequency[0] = numbers[0];
for(int i = 1; i < 10; i++)
{
if(numbers[i-1] != numbers[i])
{
sortedByFrequency[k++] = numbers[i];
}
}
return k;
}
Reducing Iterations
1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:
void CalculateFrequency(int numbers, int frequency)
{
for(int i = 0; i < 10; i++)
frequency[numbers[i]]++;
}
2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:
void SortByFrequency(int numbers, int frequency)
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9-i; j++)
{
if(frequency[numbers[j]] < frequency[numbers[j+1]])
{
temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
hasSorted = 1;
}
}
}
} while (hasSorted);
}
Miscellaneous
- As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
- The length of the array, hard coded inside your functions, should really be an additional parameter.
- Array initialisation can be done shorter:
This sets all entries to zero:
int frequency[10] = {0};
int sortedByFrequency[10] = {0};
Or you could opt to use static arrays, they are initialised to zero:
static int frequency[10];
static int sortedByFrequency[10];
answered Jan 17 at 20:51
jgbjgb
11514
$endgroup$
A few things I noticed:
Unused variables
The variables
differentNumberssizeofNumbersArrayuniqueNumbersInArray
are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!
Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.
for(int i = 0; i < 10; i++)
{
if(numbers[i] != numbers[i+1])
{
sortedByFrequency[k] = numbers[i];
k++;
}
}
The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.
The same thing (for the same reasons) happens in SortByFrequency.
Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.
You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:
int PopulateArrayByFrequencyAndReturnLength(int numbers, int sortedByFrequency)
{
int k = 1;
sortedByFrequency[0] = numbers[0];
for(int i = 1; i < 10; i++)
{
if(numbers[i-1] != numbers[i])
{
sortedByFrequency[k++] = numbers[i];
}
}
return k;
}
Reducing Iterations
1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:
void CalculateFrequency(int numbers, int frequency)
{
for(int i = 0; i < 10; i++)
frequency[numbers[i]]++;
}
2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:
void SortByFrequency(int numbers, int frequency)
{
int hasSorted = 0;
int temp = 0;
do
{
hasSorted = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9-i; j++)
{
if(frequency[numbers[j]] < frequency[numbers[j+1]])
{
temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
hasSorted = 1;
}
}
}
} while (hasSorted);
}
Miscellaneous
- As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
- The length of the array, hard coded inside your functions, should really be an additional parameter.
- Array initialisation can be done shorter:
This sets all entries to zero:
int frequency[10] = {0};
int sortedByFrequency[10] = {0};
Or you could opt to use static arrays, they are initialised to zero:
static int frequency[10];
static int sortedByFrequency[10];
answered Jan 17 at 20:51
jgbjgb
11514
answered Jan 17 at 20:51
jgbjgb
11514
answered Jan 17 at 20:51
jgbjgb
11514
answered Jan 17 at 20:51
jgbjgb
11514
11514
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
add a comment |
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Nice review from a new contributor.
$endgroup$
– chux
Jan 18 at 0:49
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
$begingroup$
Thank you for the review, very helpful! Those variables were left over when I refactored the code, I must of forgot to delete them.
$endgroup$
– Steffan Clent Davies
Jan 18 at 10:10
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcodereview.stackexchange.com%2fquestions%2f211702%2fsorting-an-array-of-numbers-by-descending-frequency%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
2
$begingroup$
Welcome to Code Review! I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information
$endgroup$
– Sᴀᴍ Onᴇᴌᴀ
Jan 17 at 17:54
$begingroup$
What should happen if there is a tie?
$endgroup$
– Deduplicator
Jan 17 at 20:44