CC-17 : Sort characters by frequency.

Description:

Given an array of integers, find the rank of each integer. The largest integer will have rank 1, the second largest will have rank 2 and so on. Put each integers ranks it’s the same index in a new array and return the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
Original String: procession	String chars sorted by freq: ssooniepcr

Pseudocode:

Class CharCount:

Create an internal class CharCount.

We will extract characters from input String and for each individual character, the instances of CharCount will hold reference to the character and count of frequency of the character within the String.

Class SortByFreq:

This class implements Comparator.compare() method. The method takes 2 instance of CharCount and helps to sort the same by frequency of the character.

Method rearrange(str):

This method takes input String as parameter.

Initialize a HashMap named freq which we will use to count the frequency of occurrence of characters in the input String.

Extract the characters from input String and store in character array named chars.

Iterate though chars from index 0 to index chars.length-1:

Check if hashMap already contains chars[idx]. If already present, extract the frequency of the chars[idx] from hashMap. Increment the frequency by 1 and put chars[idx] and the updated frequency back into to the hashMap.

Initialize a PriorityQueue instance named heap. Provide an instance of SortByFreq to the constructor the PriorityQueue to sort by frequency of occurrence of characters.

Iterate through keys of hashMap freq:

Extract current Map.entry from hashMap.

Create an instance of CharCount and set the character, freq member variables.

Add the CharCount instance)to heap. The comparator provided to heap, automatically extracts the frequency corresponding to current key from hashMap and adds integer to heap as per required heap’s index sorting order.

Initialize a StringBuilder instance named sortedChars to collate the rearranged characters.

While heapsize is not 0:

Remove a CharCount instance named CharCount from top of heap.

For (int i=0; i< charCount.frequency; i++)

Append current character from CharCount to sortedChars.

Return sortedChars.toString().

Code:

public class HeapSortCharactersByFrequency {
	
class CharCount{
	char c;
	int freq;
}

class SortByFreq implements Comparator<CharCount> {
	public int compare(CharCount c1, CharCount c2) {
		if (c1.freq < c2.freq) {return 1;}
		if (c1.freq > c2.freq) {return -1;}
		return 0;
	}	
}
 
public String SortCharsByFrequency(String str) {
	HashMap<Character,Integer> freq=new HashMap<Character,Integer>();
	char[] chars=str.toCharArray();
	for (int idx=0; idx < chars.length; idx++) {
		int currFreq=freq.getOrDefault(chars[idx],0);
		freq.put(chars[idx], currFreq+1);
	}	
	PriorityQueue<CharCount> heap=new PriorityQueue<CharCount>(new SortByFreq());
	Iterator< Map.Entry < Character,Integer > > itr=freq.entrySet().iterator();
	while (itr.hasNext()) {
		Map.Entry<Character,Integer> entry=itr.next();
		CharCount charCount=new CharCount();
		charCount.c=entry.getKey();
		charCount.freq=entry.getValue();
		heap.add(charCount);
	}
	StringBuilder sortedChars=new StringBuilder();
	while(heap.size() != 0) {
		CharCount charCount=heap.remove();
		for (int i=0; i < charCount.freq; i++) {
			sortedChars.append(charCount.c);
		}
	}
	return sortedChars.toString();
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;

public class HeapSortCharactersByFrequency {
	
class CharCount{
	char c;
	int freq;
}

class SortByFreq implements Comparator<CharCount> {
	public int compare(CharCount c1, CharCount c2) {
		if (c1.freq < c2.freq) {return 1;}
		if (c1.freq > c2.freq) {return -1;}
		return 0;
	}	
}
 
public String SortCharsByFrequency(String str) {
	HashMap<Character,Integer> freq=new HashMap<Character,Integer>();
	char[] chars=str.toCharArray();
	for (int idx=0; idx < chars.length; idx++) {
		int currFreq=freq.getOrDefault(chars[idx],0);
		freq.put(chars[idx], currFreq+1);
	}	
	PriorityQueue<CharCount> heap=new PriorityQueue<CharCount>(new SortByFreq());
	Iterator < Map.Entry< Character,Integer > > itr=freq.entrySet().iterator();
	while (itr.hasNext()) {
		Map.Entry<Character,Integer> entry=itr.next();
		CharCount charCount=new CharCount();
		charCount.c=entry.getKey();
		charCount.freq=entry.getValue();
		heap.add(charCount);
	}
	StringBuilder sortedChars=new StringBuilder();
	while(heap.size() != 0) {
		CharCount charCount=heap.remove();
		for (int i=0; i < charCount.freq; i++) {
			sortedChars.append(charCount.c);
		}
	}
	return sortedChars.toString();
}

public static void main(String[] args) {

String retVal;
try {
	HeapSortCharactersByFrequency hp=new HeapSortCharactersByFrequency();
	String str= "procession";
	System.out.println("Original String: "+ str);
	retVal=hp.SortCharsByFrequency(str);
	System.out.println("String chars sorted by freq: "+ retVal);
	
	
		
}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}