Sort and count frequency of array elements.

This is a discussion on Sort and count frequency of array elements. within the C++ Programming forums, part of the General Programming Boards category; I need a help please. I have to count the frequency of values in the array. I have this code: ...

  1. #1
    just started learning
    Join Date
    Oct 2012
    Location
    Dardanelle, Arkansas, United States
    Posts
    20

    Sort and count frequency of array elements.

    I need a help please.
    I have to count the frequency of values in the array. I have this code:

    [/code]
    Code:
    int main()
    {
       int size;
       int val, count;
       int list[] = {3,4,3,2,4,5,7,4,7,8,4,4,3,2,4,7,8,5,4,3,3,3,4,5,5};
       size = sizeof(list)/sizeof(int);
    
    
       cout << "Our unsorted list is: ";
       print(list, size);
       cout << endl;
    
    
       sort(list, size);
       cout << "Our sorted list is: ";
       print(list, size);
    
    
       cout << setw(6) << "Value:" << setw(12) << "Frequnce" << endl;
       getFrequency (val, list, size, count);
    
    
       return 0;
    }
    
    
    void getFrequency (int val, int list[], int size, int &count)
    {
      for (int v=0; v<size; v++)
      {
        val = list[v] ;
        int count = 0;
        for (int k=0;k<size;k++)
        {
          if(list[k]==val)
             count++ ;
        }
        cout << setw(3) << val << " " << setw(10) << count <<endl;
      }
    }
    The code works, but at the end it outputs like
    2 2
    2 2
    3 6
    3 6
    3 6 etc.

    I can't figure out the missing part of the code so that output is only 1 of each repeating value like
    2 2
    3 6
    4 8 etc.

    Thank you.
    P.S. I can't use pointers or classes with this task

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    Basically, you need to map each distinct element of the array to its frequency. The generic easy way is to just use a std::map or std::unordered_map. In this case though, if the elements of the array are guaranteed to be within some small range, you could just use another array to store the mapping.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    I want to point out that the prototype could be instead of this
    Code:
    void getFrequency (int val, int list[], int size, int &count)
    this
    Code:
    void getFrequency (int list[], int size)
    -Why?
    -Because val and count are local variables and should live only inside the.Also with your implementation you declare new ones inside the body,so no use of the parameters val and count.

    As for the algorithm ,the same values lie next to each other,so let's take for example this sorted list
    2,2,3,3,3,3,3,3
    your algorithm will go and check the first element (list[0]) and will compute its frequency and eventually print it.Good until here.Now the main loop starts again,and v is increased by one... (!)
    So now we are going to check for element list[1]...which is the same as the first..we do not want that.We want the value of v to be increased by two,so let's have this main for
    Code:
    for (int v=0; v<size; v+=2)
    or not?Of course not!If you continue the algorithm and you reach the 3s then you see it will print 3 6 more than once and less that what you posted?
    -Why?
    -Because you increase the v by two.We should increase it by the number of the counter,in order to do not same 2 again while val is 2,or 3 again while val is 3
    Hope this helps

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    Oh... actually yeah: since the instruction is to sort first, a mapping container is not needed if all you are going to do is to print the mapping immediately after computing the frequency. On the other hand, then getFrequency is not a good name for the function: something like "printFrequencies" may be better.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    just started learning
    Join Date
    Oct 2012
    Location
    Dardanelle, Arkansas, United States
    Posts
    20
    Quote Originally Posted by laserlight View Post
    Basically, you need to map each distinct element of the array to its frequency. The generic easy way is to just use a std::map or std::unordered_map. In this case though, if the elements of the array are guaranteed to be within some small range, you could just use another array to store the mapping.
    Thank you for your advise, but I cannot use Classes here. Requirement is to use basic arrays and functions.

  6. #6
    just started learning
    Join Date
    Oct 2012
    Location
    Dardanelle, Arkansas, United States
    Posts
    20
    It would be good for this given array, but I need a generic function, in case if I don't know if there will be repetitions or how many repetitions in the array.

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by Nurlana View Post
    It would be good for this given array, but I need a generic function, in case if I don't know if there will be repetitions or how many repetitions in the array.
    I agree and the idea i said before targets this case exactly!You need to increase v by the counter of frequencies.Do not forget to initialize the counter to zero every time you are about to enter the loop.
    So
    Code:
    for (int v=0; v<size; v+=counter)
    is what i am saying
    Hope this helps

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Well it was mentioned a day ago that you should sort the array first.
    I recommend writing code to do that and post it here.
    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"

  9. #9
    just started learning
    Join Date
    Oct 2012
    Location
    Dardanelle, Arkansas, United States
    Posts
    20
    Quote Originally Posted by iMalc View Post
    Well it was mentioned a day ago that you should sort the array first.
    I recommend writing code to do that and post it here.
    I have already sorted the list. The function call is already in the main.
    As for function description, I didn't show it here, because it was working fine.

    Code:
    void sort(int list[], int size)
    {
      for (int i= size; i>1; i-- )
      {
        for (int j = 1; j<i; j++)
        {
          if (list[j-1]> list[j])
          {
            swap (list[j-1], list[j]);
          }
        }
      }
    }

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    The idea is that once you have sorted them, the adjacent elements will be grouped together. Therefore, if you do not need the count for later use, you can count them and print the count immediately (without storing in a mapping container). However, this means that you should only print the first element in each group, and start the count anew once you detect the next element (or the end of the sequence). A single loop without nesting an inner loop will do.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Oh okay, so you did.
    So, now you just need to count the number of consecutive entries that are the same. This isn't really much harder than what you've done already. Have a go and we'll help when you get stuck.
    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
    just started learning
    Join Date
    Oct 2012
    Location
    Dardanelle, Arkansas, United States
    Posts
    20
    Sorry, guys, I am really stuck. My brains will soon fry. the instructor said I need to use the following in the main:
    Code:
    cout << setw[6] << "Value" << setw(12) << "Frequency" << endl;
    int v = list[0];
    int freq = 0;
    getFrequency (v, data, size, freq);
    cout << v << "  " << freq;
    for (val=0; val<size; val++)
      if (v!=val)
     { 
        v = val;
        getFrequency (v, list, size, freq);
        cout << v << "  " << freq;
     }
    But I don't understand this code. It seems repeating same thing. Can you help?

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,707
    It seems like a very poor way of doing it to be honest. At a guess, getFrequency()'s job is to count the number of v in list, and store the answer in freq, while val goes through a small range of numbers in the for loop (equivalent to [0,size-1]). The if(v!=val) section is a kind of reset, you have to start counting the occurrences of the new val. I'm having a hard time understanding why you would write code such that you even need that if statement.

    IMHO, using this version of getFrequency() should be as simple as:
    Code:
    for (size_t i = 0; i < list.size(); i += freq) 
    {
       getFrequency(list[i], list, list.size(), freq);
       cout << list[i] << "  " << freq << endl;
    }
    [edit] Not so simple, heh. Had to change the increment of i. [/edit]
    Last edited by whiteflags; 10-26-2012 at 12:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 09-21-2012, 04:58 PM
  2. Frequency of Array Elements
    By Zaheer Attar in forum C Programming
    Replies: 6
    Last Post: 12-22-2011, 11:42 PM
  3. count and print the frequency of each ASCII character
    By s_jsstevens in forum C Programming
    Replies: 3
    Last Post: 02-07-2011, 08:33 PM
  4. count elements in an array
    By whichet in forum C Programming
    Replies: 9
    Last Post: 11-25-2007, 07:05 AM
  5. Sort indexes of frequency array?
    By davidol in forum C++ Programming
    Replies: 2
    Last Post: 06-03-2002, 09:04 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21