Printable View
I apologize fot the question but I need to know how can I write a piece of code that keeps track of 30 different numbers that can continuously change in value. I need to track all 30 and write the lowest 5 of the 30 to a five element array. This isn't for school or an assignment or work. Any help is appreciated. Thank you. Jerry.
Sort the array, and take the last 5. Not the most efficient way (Olog(n)), but probably the easiest.
The more efficient (O(n)) way is to start with the first 5 numbers, and for every new number you get, add to the list (so now there are 6), and remove the largest number from the list.
I have to sort 30 numbers and write the lowest 5 to a 5 element array. I don't know how to start. Thanks!
Depends what you mean by "continuously change". If your program is changing them, then you can sort the array each time a change is made (because you know where changes are made).
If something outside your program is changing the numbers (e.g. some shared resource) then that's trickier -- it'd depend on the use case and system I think.
If you just mean the array will have different values each time the program is run, then yes, sorting them is easiest. You can sort with qsort: qsort - C++ Reference then just copy the first or last 5 numbers to another array,
Quicksort is not optimal for short arrays. For 30 elements, implement a selection sort instead. That's what most quicksort implementations do anyway. A selection sort in pseudocode is:
Note that this variant is stable: equal values are kept in the same order. For integers this does not matter at all, but it is useful would for associated data. (You only need to swap the associated data for indices target and smallest_index in the last if clause, if you have any.)Code:/* Sort count elements in array in ascending order. */
for target = 0 to count - 1
smallest_value = array[target]
smallest_index = target
for index = target + 1 to count - 1
if array[index] < smallest_value
smallest_index = index
smallest_value = array[index]
end if
end for
if smallest_index > target
array[smallest_index] = array[target]
array[target] = smallest_value
end if
end for
In your case, I recommend copying the changing 30 values to a temporary array, sorting it using the above algorithm, and then copying the first five values to the five-element array.
o_OQuote:
This isn't for school or an assignment or work.
/If this was Fark, the "Unlikely" tag would be applicable.
If the range of the numbers is small, a fast and easy way to do this is to use "counting" sort. It's how you can have the effect of sorting data, without having to actually sort, anything.
Say you had 10 numbers, and they were all odd numbers: (7,11,5,9,3,15,3,11,13,7). When you get a number, you simply add one to that numbers array value[index].
Processing the above:
int number;
number=7;
a[number]++;
number=11;
a[number]++;
In a for loop:
At any time during the processing, the lower values so far, will be found in the lower array[index]. Say you want 5 of them printed out:Code:for(i=0;i<10;i++) {
number = nextValue;
a[number]++;
}
Because there is no sorting, it's incredibly fast - IF - the numbers are within a reasonable range, and they consist of only positive numbers.Code:for(i=0;i<5;i++) {
if(array[i] > 0)
printf("%d ",array[i]);
}
Naturally, you need the array values to be set to all zeroes, before you start this processing. If it's a dynamic array, use calloc, instead of malloc. If it's a global array, it will be set to all zeroes for you. If it's a local array, loop through it first, and assign zero to each array element value, with a for loop.
This "counting sort" can't be used all the time, but when it can be used, no sorting algorithm can begin to match it's speed, or simplicity. Try it, and you will be amazed. Several people have thought it was initially broken because it works so very fast.
Yes. That's what I told you. If you don't know how to start, break it down further. Do you know how to sort an array?Quote:
I have to sort 30 numbers and write the lowest 5 to a 5 element array. I don't know how to start. Thanks!
I recommend addressing smokeyangel's points from post #4; what you are actually trying to do is not clear to me.Quote:
Originally Posted by jerrykelleyjr
Looks like a typo error, i.e., "Olog(n)" should have been "O(n log n)".Quote:
Originally Posted by cyberfish
This would be O(n) because the "5" is fixed. But if instead of "5" we consider the first m numbers, then I think that you'll be dealing with a O(n log m) time complexity instead. Of course, with only 30 elements, you could even get away with using bogosort.Quote:
Originally Posted by cyberfish
Personally, I think just using qsort from <stdlib.h> would be simpler. If you did want to implement selection sort, then you might as well do a partial sort. If you wanted to be more fancy, I guess we could consider the quicksort partitioning nth element algorithm for an O(n) average case, but it is overkill for just 30 elements.Quote:
Originally Posted by Nominal Animal
I wonder if sorting the whole array every time something changes is really needed here !
Maybe I haven't read the thread carefully enough..
but one can maintain the indices of the least 5 in a separate array . (populated once at the beginning).
And then update it when needed . (That may not even need iterating over the 5 stored indices...if the least and greatest among them are known and updated accordingly.)
[Eh...that was what cyberfish suggested in the first place ! I feel a bit foolish. :(]
I recommend running the Quickselect algorithm to find the lowest k values in an array. But you have been very poor at explaining anything about the problem.
E.g. do you need to know which indexes in the array the smallest items came from, or anything like that?
You must explain in detail what this is for and precisely what it needs to do.
QuickSelect - Pinewiki
k largest(or smallest) elements in an array | added Min Heap method | GeeksforGeeks
From the original post, the phrases "continuously change in value" and "track all 30" suggest an array of 30 values that change independently of the program over time (such as 30 pH sensors in your hydroponic tomato patch).
If that's the case, then you'd want to sample them every how-ever-many milliseconds and send their values to a routine that updates the "low five". This routine could simply loop through the 30 captured values and insert them into the current low five list. That would probably be efficient enough.