Thread: how can I keep track of the lowest of 30 changing numbers...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    77

    how can I keep track of the lowest of 30 changing numbers...

    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.

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    77
    I have to sort 30 numbers and write the lowest 5 to a 5 element array. I don't know how to start. Thanks!

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    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,

  5. #5
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    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:
    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
    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.)

    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.

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    2,675
    This isn't for school or an assignment or work.
    o_O

    /If this was Fark, the "Unlikely" tag would be applicable.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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:
    Code:
    for(i=0;i<10;i++) {
       number = nextValue;
       a[number]++;
    }
    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<5;i++) {
       if(array[i] > 0)
          printf("%d  ",array[i]);
    }
    Because there is no sorting, it's incredibly fast - IF - the numbers are within a reasonable range, and they consist of only positive numbers.

    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.
    Last edited by Adak; 07-27-2012 at 10:28 AM.

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    I have to sort 30 numbers and write the lowest 5 to a 5 element array. I don't know how to start. Thanks!
    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?

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by jerrykelleyjr
    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 recommend addressing smokeyangel's points from post #4; what you are actually trying to do is not clear to me.

    Quote Originally Posted by cyberfish
    Sort the array, and take the last 5. Not the most efficient way (Olog(n)), but probably the easiest.
    Looks like a typo error, i.e., "Olog(n)" should have been "O(n log n)".

    Quote Originally Posted by cyberfish
    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.
    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 Nominal Animal
    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.
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    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. ]
    Last edited by manasij7479; 07-27-2012 at 11:41 AM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to drop 2 lowest numbers (grades) in a C program
    By h20skier in forum C Programming
    Replies: 6
    Last Post: 04-19-2011, 10:18 PM
  2. Trying to sort numbers from lowest to highest
    By jw232 in forum C++ Programming
    Replies: 21
    Last Post: 01-21-2008, 04:03 PM
  3. lowest spacing between numbers
    By Ene Dene in forum C++ Programming
    Replies: 8
    Last Post: 12-05-2007, 04:08 PM
  4. Changing random numbers
    By napkin111 in forum C++ Programming
    Replies: 1
    Last Post: 09-04-2002, 11:40 AM
  5. Changing Random Numbers?
    By napkin111 in forum C++ Programming
    Replies: 6
    Last Post: 04-23-2002, 12:13 PM