Sorting frequency of chars

Question

I just made an algorithm that counts the frequency of chars in a String. What I am confused about is how to sort the frequency so the character with the greatest number of occurences is listed at the top, and the least at the bottom.

At first I tried having another variable 'fc' (for frequency counter) to coincide with my original counter variable 'k'. However I am stuck in the thought process of how to go about sorting this frequency, the fc var I made is just useless.

Thanks for any help provided!

Here is my code:

  import java.io.*;
public class Freq
{
    public static void main(String args[])throws IOException
    {
        //read input stream
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int ci,i,j,k,l,fc;l=0;
        String str,str1;
        char c,ch;
        System.out.println("Enter your String");
        str=in.readLine();
        i=str.length();
        //cycle through ASCII table chars and obtain chars typed
        for(c='A';c<='z';c++)
        {
            k=0;
            fc=0;           //fc keeps count like k
            for(j=0;j<i;j++)
            {
                ch=str.charAt(j);
                if(ch==c)
                    k++;
                    fc=k-1;     //was going to represent this counter for 'less than k'

            }
            if(k>0)
            System.out.println("The character "+c+" has occured for "+k+" times");
        }
    }
}

Answer 1

You will need to store them all first. You can use a HashMap to store them all, it will also simplify your counting routine. Then Collections.sort on the entry set. You will need to make a Comparable> to compare the entry values for sorting.

Edited to add sample code....

    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter your String");
    String line = in.readLine();
    HashMap<Character,Integer> counts = new HashMap<>();
    for(char c : line.toCharArray()) {
        Integer count = counts.get(c);
        if (count == null) {
            count = 0;
        }
        counts.put(c, ++count);
    }
    List<Entry<Character,Integer>> list = new ArrayList<>(counts.entrySet());
    Collections.sort(list, new Comparator<Entry<Character,Integer>>() {
        @Override
        public int compare(Entry<Character, Integer> o1,
                Entry<Character, Integer> o2) {
            return o2.getValue() - o1.getValue();
        }
    });
    for(Entry<Character,Integer> entry : list) {
        System.out.println("The character "+entry.getKey() +" has occured for "+ entry.getValue()+" times");
    }

Answer 2

You can follow these steps:

1) Create a class call CharCount having two fields : char and freq. Override equals to return true if characters are equal and override hashcode to return character's hashcode. Make it implement Comparable and override compare and return -1,0 or 1 based on values of freq of objects being compared
2) Have a Set of CharCount
3)Each time you find a character create an instance of this class with character and freq as 0.
4)Check if it exists in set and update feq accordingly
5) Sort set data yourself or call Collections.sort

Answer 3

I would do it like this:

int[] frequencyArray =  new int['z' -'A'];

String inputString = "ttttttttttttttttest";

for(int i = 0; i<inputString.length();i++)
{
    frequencyArray[inputString.charAt(i) -'A']++;
}

Then, you can sort this array by any of the popular sorting algorithms of your choosing.

EDIT Made the code more memory efficient.

Answer 4

Make a function count that gives you the count of particular character and sort on behalf of count, e.g

if( count(str,str.charAt[j]) > count(str,str.charAt[j+1]) )
SWAP

its better to convert str to char array before this, then it will be like

count(chararr,charrarr[j]) 

Answer 5

This one works faster than Hashmap solution:

    public static void frequencySort(String s) {
        int[] f = new int[256];
        for (int c : s.toCharArray())
            f[c]++;
        List<CharStore> list = new ArrayList<>();
        for (int i = 0; i < f.length; i++) {
            if (f[i] != 0) list.add(new CharStore(i, f[i]));
        }
        Collections.sort(list);
        for (CharStore c : list) {
            System.out.println(((char)c.c) + " has occured " + c.count + " times";  
        }
    }

    static class CharStore implements Comparable<CharStore> {
        int c;
        int count;

        public CharStore(int c, int count) {
            this.c = c;
            this.count = count;
        }

        @Override
        public int compareTo(CharStore o) {
            return o.count - count;
        }
    }