Sort according to frequency

[guffadi]

    //With this method, I input a string and return an array that contains a sorted list of characters as per the frequency. Eg: If i input "apple", the out put should be p,a,l,e, How do I do this?

   public static ArrayList<Character> characterFreqDist(String statement)
{
  char[] Array = statement.toCharArray();
  int length = Array.length;
  int most_frequent_count = 0;
  char most_freq_character = '\0';
  char[] Final_Array = new char[length];

  ArrayList<Character> Sorted_Array = new ArrayList<Character>();

  for(int loop = 0 ; loop<length ; loop++)
  {
      most_freq_character = '\0';
      most_frequent_count = 0;
  for(int i = 0; i<length ; i++)
        { 
            char single_character = Array[i] ;

            int counter = 0;

            for(int j = 0; j<length ; j++)
            {
                if (single_character == Array[j])
                {
                    counter++;
                } 
            }
                if (counter > most_frequent_count)
                {
                    most_frequent_count = counter;
                    most_freq_character = single_character;
                }                   

      }

      Sorted_Array.add(most_freq_character);

                int index = 0;
                for (int k = 0; k < length; k++)
                {
                    if(Array[k] != most_freq_character)
                    Final_Array[index++] = Array[k];
                }

      Array =  Final_Array.clone();

      length = Array.length;

    }
    return Sorted_Array;
}

[JamesCherrill]

It can be done using loops like that, but you have to do something like:

while some input remains...
  find the most frequent character (like in your code)
  add the right number of that character to the output
  remove all instances of that character from the input

A much simpler approach is

Create a Map<Character, Integer>
Popuate it with the chars in the input and their corresponding counts
Get the maps EntrySet as a List and sort it by value descending
(thats just 4 lines of code so far)

build the output string from the sorted list (this is actually the messiest part!)

Finally, if you know the input is just ASCII you can use an array[128] instead of a Map for a wonderfully simple solution (just 6 short and easy lines of code)...

create an array of 128 empty Strings
append each input char to the string at index = the char
sort the array on string length descending
append all the array members to the output

(use StringBuilders instead of Strings if performance is really important)

[guffadi]

I tried the code above and it gives me wierd output.

If I input "apple ball" it returns [l, , , ,].

I create and array, and remove the most frequent characters but still dont know why it is not sorting well

[JamesCherrill]

Without seeing the actual code I cannot know anything about why it didn't work.

[guffadi]

I'm sorry. I have the code above in the question.

[JamesCherrill]

OK, I thought you had tried a different algorithm.

Unfortunately I don't have the time to plough through uncommented code that defies all normal Java coding conventions, has misleading variable names and incorrect indentation. Eg : you have three things called arrays (one of which is not an array) with no explanation of why.

If you clean up your code, with proper variable names, and comments explaining the algorithm, you will almost certainly find places where you mis-use variables or the code does not match the comments. Fix those, then put sopme print statements in your loops so you can see how your arrays are being updated. That will reveal where things are going wrong.

In the meantime, here are some guesses...
lines 13-36 find the most common char?
line 38 appends it to the output list ... but just one char (should be added count times?)
lines 40-49 remove the char from the source array? (but leave it padded with zeros, which will soon become the most common char?)

[JamesCherrill]

<3 hours later>

Found a little time and confirmed just two bugs to be fixed:
append correct number of chars to output
deal with unused array members when removing chars from source array

With those two fixes it's giving me the correct result.